高级检索

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

    An Evolutionary Tree Reconstruction Method Combining Quartet Puzzling and Neighbor Joining

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

       

      Abstract: Evolutionary tree reconstruction is a very important topic in biology. A reliable evolutionary tree has many important applications in medical and biological research, such as drug discovery and conservation biology. A rich variety of tree reconstruction methods have been developed, which fall into three categories: 1) maximum parsimony methods, 2) distance based methods, and 3) approaches applying the maximum likelihood principle. Maximum likelihood programs can recover the correct tree more frequently than other methods. But, inference of evolutionary trees using the maximum likelihood principle is NP-hard. The reconstruction method quartet puzzling(QP) is currently receiving considerable attention. QP is a divide-and-conquer approach to the maximum likelihood problem. QP works by estimating the set Q of quartet topologies, then combining the information in Q into an evolutionary tree on the whole set by some recombination technique. However, it is demonstrated that current performance of QP is far from satisfactory as expected. How to reconcile the different topologies of the quartets into one tree is still a major problem faced by QP. In order to improve QP, a new method named QPNJ is proposed, which has the same computational complexity as QP. Experiments with simulated datasets show that QPNJ is more accurate than others. Moreover, unlike QP, QPNJ is less dependent on the shape of the correct tree.

       

    /

    返回文章
    返回