生物序列分析中若干问题的研究

论文摘要

随着生物学中高通量的实验方法,如基因测序、DNA芯片等的使用,产生了海量的数据。如何有效地理解并利用这些数据,阐明数据当中所蕴含的生物学意义是生物信息学的主要目的。生物信息学的一个重要研究领域是对生物序列进行比对和聚类。本文就多重序列比对和蛋白质聚类方面进行了深入的探讨和研究,主要的研究内容和结果如下:1.综合研究并分析了近年来多重序列比对方法存在的问题及改进情况。多重序列比对是生物信息学的基本理论与方法之一,对结构建模,功能位点预测,进化树分析等方面起着非常关键的作用。本文综述了近年来的一些比对方法上的改进,如使用快速的方法计算序列的相似度,运用迭代优化策略和序列一致性信息等,并阐述了综合序列的结构信息和同源序列进行比对的方法。最后综述了一些对于比对质量的评估的方法和测试数据集以及比对速度的问题。2.提出了一种改进Kalign比对质量的算法。Kalign算法是一种常见的多重序列比对算法,然而由于对序列的距离估计不准导致比对的质量不高。本文提出了一种改进Kalign比对质量的算法,根据Kalign最初比对的结果,计算出新的两两序列之间的距离,然后使用UPGMA（Unweighted Pair Group Method Average,不加权成对分组平均）方法构建向导树,再进行渐进比对,产生新的比对结果。重复这一过程,直到比对的SP得分不再改变或者达到一定迭代次数为止。本文用BAliBASE 3.0对改进后的Kalign算法进行了测试,结果显示该算法较好地改进了Kalign的比对质量。3.提出了一种快速多重序列比对算法。本文使用了一种类似BLAST的算法来快速地估计序列之间的距离,并且为了能够比对大量的序列,采用了节省空间的动态规划算法来比对序列,使用ROSE程序生成的具有不同序列长度和数量的测试集。本文提出的算法在运行时间、比对质量和内存的使用上和其他常用的程序相比,算法在速度上是最快的程序之一,在比对分化大的序列时质量最好,而且使用的内存相对较少。4.提出了一种新的计算蛋白质序列相似度的算法。该算法基于相似子序列和序列的L-tuple频率,充分考虑了两个序列之间的相似子序列和非相似子序列之间的相似度,使用新近提出的一种聚类算法—仿射传播聚类（Affinity Propagation,AP）,对蛋白质序列进行聚类,并在COG、G-protein、CAZy和SCOP四个数据集上进行了测试。结果表明新的相似度度量方法能够更好地描述蛋白质序列之间的相似度,特别是对那些很难比对的序列。5.分析了使用AP算法聚类随机产生的数据集时出现的性能上的问题,并发现AP算法不能通过调整其参数preference来得到更合理的结果的问题。为了解决这个问题,本文提出了一种对AP算法的结果进行后处理的算法。这种算法使用输入相似度的中值作为preference,利用简单合并和重分配算法对聚类的结果进行重新聚类。本文将改进的算法和原始的AP算法及其他几个常用的算法在COG、SCOP和G-protein数据集上进行了比较,结果表明:在比对质量上,改进的算法比原始的AP算法提高很多,比其他的常用算法也有所提高。

论文目录

• 摘要
• ABSTRACT
• 第一章 引言
• 1.1. 生物信息学简介
• 1.1.1. 核酸序列
• 1.1.2. 蛋白质序列
• 1.2. 生物序列比对
• 1.2.1. 生物序列比对的意义
• 1.2.2. 替换矩阵
• 1.2.3. 空位罚分函数
• 1.2.4. 比对的统计学显著性
• 1.2.5. 两序列比对算法
• 1.2.5.1. 点阵分析
• 1.2.5.2. 动态规划（DP）算法
• 1.2.5.3. BLAST 算法
• 1.3. 序列聚类
• 1.3.1. 蛋白质序列聚类的意义
• 1.3.2. 蛋白质序列聚类的方法
• 1.3.2.1. Protomap
• 1.3.2.2. ProClust
• 1.3.2.3. SYSTERS
• 1.3.2.4. CLUSS
• 1.3.2.5. Spectral clustering
• 1.4. 本文的主要研究内容
• 第二章 多重序列比对
• 2.1. 引言
• 2.2. 常用算法
• 2.2.1. Clustal W
• 2.2.2. Muscle
• 2.2.3. MAFFT
• 2.2.4. POA
• 2.2.5. T-Coffee
• 2.2.6. DIALIGN
• 2.2.7. ProbCons
• 2.2.8. Kalign
• 2.3. 使用额外信息的比对算法
• 2.3.1. SPEM
• 2.3.2. Expresso
• 2.3.3. Dbclustal
• 2.3.4. PROMALS
• 2.3.5. PRALINE
• 2.4. 比对质量的评估
• 2.5. 比对的速度
• 2.6. 结论
• 第三章 基于迭代优化算法改进Kalign 比对质量
• 3.1. 算法
• 3.1.1. 相似性得分
• 3.1.2. 序列距离
• 3.1.3. 构建向导树
• 3.1.4. 迭代优化
• 3.2. 方法评估
• 3.3. 结论
• 第四章 一种快速多重序列比对算法
• 4.1. 比对算法
• 4.1.1. 距离的估计
• 4.1.2. 动态规划算法
• 4.1.3. 比对的参数
• 4.2. 测试及讨论
• 4.2.1. 运行时间
• 4.2.2. 比对质量
• 4.2.3. 内存的使用
• 4.3. 结论
• 第五章 基于新的距离度量聚类蛋白质序列
• 5.1. 距离计算方法
• 5.1.1. 距离计算方法的概述
• 5.1.2. ISMS（Improved SMS，改进的SMS）算法
• 5.2. AP 聚类算法
• 5.3. 测试数据集：
• 5.3.1. 数据集A-COG 数据库
• 5.3.2. 数据集B-G 蛋白数据库
• 5.3.3. 数据集C-CAZy 数据库
• 5.3.4. 数据集 D-SCOP 数据库
• 5.4. 聚类性能的度量
• 5.5. 测试结果及讨论
• 5.5.1. 四个数据库的测试结果
• 5.5.2. 33 个（α/β）8 barrel 蛋白测试结果
• 5.6. 结论
• 第六章 基于后处理的AP 算法聚类蛋白质序列
• 6.1. AP 算法的局限性分析
• 6.2. 基于AP 算法结果的后处理算法
• 6.3. 聚类结果分析
• 6.4. 结论
• 第七章 结论
• 7.1. 工作总结
• 7.2. 研究前景展望
• 致谢
• 参考文献
• 附录
• 1. 序列L-tuple 计数的方差的计算
• 2. 计算相似度得分的算法
• 3. AP 算法局限性的分析
• 攻博期间取得的研究成果