一种基于Quartet Puzzling和邻接法的进化树构建算法

摘要：

最大似然法是目前较准确的一种进化树构建方法,但是其时间复杂度非常高.在实际应用中,用分治策略实现最大似然法的Quartet Puzzling(QP)得到了人们的关注.它首先估计Quartet拓扑结构集合Q,然后利用重组技术将Q中的信息合并到一起构成一个包含所有序列的进化树.研究表明,QP的准确性不像人们所期望的那样高.如何快速有效地将Q所包含的信息融合在一起仍然是QP所面-临的一个问题.为了提高QP,结合邻接法提出一种新的进化树构建方法QPNJ.理论上,QPNJ与QP具有相同的时间复杂度.通过模拟实验将QPNJ与QP以及目前流行的进化树构建方法进行了比较.结果表明,QPNJ比QP和邻接法更准确,并且其性能不依赖于模型树的结构,从而证明了QPNJ的有效性.

关键词：进化树、最大似然法、分治算法、Quartet、Puzzling、邻接法

所属期刊栏目：45

分类号：TP391;Q811.4(计算技术、计算机技术)

资助基金：国家自然科学基金项目60741001,60871092;黑龙江省杰出青年科学基金项目JC200611;黑龙江省自然科学基金重点项目ZJG0705;哈尔滨工业大学校基金项目HIT.2003.53

在线出版日期：2009-02-18（万方平台首次上网日期，不代表论文的发表时间）

页数：共9页

页码：1965-1973