生物多序列比对算法Kalign’s的研究分析

论文摘要

序列比对是现代生物信息学中的一个最基本的研究课题。随着生物数据库快速持续的增长,对多序列比对算法的敏感性和运算速度提出了更高的要求,开发具有高敏感性和高效率的算法成为当今研究的重点。本文对此进行了深入研究和探讨,主要研究成果如下:本文首先介绍了序列比对涉及的基本问题:空位罚分,替换矩阵和比对结果评价标准。接着对基于渐进方法构建的多序列比对算法ClustalW、T-Coffee和Muscle算法进行了深入的研究。然后通过对这些算法的分析,对Kalign算法提出了改进。Kalign是一种常见的多重序列比对算法,它使用Wu-Manber字符匹配算法来改善比对的质量和速度,对大量序列和距离较远的序列的比对有较明显的速度优势。然而由于对序列的距离估计不准导致比对的质量不高。本文提出了一种改进Kalign比对质量的算法---Kalign’s算法,根据Kalign最初比对的结果,利用新的序列距离测试方法计算出新的两两序列之间的距离,然后使用UPGMA方法构建向导树,再进行渐进比对,产生新的比对结果。重复这一过程,直到比对的SP得分不再改变或者达到一定迭代次数为止。用Balibase3.0进行测试,结果显示该算法较好的改进了Kalign的比对质量。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 生物信息学的背景及意义
• 1.2 生物信息学的研究现状
• 1.3 论文主要工作及安排
• 1.3.1 论文主要工作
• 1.3.2 论文内容具体安排
• 1.4 本章小结
• 第二章 序列比对基础
• 2.1 概论
• 2.2 空位罚分和记分矩阵
• 2.2.1 空位罚分
• 2.2.2 记分矩阵
• 2.3 目标函数
• 2.3.1 SP 目标函数
• 2.3.2 COFFEE 目标函数
• 2.4 序列比对
• 2.4.1 双序列比对
• 2.4.2 多序列比对
• 2.5 本章小结
• 第三章 生物序列比对算法研究现状
• 3.1 双序列比对
• 3.1.1 双序列比对算法数学原理
• 3.1.2 点阵图法
• 3.1.3 动态规划算法
• 3.1.4 BLAST 和FASTA 算法
• 3.2 多序列比对
• 3.2.1 多序列比对算法分析
• 3.2.2 经典多序列比对算法简介
• 3.2.3 一些其它多序列比对算法
• 3.3 本章小结
• 第四章 KALIGN’S 方法的提出与研究
• 4.1 字符串匹配原理
• 4.1.1 基本概念
• 4.1.2 字符串匹配原理
• 4.2 Wu-Manber 算法数学原理
• 4.3 KALIGN 算法
• 4.4 KALIGN 算法的改进----KALIGN’s 算法
• 4.4.1 相似性得分
• 4.4.2 序列距离
• 4.4.3 树的构造
• 4.4.4 序列加权
• 4.4.5 迭代优化
• 4.5 本章小结
• 第五章 KALIGN’s 算法比对质量的实现与评估
• 5.1 多序列比对算法评价基准数据集 BAliBASE
• 5.2 Kalign’s 算法测试结果
• 5.3 本章小结
• 第六章 结束语
• 致谢
• 参考文献
• 攻硕期间取得的研究成果