Why Neighbor-Joining Works
Why Neighbor-Joining Works
复制标题
DOI：
10.1007/s00453-007-9116-4
复制
发表时间：
2009-05-01
期刊：
影响因子：
1.1
通讯作者：
Pachter, Lior
中科院分区：
文献类型：
--
作者：
Mihaescu, Radu;Levy, Dan;Pachter, Lior
我们证明了邻居连接算法是一种健壮的四元组方法，可以从距离构造树。这导致了一种新的性能保证，它将Atteson的最优半径界作为特例，并解释了许多邻居加入成功的情况，即使在Atteson准则不满足的情况下也是如此。我们还证明了Atteson关于邻接算法的最佳边半径的猜想。我们提供的强大的性能保证也适用于二次时间快速邻居加入算法，从而为利用邻居加入推断非常大的系统进化提供了理论基础。
We show that the neighbor-joining algorithm is a robust quartet method for constructing trees from distances. This leads to a new performance guarantee that contains Atteson's optimal radius bound as a special case and explains many cases where neighbor-joining is successful even when Atteson's criterion is not satisfied. We also provide a proof for Atteson's conjecture on the optimal edge radius of the neighbor-joining algorithm. The strong performance guarantees we provide also hold for the quadratic time fast neighbor-joining algorithm, thus providing a theoretical basis for inferring very large phylogenies with neighbor-joining.