On the optimality of the neighbor-joining algorithm

详细信息    查看全文

• 作者：Kord Eickmeyer (1)
  Peter Huggins (2)
  Lior Pachter (2)
  Ruriko Yoshida (3)
  
• 刊名：Algorithms for Molecular Biology
• 出版年：2008
• 出版时间：December 2008
• 年：2008
• 卷：3
• 期：1
• 全文大小：452KB
• 参考文献：1. Saitou N, Nei M: The neighbor joining method: a new method for reconstructing phylogenetic trees. / Mol Biol Evol 1987,4(4):406-25.
  2. Gascuel O, Steel M: Neighbor-joining revealed. / Molecular Biology and Evolution 2006,23(11):1997-000. CrossRef
  3. WHE Day: Computational complexity of inferring phylogenies from dissimilarity matrices. / Bulletin of Mathematical Biology 1987,49(4):461-67.
  4. Desper R, Gascuel O: Theoretical foundation of the balanced minimum evolution method of phylogenetic inference and its relationship to weighted least-squares tree fitting. / Mol Biol Evol 2004,21(3):587-8. CrossRef
  5. Semple C, Steel M: Cyclic permutations and evolutionary trees. / Applied Mathematics 2003, 32:669-80.
  6. Pachter L, Sturmfels B: / Algebraic Statistics for Computational Biology Cambridge University Press 2005.
  7. Bryant D: On the uniqueness of the selection criterion in neighbor-joining. / J Classif 2005, 22:3-5. CrossRef
  8. Ziegler GM: / Lectures on polytopes, Graduate Texts in Mathematics Springer-Verlag, New York 1995., 152:
  9. Schrijver A: / Theory of Linear and Integer Programming. Wiley-Interscience Series in Discrete Mathematics John Wiley & Sons Ltd., Chichester. A Wiley-Interscience Publication 1986.
  10. Semple C, Steel M: / Phylogenetics, Oxford Lecture Series in Mathematics and its Applications Oxford University Press, Oxford 2003., 24:
  11. Eickmeyer K, Yoshida R: Geometry of neighbor-joining algorithm for small trees. / Proceedings of the third international conference on Algebraic Biology 2008.
  12. Gawrilow E, Joswig M: Polymake: a framework for analyzing convex polytopes. / Polytopes -Combinatorics and Computation. Birkh?user / (Edited by: Kalai G, Ziegler GM). 2000, 43-4.
  13. Jukes TH, Cantor C: Evolution of protein molecules. / Mammalian Protein Metabolism / (Edited by: Munro HN). New York Academic Press 1969, 21-2.
  14. Matsen FA, Steel M: Phylogenetic mixtures on a single tree can mimic a tree of another topology. / Systematic Biology 2007,56(5):767-75.
  15. Atteson K: The performance of neighbor-joining methods of phylogenetic reconstruction. / Algorithmica 1999, 25:251-78. CrossRef
  16. Ota S, Li WH: NJML: A hybrid algorithm for the neighbor-joining and maximum likelihood methods. / Molecular Biology and Evolution 2000,17(9):1401-409.
  17. Sat? Q: Spherical simplicies and their polars. / Quarterly J Math 2007, 58:107-26. CrossRef
  18. Mihaescu R, Levy D, Pachter L: Why neighbor-joining works. / Algorithmica 2007, / in press.
  19. Huggins P: NJBMEVolume: Software for computing volumes. [http://bio.math.berkeley.edu/NJBME] 2008.
  20. Studier JA, Keppler KJ: A note on the neighbor-joining method of Saitou and Nei. / Mol Biol Evol 1988,5(6):729-31.
  21. Desper R, Gascuel O: Fast and accurate phylogeny reconstruction algorithms based on the minimum-evolution principle. / Journal of Computational Biology 2002, 687-05.
  22. Deshpande A, Rademacher L, Vemapla S, Wang G: Matrix approximation and projective clustering via volume sampling. / Theory of Computing 2006, 225-47.
  
• 作者单位：Kord Eickmeyer (1)
  Peter Huggins (2)
  Lior Pachter (2)
  Ruriko Yoshida (3)
  
  1. Department of Computer Science, Humboldt University, Unter den Linden 6, 10099, Berlin, Germany
  2. Department of Mathematics, University of California at Berkeley, Berkeley, CA, 94720-3840, USA
  3. Department of Statistics, University of Kentucky Lexington, KY, 40506, USA
  
• ISSN：1748-7188

文摘

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 l 2 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.