基于DNA序列的进化树构建算法的研究

论文摘要

进化树又称为系统发生树,是一种用来描述各种生命实体之间进化关系的树型结构。一个可靠的进化树推断不仅有助于了解生物的进化历史和进化机制,而且对生物医药学、计算分子生物学其他分支的研究具有重要意义。目前常见的进化树构建方法有距离法、最大简约法和最大似然法三种。其中,最大似然法被认为比其他两种方法更为准确,但是其计算复杂度非常高。为了提高最大似然法,本文从以下4个方面展开了深入研究:（1）提出了一个快速高效的分支交换操作由于计算复杂度非常高,实际应用中的最大似然法都是基于启发式的。虽然不同的启发式算法具有不同的搜索策略,但是其基本思路都是通过一系列的分支交换操作来提高起始进化树。并且,启发式算法的性能在一定程度上取决于其所采用的分支交换操作的搜索能力。目前常见的分支交换操作有NNI（Nearest Neighbor Interchange） , SPR（Subtree Prune and Regraft）和TBR（Tree Bisection and Reconnection）,其中TBR的搜索空间最广。但研究表明,TBR的搜索空间还不够广,容易陷入局部极优。另一种分支交换操作p-ECR （p-Edge Contraction and Refinement）具有更广的搜索空间,能够在一定程度上避免局部极优。但是由于计算复杂度非常高,p-ECR很少被使用。本文结合邻接法和p-ECR提出了一个分支交换操作p-ECRNJ。p-ECRNJ的基本思想是利用邻接法分解p-ECR中产生的未分解节点。这样,每一次p-ECRNJ操作只需要O（p3）去分解未分解节点,而无须花费大量的时间去尝试所有的可能（最多（2p+1）!!）,从而大大降低了时间复杂度。对12组真实数据的测试结果表明基于p-ECRNJ的进化树构建算法能够在合理的时间内找到比其他流行的算法更好的进化树。并且,p-ECRNJ还可以有效地提高其他分支交换操作,如NNI。从而,证明了p-ECRNJ的有效性。（2）提出了一种PSO的进化树构建算法爬山算法在进化树重构中得到了广泛应用并取得了一定的成功。但是由于进化树的似然函数通常含有多个局部极优解,而爬山算法没有逃离局部极优的能力,因此基于爬山算法的进化树构建算法很容易陷入局部极优。从本质上讲,粒子群优化算法（Particle Swarm Optimization,简称PSO）是一种并行的、动态的爬山算法,具有一定的逃离局部极优的能力。本文提出了一个基于PSO的进化树构建算法PSOML。该算法采用PSO的基本框架,利用p-ECRNJ完成粒子状态的更新,其中p值是根据粒子的速度确定的。对真实数据的测试结果表明虽然要花费较长的时间,PSOML的准确性要明显优于基于爬山算法的PHYML和RAxML。并且,PSOML可以在合理的时间内找到比基于遗传算法GARLI更好的进化树。（3）结合Quartet puzzling和邻接法提出了一种进化树构建方法由于最大似然法的时间复杂度非常高,基于分治思想的最大似然法——quartet方法得到了人们的关注。最流行的quartet方法是Quartet Puzzling（简称QP）。它首先利用最大似然法估计quartet拓扑结构集合Q,然后利用一个贪心算法将Q进行重组构成一个包含所有序列的进化树。研究表明,QP的准确性不够高,甚至比邻接法还要低。如何快速有效地将Q进行重组是QP所面临的一个难题。另一方面,邻接法具有很好的理论特性,但其准确性取决于作为输入的距离矩阵的质量。长分支一直是困扰邻接法的一个问题。本文结合邻接法和QP提出了一个进化树构建算法QPNJ。QPNJ的基本思想是首先用最大似然法估计quartet拓扑结构集合Q,然后根据Q估计序列之间的进化距离,构成距离矩阵M,最后利用邻接法根据M构建进化树。QP和邻接法的这种结合会达到取长补短的效果。一方面利用更有理论依据的邻接法完成Q的重组可以提高QP的准确性,另一方面利用quartet估计序列之间的进化距离可以在一定程度上避免邻接法所面临的长分支问题。理论上,QPNJ与QP具有相同的时间复杂度。需要指出的是,邻接法和QP的结合不是唯一的,任意类似于邻接法的聚类过程如Weightor都可以按照QPNJ的思想代替邻接法与QP相结合。模拟实验表明,QPNJ和QPWNJ（结合了Weightor与QP）比QP更加准确,甚至比邻接法和Weightor还准确。并且,QPNJ和QPWNJ的准确性不像QP一样依赖于模型树的结构。从而证明了QP与聚类算法如邻接法和Weighbor的结合是有效的。（4）结合同伦方法和SEM提出了一种进化树构建算法根据当前物种构建进化树是一个典型的从非完全数据学习的问题。结构期望最大化（Structural Expectation Maximization,简称SEM）算法是一个根据不完全数据求解模型结构的有效方法,它通过迭代交替搜索的简单方式能够简化最大似然估计问题。但是,由于SEM算法直接采用贝叶斯公式计算隐变量的条件概率,使得每次迭代的结果都是上次迭代中期望似然值的最优解,因此算法对于初始点的选择具有很强的依赖性。尤其是进化树的似然函数往往具有多个局部极优解,所以直接利用SEM构建进化树很容易陷入局部极优。同伦方法是一个全局方法,其基本思想是构造一个同伦函数将一个已知解的问题与待解问题联系起来,然后从已知解的问题开始,利用同伦参数的变化,最终求得待解问题的最优解。本文结合同伦方法和SEM提出了一种进化树构建算法HSEMPHY。HSEMPHY首先利用最大熵原理计算隐变量的条件概率,引入同伦参数β,然后借鉴同伦方法的过程优化似然函数。对真实数据的测试结果表明HSEMPHY与目前两个流行的进化树构建算法PHYML和RAxML性能相当,并且对初始点具有较低的敏感性。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 课题背景
• 1.2 进化树
• 1.3 分子数据
• 1.4 DNA 进化及进化模型
• 1.4.1 基本假设
• 1.4.2 常见的进化模型
• 1.5 国内外研究现状及分析
• 1.5.1 距离法
• 1.5.2 最大简约法
• 1.5.3 最大似然法
• 1.5.4 算法比较
• 1.6 本文主要工作
• 1.6.1 研究内容
• 1.6.2 研究成果
• 第2章 基于邻接法的p-ECR 分支交换操作
• 2.1 引言
• 2.2 NNI、SPR、TBR 和p-ECR 搜索能力分析
• 2.3 p-ECRNJ 操作
• 2.4 实验与讨论
• 2.4.1 实验数据
• 2.4.2 实验结果
• 2.5 本章小节
• 第3章 一种基于 PSO 的进化树构建算法
• 3.1 引言
• 3.2 粒子群优化算法
• 3.2.1 原理
• 3.2.2 特点
• 3.2.3 应用
• 3.3 基于PSO 的进化树构建算法
• 3.4 实验和讨论
• 2.4.1 参数影响
• 2.4.2 与其他算法比较
• 3.5 本章小结
• 第4章 一种结合QP 和邻接法的进化树构建算法
• 4.1 引言
• 4.2 QP 和邻接法的性能分析
• 4.2.1 QP 性能分析
• 4.2.2 邻接法性能分析
• 4.3 QPNJ
• 4.4 实验和讨论
• 4.5 本章小结
• 第5章 结合同伦方法和 SEM 的进化树构建算法
• 5.1 引言
• 5.2 最大似然法和SEM 算法
• 5.3 基于同伦方法的 SEM 算法
• 5.3.1 算法推导
• 5.3.2 收敛性证明
• 5.4 基于HSEM 的进化树构建算法
• 5.5 实验和讨论
• 5.5.1 与SEMPHY 比较
• 5.5.2 与其他算法比较
• 5.6 本章小结
• 第6章 实例分析
• 6.1 引言
• 6.2 进化关系分析
• 6.2.1 30 种昆虫的进化关系分析
• 6.2.2 16 种灵长类动物的进化关系分析
• 6.2.3 13 种猫科动物的进化关系分析
• 6.3 本章小结
• 结 论
• 参考文献
• 攻读学位期间发表的学术论文
• 致谢
• 个人简历