生物序列比对近似算法及其并行化研究

摘要

生物信息学是一门综合数学、计算机科学和生物学等学科的交叉学科，是当今科学的研究热点之一。生物序列比对是生物信息学中的一个基本的、重要的研究问题，是生物信息学的基础，它是进行系统进化、生态学、生物保护、疾病控制、病毒起源甚至HIV病毒统计和传播等方面研究的基本工具，并可用来预测生物序列的功能、结构和进化过程等。所以，进行生物序列比对研究具有重要的理论意义和应用价值。 生物序列比对可分为双生物序列比对和多生物序列比对。本文在分析生物序列本身的固有特性和常用生物序列比对算法的基础上，对生物序列比对问题进行了学习和研究，主要研究内容包括：(1)基于结构信息预处理的双生物序列比对算法用于解决双生物序列比对的常用算法基本上都是用动态规划的方法来逐点计算双生物序列问的代价，这些方法可以发现数学意义上具有最大计分值的比对结果，但这种比对结果有时可能忽略了生物序列中所隐含的结构信息。为了在双序列比对中更好地考虑生物序列的结构信息，本文利用可变长马尔可夫链方法来预测生物序列中所隐含的结构信息，然后再进行双生物序列的比对，最后给出了一个对经典双生物序列比对的Smith-Waterman算法的修正算法以及一个基于结构信息的启发式算法。实验结果表明，这可以有效地提高序列比对的准确性。 (2)基于结构信息的多生物序列比对启发式算法多生物序列比对是生物序列比对研究中的重点。目前，国际上常用的多序列比对算法一般都是采用渐进比对和迭代比对的方法来设计的，这些多序列比对算法都有其不同的优缺点，尤其是在序列间一致性比较低的情况下多序列比对结果的可信度不高。本文在分析生物序列特征的基础上，利用可变长马尔可夫链方法来识别多生物序列中的结构信息，并在此基础上，研究了一个聚类的多序列比对算法。实验结果表明，这个算法可以较好的对亲缘性比较差的生物序列进行比对，并且可以发现生物序列问业已清楚的结构信息。 (3)一种基于熵的多生物序列比对自适应遗传算法生物序列比对问题最大的障碍在于现在还很难找到一种把生物序列的进化过程进行合理形式化的数学方法，而遗传算法能避开问题本身的数学复杂性，基本不用搜索空间的知识或其它辅助信息来求解问题。所以本文研究用遗传算法来解决多序列比对问题，并且引入信息论中熵的概念来评价生物序列比对过程中种群的多样性，提出了一种能综合考虑生物序列间相似性和结构信息的适应度函数，用比对过程中熵的动态变化来自动调整遗传算法的交叉和变异概率，并且结合动态规划算法来设计遗传操作算子。实验结果表明，这个算法具有较强的全局搜索能力和局部搜索能力，并且能有效地克服未成熟收敛问题。 (4)生物序列比对并行算法的研究随着生物技术的进步和基因组测序的相继完成，多序列比对问题的计算规模急剧扩展，现有的一些串行算法已经很难跟上序列规模增大的要求。在实际多序列比对应用中，人们必须要考虑能否将已有的串行算法并行化，或是设计符合实际需要的并行算法，从而大大降低算法运行时间。本文首先介绍了并行算法的一些基本计算模型、双序列比对中常用的并行算法以及在CellMatrixTM结构上的并行算法，然后在研究多序列比对已有并行算法的基础上，提出了一个在SMPClusters(SMP集群)上的新的序列搜索并行算法。 本文的贡献与创新之处主要有：(1)在生物序列比对中结合了生物序列结构信息，利用可变长马尔可夫链的方法来预测生物序列间的结构信息，提出了一种新的双序列比对计分机制，并且把这种思想扩展到多序列比对上，提出了一种基于聚类方法的多序列比对方法。 (2)利用遗传算法来进行多序列比对问题的研究，引入信息论中熵的概念来评价生物序列比对过程中种群的多样性，提出了一种综合考虑生物序列间相似性和结构信息的适应度函数，用比对过程中熵的动态变化来自动调整遗传算法的交叉和变异概率。 (3)在基于二分竞赛树和并行k-选择方法的基础上，充分利用SMPClusters模型具有良好扩展性的特点，提出在此模型上的求解(K，1)序列搜索问题的并行算法。

目录

文摘

英文文摘

第1章绪论

1.1生物序列比对中的基本概念及其作用

1.1.1生物序列的相似性

