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