Fast and accurate phylogeny reconstruction algorithms based on the minimum-evolution principle
Fast and accurate phylogeny reconstruction algorithms based on the minimum-evolution principle
复制标题
DOI：
10.1089/106652702761034136
复制
发表时间：
2002-01-01
影响因子：
1.7
通讯作者：
Gascuel, O
中科院分区：
文献类型：
--
作者：
Desper, R;Gascuel, O
最小进化（ME）的方法来估计遗传学已被证明是统计上一致的，当它与普通最小二乘（OLS）拟合的度量树结构。使用ME的传统方法是从给定矩阵的邻居连接（NJ）拓扑开始，然后从该起点进行拓扑搜索。第一阶段需要O（n（3））时间，其中n是分类的数量，而第二阶段的当前实现是O（pn（3））或更多，其中P是程序执行的交换次数。在本文中，我们研究了一个贪婪的方法，以最小的发展，产生一个起始拓扑在O（n（2））的时间。此外，我们还提供了一种算法，该算法使用最近邻交换（NNI）搜索最佳拓扑，其中执行p个NNI的成本为O（n（2）+ pn），即，O（n（2）），因为p总是比n小得多。贪婪最小进化（GME）算法，当与NNI组合使用时，产生的树在拓扑精度方面相当接近NJ树。我们还研究ME下的平衡加权方案，兄弟子树具有相等的权重，而不是标准的“未加权”OLS，其中所有分类群具有相同的权重，使子树的权重等于其分类群的数量。平衡最小进化方案（BME）运行速度比OLS版本慢，需要O（n（2）x diam（T））操作来构建起始树和O（pn x diam（T））来执行NNI，其中diam（T）是输出树的拓扑直径。在系统发育树上的通常的Yule-Harding分布中，直径期望是log（n），因此我们的算法在实践中比NJ更快。此外，这种BME计划产生了一个非常显着的改善NJ和其他基于距离的算法，特别是与大树，在拓扑精度方面。
The Minimum Evolution (ME) approach to phylogeny estimation has been shown to be statistically consistent when it is used in conjunction with ordinary least-squares (OLS) fitting of a metric to a tree structure. The traditional approach to using ME has been to start with the Neighbor Joining (NJ) topology for a given matrix and then do a topological search from that starting point. The first stage requires O (n(3)) time, where n is the number of taxa, while the current implementations of the second are in O (pn(3)) or more, where P is the number of swaps performed by the program. In this paper, we examine a greedy approach to minimum evolution which produces a starting topology in O (n(2)) time. Moreover, we provide an algorithm that searches for the best topology using nearest neighbor interchanges (NNIs), where the cost of doing p NNIs is O(n(2) + pn), i.e., O(n(2)) in practice because p is always much smaller than n. The Greedy Minimum Evolution (GME) algorithm, when used in combination with NNIs, produces trees which are fairly close to NJ trees in terms of topological accuracy. We also examine ME under a balanced weighting scheme, where sibling subtrees have equal weight, as opposed to the standard "unweighted" OLS, where all taxa have the same weight so that the weight of a-subtree is equal to the number of its taxa. The balanced minimum evolution scheme (BME) runs slower than the OLS version, requiring O (n(2) x diam(T)) operations to build the starting tree and O(pn x diam(T)) to perform the NNIs, where diam(T) is the topological diameter of the output tree. In the usual Yule-Harding distribution on phylogenetic trees, the diameter expectation is in log(n), so our algorithms are in practice faster that NJ. Moreover, this BME scheme yields a very significant improvement over NJ and other distance-based algorithms, especially with large trees, in terms of topological accuracy.