基于三参数模型的进化树算法研究

摘要

多种生物克隆实验结果说明，存在于细胞核染色体中的DNA序列包含了该生命体的全部信息。生物序列进行序列比对后，所得结果包含了序列之间的关系和进化的信息，利用这些信息可以得到各个序列在进化过程中的亲疏、远近关系[1]。进化树就是用来描述序列间进化关系的一种树状拓扑结构。其中，树的叶子结点代表各种生物序列，树枝的长度表示生物间的进化距离。
　　构建一个可靠的进化树不仅可以推测出生物的进化过程，估计现存的各类生物间的进化关系，并且对于生物医药学、基因组学和病毒学等其他领域的研究也具有重要意义。目前常见的进化树构建方法有三类：基于距离的方法、基于特征的方法和基于概率论的方法。距离矩阵法具有较为完善的统计理论基础，算法简单，目前应用最为广泛。其中，邻接法又因其具有较小的时间复杂度，且所获得的进化树总是替代总数为最小的树而优于其他的距离矩阵算法。
　　距离矩阵的构造是距离矩阵法的基础，序列间的进化距离估计越精确，构建的进化树才会更准确。因此选择正确的进化模型来构建距离矩阵成了进化树研究的重要内容之一。UPGMA算法[2]和邻接法[3]都是传统距离矩阵法，两者都采用了Jukes-Cantor单参数模型来估算序列间的进化距离，该模型认为4种核苷酸A,T,C和G间的相互替换的速率相等。但在大多数DNA序列中，通常核苷酸转换的比率要高于颠换的比率，而且真实的核苷酸替代模型要比Jukes—Cantor单参数模型复杂得多。因此在实际应用中，用Jukes-Cantor单参数模型来估计序列间的进化距离并不理想。邻接法除了进化距离的估计影响其准确性外，它的聚类过程也是影响其准确性的一个重要方面。由进化模型估计得到距离矩阵后，邻接法对其进行聚类计算来完成进化树的构建，它要求在每一次聚类时尽量使得当前树的所有分支长度之和最小。这个聚类过程是一个贪心过程，它求得的仅是局部最优解，并非整体最优解，求得的邻居不一定是真正的邻居。也就是说邻接法所构建的进化树并不总是真实的进化树，而有可能只是真实进化树相近似的拓扑结构。
　　为提高邻接法构建进化树的准确性，本文在基于三参数模型的进化树构建算法（KTPMPT）中采用了Kimura三参数模型[4]来计算序列之间的进化距离，并给出了新的改进算法。论文中通过计算机模拟法，对KTPMPT算法、UPGMA算法和邻接法的准确性进行了对比分析，实验结果表明KTPMPT算法明显优于UPGMA算法和邻接法。在基于最小生成树的进化树构建算法（MSTPT）中，在由三参数模型得到的距离矩阵的基础上，应用Prim算法求出最小生成树，然后用这棵最小生成树来指导邻接法在建树过程中寻找最佳合并的邻居节点进行聚类。文中通过实例来说明MSTPT算法的算法过程，其计算结果与真实进化树拓扑结构完全一致，修正了邻接法生成的进化树中原有的局部拓扑错误。这可以说明MSTPT算法能够在一定程度上遏制邻接法的贪心搜索特性，构建更符合物种间进化关系的进化树。
　　本文采用三参数模型计算进化距离，提高了距离矩阵的质量，这对于高度依赖距离矩阵的算法来说是很有意义的，距离矩阵质量的提高有利于得到更准确的进化树。用最小生成树来指导邻接法的聚类建树是一个全新的尝试，在一定程度上消除了邻接法的贪婪特性，最小生成树在建树算法中的应用还有更进一步的研究空间。

目录

封面

中文摘要

英文摘要

目录

1 绪 论

1.1 研究背景

1.2 国内外研究概况

1.3 本文的主要研究工作

1.4 文章的框架结构

2 构建进化树的距离矩阵法

2.1 进化树的定义

2.2 构建进化树的步骤

2.3 计算进化距离的进化模型

2.4 构建进化树的距离矩阵法

2.5 算法分析

2.6 小结

3 基于三参数模型的进化树构建算法

3.1 邻接法非唯一性分析

3.2 算法思想

3.3 算法步骤

3.4 实例说明

3.5 算法实现

3.6 计算机模拟验证

3.7 算法分析

3.8 小结

4 基于最小生成树的进化树构建算法

4.1 邻接法贪心搜索特性分析

4.2 算法思想

4.3 算法步骤

4.4 实例说明

4.5 计算机模拟验证

4.6 算法分析

4.7 小结

5 总 结

致谢

参考文献

附 录