基于A-Star和DiAlign算法的多序列比对

论文摘要

序列比对是现代生物信息学中一个最基本的研究课题。通过多序列比对,可以预测新序列的结构和功能,分析序列之间的同源关系,以及进行系统发育分析。本文首先介绍了序列比对涉及的基本问题:空位罚分,替换矩阵和比对结果评价标准。接着,主要介绍了两种序列比对算法:A*算法和斜线比对算法求多序列比对。理论上Needleman–Wunsch算法可以很容易地应用于多条序列中产生分值最优的比对,但是随着序列条数的增长,算法的复杂性成指数增长,而且算法不能扩展到多于三条序列。而A*算法利用合理的启发式函数限制多序列比对的搜索空间。用这种方法,即使是八条序列,每条序列含有几百氨基酸残基也可以同时比对。首先,该算法将多序列比对问题转化为求最短路径问题,利用A*算法可以在找到最短路径的同时有效地降低时间复杂度。本文将A*算法应用于多序列比对,选择有效的预测函数和边界值,最大限度的缩小搜索空间。并且从程序性能和算法性能上努力做出改进:找更接近的边界值;利用哈希链表代替简单链表提高程序的节点查找时间。最后,讨论了算法在测试例子中的应用,并且与经常使用的比对方法产生的结果比较。实验结果表明:设置边界值(BOUND)和利用哈稀链表代替简单链表后,程序的执行速度比未改进之前提高了好几倍。理论上讲,只要选择合适的目标函数和打分矩阵,计算出的结果应该是非常理想的;然而,实际情况与理想值之间还有较大的差距,还有待于预测函数以及目标函数进一步的改进。但是该算法的潜能是非常大的,一旦打分矩阵和目标函数的设定方面获得突破,其前景将不可限量。在本文中,接着介绍了另一个不同的序列比对的方法,即斜线比对算法。不同于比较单个的残基,它使用免空格段段比对算法比较随机长度的序列片段。特别地,该算法不使用任何空格罚分。通过定义关于斜线位置的集合,它把比对看成一个一致的等价关系。在寻找斜线段阶段,尝试使用新的方法。即先将两条序列比对,然后只在两两最优比对部分查找。在对算法的总体性能影响不太大的情况下,有效地提高了程序的执行速度。实验表明:该算法是一种有效的局部多序列比对算法,非常适合产生生物信息学上的有某种特定意义的比对。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 序列比对的研究背景
• 1.1.1 序列比对的生物学背景
• 1.1.2 序列比对在生物信息学中的兴起
• 1.2 序列比对的研究现状
• 1.3 本文主要工作及安排
• 第二章 生物序列比对
• 2.1 序列比对的基础知识
• 2.1.1 序列比对的相关概念
• 2.1.2 替换矩阵与空位罚分
• 2.1.3 目标函数
• 2.2 各种序列比对算法简介
• 2.2.1 动态规划简介
• 2.2.2 双序列比对
• 2.2.3 多序列比对
• 2.3 本章小结
• 第三章 基于A*算法的多序列比对
• 3.1 多序列比对问题描述和数学模型
• 3.1.1 问题描述
• 3.1.2 数学模型
• 3.2 A*方法求多序列比对
• 3.2.1 A*算法简介
• 3.2.2 预测函数h（x）的建立
• 3.2.3 边界值的计算
• 3.2.4 算法实现
• 3.3 算法和程序方面的改进
• 3.3.1 算法方面改进
• 3.3.2 程序实现上的改进
• 3.4 实验结果与分析
• 3.4.1 评价标准
• 3.4.2 实验结果和分析
• 3.5 结束语
• 第四章 斜线比对算法求解多序列比对问题
• 4.1 简介
• 4.2 两条DNA或蛋白质序列比对的算法
• 4.2.1 斜线权值的重要性
• 4.2.2 计算最大的比对
• 4.3 多序列比对
• 4.4 比对一致性
• 4.5 比对算法的优化
• 4.6 算法实现和举例
• 4.6.1 算法实现
• 4.6.2 重要步骤
• 4.7 实验结果和分析
• 4.7.1 实验结果
• 4.7.2 结果分析
• 第五章 结束语
• 致谢
• 参考文献
• 在校期间科研成果