On the optimality of the neighbor-joining algorithm.
On the optimality of the neighbor-joining algorithm.
复制标题
关于邻居加入算法的最佳性。
DOI：
10.1186/1748-7188-3-5
复制
发表时间：
2008-04-30
影响因子：
1
通讯作者：
Yoshida, Ruriko
中科院分区：
文献类型：
--
作者：
Eickmeyer, Kord;Huggins, Peter;Pachter, Lior;Yoshida, Ruriko
在系统发育学中流行的邻居连接(NJ)算法是一种贪婪算法，用于寻找与相异地图相关联的平衡最小进化树(BME)。从这个角度来看，当算法输出最小化平衡最小进化准则的树时，NJ是最优的。我们利用NJ树拓扑和BME树拓扑由相异映射空间的多面体细分来确定的事实来研究邻接连接算法的最优性。特别是，我们研究和比较了n≤8的多面体细分。这需要测量高维球形多面体的体积，这是我们使用蒙特卡罗方法和多面体算法的组合得到的。我们的结果包括一个证明，在BME重建中高度不相关的树可以是共同最优的，并且NJ区域不是凸的。我们得到了n=5时邻居加入算法的L2半径，并推测邻居加入算法恢复BME树的能力依赖于BME树的直径。
The popular neighbor-joining (NJ) algorithm used in phylogenetics is a greedy algorithm for finding the balanced minimum evolution (BME) tree associated to a dissimilarity map. From this point of view, NJ is "optimal" when the algorithm outputs the tree which minimizes the balanced minimum evolution criterion. We use the fact that the NJ tree topology and the BME tree topology are determined by polyhedral subdivisions of the spaces of dissimilarity maps to study the optimality of the neighbor-joining algorithm. In particular, we investigate and compare the polyhedral subdivisions for n ≤ 8. This requires the measurement of volumes of spherical polytopes in high dimension, which we obtain using a combination of Monte Carlo methods and polyhedral algorithms. Our results include a demonstration that highly unrelated trees can be co-optimal in BME reconstruction, and that NJ regions are not convex. We obtain the l2 radius for neighbor-joining for n = 5 and we conjecture that the ability of the neighbor-joining algorithm to recover the BME tree depends on the diameter of the BME tree.
登录
查看更多内容
影响因子：
1.1
作者：
Atteson, K
通讯作者：
Atteson, K
影响因子：
6.5
作者：
Matsen, Frederick A.;Steel, Mike
通讯作者：
Steel, Mike
影响因子：
10.7
作者：
Desper, R;Gascuel, O
通讯作者：
Gascuel, O
影响因子：
10.7
作者：
SAITOU, N;NEI, M
通讯作者：
NEI, M
影响因子：
10.7
作者：
Ota, S;Li, WH
通讯作者：
Li, WH