1.1.2生物序列及其字母表

1.1.3编辑操作

1.1.4序列相似性的打分矩阵

1.1.5生物序列比对的意义

1.2双生物序列比对算法研究现状

1.2.1全局双生物序列比对算法的研究概况

1.2.2局部双生物序列比对算法的研究概况

1.2.3启发式双序列比对算法的研究概况

1.3多生物序列比对算法研究现状

1.3.1多生物序列比对的评分模型

1.3.2多生物序列比对精确算法研究概况

1.3.2多生物序列比对近似算法研究概况

1.3.3启发式多序列比对算法研究概况

1.3本文的研究内容和研究思路

1.4论文的组织

第2章序列比对算法的相关知识

2.1贝叶斯分析方法

2.1.1先验分布与后验分布

2.1.2贝叶斯参数估计

2.1.3贝叶斯假设检验

2.2隐马尔可夫模型

2.2.1马尔可夫链

2.2.2 隐马尔可夫模型的基本原理

2.2.3Viterbi算法

2.2.4前向算法和反向算法

2.2.5隐马尔可夫模型的参数估计

2.2.6隐马尔可夫模型上的序列比对

2.3可变长马尔可夫模型

2.3.1可变长马尔可夫模型的基本概念

2.3.2概率后缀树

2.4并行算法的基本设计技术

2.5本章小结

第3章基于结构的双生物序列比对算法

3.1经典双生物序列比对算法的分析

3.1.1经典算法与生物模式串

3.1.2序列比对的显著性

3.2双生物序列中结构信息的提取和处理

3.2.1 PST的构造

3.2.2保守子片段的确定

3.2.3保守子片段的预处理

3.3基于结构信息和动态规划方法的双序列比对算法

3.3.1计分机制的设计

3.3.2算法分析和实验结果

3.4基于结构信息的一种启发式双序列比对算法

3.4.1最长递增子序列的求解

3.4.2构造完整比对

3.5本章小结

第4章基于结构的多序列比对启发式算法

4.1常用生物多序列比对算法分析

4.1.1渐进比对算法

4.1.2迭代比对算法

4.2多生物序列比对中的序列特征分析

4.2.1序列间一致性和序列长度

4.2.2序列间的亲缘性关系

4.2.3全局比对与局部比对

4.2.4序列中的模体和样式

4.3结构信息的片段的预处理

4.3.1多生物序列的中结构片段预测

4.3.2结构子片段的排序

4.4基于结构信息的一种聚类多序列比对算法

4.4.1序列间距离的计算

4.4.2聚类算法

4.4.3算法框架

4.4.4算法实验结果

4.4.5关于算法的一些讨论

4.5本章小结

第5章多序列比对中的遗传算法

5.1遗传算法简介

5.1.1遗传算法和生物进化的联系

5.1.2标准遗传算法

5.1.3遗传算法的特点

5.2编码和适应度函数

5.2.1序列比对问题的染色体编码

5.2.2适应度函数

5.2.3保守区域的探测

5.3基于熵的遗传算法参数设置

5.3.1信息与熵

5.3.2生物序列中熵的计算

5.3.3自适应概率的设计

5.4遗传操作的设计

5.4.1选择算子的设计

5.4.2交叉算子的设计

5.4.3变异算子的设计

5.5实验验证

5.5.1数据来源和参数设定

5.5.2实验结果和讨论

5.6本章小结

第6章生物序列比对中的并行算法

6.1并行算法的概念和复杂性度量

6.2并行计算模型

6.2.1共享存储的计算模型

6.2.2分布存储的计算模型

6.2.3生物计算中的新型计算模型

6.2双生物序列比对问题的并行化

6.2.1在传统模型上的双生物序列比对并行算法

6.2.2在CELL MatrixTM模型上的双生物序列比对并行算法

6.3多生物序列比对问题的并行化

6.3.1 PRAM-CREW模型上的多序列比对

6.3.2 LARPBS模型上的多序列比对

6.4基于SMP Clusters的序列搜索的并行计算

6.4.1 SMP Clusters的计算结构

6.4.2生物序列搜索问题的描述

6.4.3分组最大比对值的并行算法

6.4.4 MESH网络上的k-选择并行算法

6.4.5 SMP Clusters模型的(K，1)序列搜索并行算法

6.5本章小结

第7章总结

7.1本文的工作

7.2本文的贡献与创新之处

7.3进一步的工作

参考文献

致谢

在读期间发表和录用的学术论文