Recrafting the neighbor-joining method
Recrafting the neighbor-joining method
复制标题
DOI：
10.1186/1471-2105-7-29
复制
发表时间：
2006-01-19
影响因子：
3
通讯作者：
Phillips, D
中科院分区：
文献类型：
--
作者：
Mailund, T;Brodal, GS;Phillips, D
背景：Saitou 和 Nei 提出的邻接方法是一种广泛使用的构建系统发育树的方法。该方法的公式化产生了规范 Theta(n(3)) 算法，所有现有的实现都基于该算法。结果：在本文中，我们提出了加速规范邻接方法的技术。我们的算法构建与规范邻接方法相同的系统发育树。我们算法的最佳情况运行时间是 O(n(2))，但最坏情况仍然是 O(n(3))。我们根据经验评估我们的算法在从 Pfam 比对集合中获得的距离矩阵上的性能。实验表明，我们的算法的运行时间在所检查的实例集合上随着 Theta(n(2)) 的变化而变化。我们还将运行时间与 QuickTree 工具的运行时间进行了比较，QuickTree 工具是一种广泛使用的规范邻接方法的高效实现。结论：实验表明，我们的算法对于中型实例也产生了显着的加速。
Background: The neighbor-joining method by Saitou and Nei is a widely used method for constructing phylogenetic trees. The formulation of the method gives rise to a canonical Theta(n(3)) algorithm upon which all existing implementations are based.Results: In this paper we present techniques for speeding up the canonical neighbor-joining method. Our algorithms construct the same phylogenetic trees as the canonical neighbor-joining method. The best-case running time of our algorithms are O(n(2)) but the worst-case remains O(n(3)). We empirically evaluate the performance of our algorithms on distance matrices obtained from the Pfam collection of alignments. The experiments indicate that the running time of our algorithms evolve as Theta(n(2)) on the examined instance collection. We also compare the running time with that of the QuickTree tool, a widely used efficient implementation of the canonical neighbor-joining method.Conclusion: The experiments show that our algorithms also yield a significant speed-up, already for medium sized instances.