{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T19:26:09Z","timestamp":1781119569756,"version":"3.54.1"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"1","content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithms Mol Biol"],"published-print":{"date-parts":[[2008,12]]},"abstract":"Abstract<\/jats:title>\n 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 \n \n \n \n \n R<\/mml:mi>\n +<\/mml:mo>\n \n \n (<\/mml:mo>\n \n \n \n \n n<\/mml:mi>\n <\/mml:mtd>\n <\/mml:mtr>\n \n \n 2<\/mml:mn>\n <\/mml:mtd>\n <\/mml:mtr>\n <\/mml:mtable>\n <\/mml:mrow>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:msubsup>\n <\/mml:mrow>\n MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacPC6xNi=xH8viVGI8Gi=hEeeu0xXdbba9frFj0xb9qqpG0dXdb9aspeI8k8fiI+fsY=rqGqVepae9pg0db9vqaiVgFr0xfr=xfr=xc9adbaqaaeGaciGaaiaabeqaaeqabiWaaaGcbaWenfgDOvwBHrxAJfwnHbqeg0uy0HwzTfgDPnwy1aaceaGae83gHi1aa0baaSqaaiabgUcaRaqaamaabmaabaqbaeqabiqaaaqaaiabd6gaUbqaaiabikdaYaaaaiaawIcacaGLPaaaaaaaaa@3BA1@<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/jats:inline-formula> to study the optimality of the neighbor-joining algorithm. In particular, we investigate and compare the polyhedral subdivisions for n<\/jats:italic> \u2264 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<\/jats:italic>\n 2<\/jats:sub> radius for neighbor-joining for n<\/jats:italic> = 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.<\/jats:p>","DOI":"10.1186\/1748-7188-3-5","type":"journal-article","created":{"date-parts":[[2008,4,30]],"date-time":"2008-04-30T18:14:29Z","timestamp":1209579269000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":34,"title":["On the optimality of the neighbor-joining algorithm"],"prefix":"10.1186","volume":"3","author":[{"given":"Kord","family":"Eickmeyer","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Peter","family":"Huggins","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lior","family":"Pachter","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ruriko","family":"Yoshida","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2008,4,30]]},"reference":[{"issue":"4","key":"46_CR1","first-page":"406","volume":"4","author":"N Saitou","year":"1987","unstructured":"Saitou N, Nei M: The neighbor joining method: a new method for reconstructing phylogenetic trees. Mol Biol Evol. 1987, 4 (4): 406-425.","journal-title":"Mol Biol Evol"},{"issue":"11","key":"46_CR2","doi-asserted-by":"publisher","first-page":"1997","DOI":"10.1093\/molbev\/msl072","volume":"23","author":"O Gascuel","year":"2006","unstructured":"Gascuel O, Steel M: Neighbor-joining revealed. Molecular Biology and Evolution. 2006, 23 (11): 1997-2000.","journal-title":"Molecular Biology and Evolution"},{"issue":"4","key":"46_CR3","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1007\/BF02458863","volume":"49","author":"WHE Day","year":"1987","unstructured":"WHE Day: Computational complexity of inferring phylogenies from dissimilarity matrices. Bulletin of Mathematical Biology. 1987, 49 (4): 461-467.","journal-title":"Bulletin of Mathematical Biology"},{"issue":"3","key":"46_CR4","doi-asserted-by":"publisher","first-page":"587","DOI":"10.1093\/molbev\/msh049","volume":"21","author":"R Desper","year":"2004","unstructured":"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-98.","journal-title":"Mol Biol Evol"},{"key":"46_CR5","first-page":"669","volume":"32","author":"C Semple","year":"2003","unstructured":"Semple C, Steel M: Cyclic permutations and evolutionary trees. Applied Mathematics. 2003, 32: 669-680.","journal-title":"Applied Mathematics"},{"key":"46_CR6","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511610684","volume-title":"Algebraic Statistics for Computational Biology","author":"L Pachter","year":"2005","unstructured":"Pachter L, Sturmfels B: Algebraic Statistics for Computational Biology. 2005, Cambridge University Press"},{"key":"46_CR7","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/s00357-005-0003-x","volume":"22","author":"D Bryant","year":"2005","unstructured":"Bryant D: On the uniqueness of the selection criterion in neighbor-joining. J Classif. 2005, 22: 3-15. 10.1007\/s00357-005-0003-x.","journal-title":"J Classif"},{"key":"46_CR8","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-8431-1","volume-title":"Lectures on polytopes, Graduate Texts in Mathematics","author":"GM Ziegler","year":"1995","unstructured":"Ziegler GM: Lectures on polytopes, Graduate Texts in Mathematics. 1995, 152: Springer-Verlag, New York"},{"key":"46_CR9","volume-title":"Theory of Linear and Integer Programming. Wiley-Interscience Series in Discrete Mathematics","author":"A Schrijver","year":"1986","unstructured":"Schrijver A: Theory of Linear and Integer Programming. Wiley-Interscience Series in Discrete Mathematics. 1986, John Wiley & Sons Ltd., Chichester. A Wiley-Interscience Publication"},{"key":"46_CR10","volume-title":"Phylogenetics, Oxford Lecture Series in Mathematics and its Applications","author":"C Semple","year":"2003","unstructured":"Semple C, Steel M: Phylogenetics, Oxford Lecture Series in Mathematics and its Applications. 2003, 24: Oxford University Press, Oxford"},{"key":"46_CR11","volume-title":"Proceedings of the third international conference on Algebraic Biology","author":"K Eickmeyer","year":"2008","unstructured":"Eickmeyer K, Yoshida R: Geometry of neighbor-joining algorithm for small trees. Proceedings of the third international conference on Algebraic Biology. 2008"},{"key":"46_CR12","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1007\/978-3-0348-8438-9_2","volume-title":"Polytopes \u2013 Combinatorics and Computation. Birkh\u00e4user","author":"E Gawrilow","year":"2000","unstructured":"Gawrilow E, Joswig M: Polymake: a framework for analyzing convex polytopes. Polytopes \u2013 Combinatorics and Computation. Birkh\u00e4user. Edited by: Kalai G, Ziegler GM. 2000, 43-74."},{"key":"46_CR13","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/B978-1-4832-3211-9.50009-7","volume-title":"Mammalian Protein Metabolism","author":"TH Jukes","year":"1969","unstructured":"Jukes TH, Cantor C: Evolution of protein molecules. Mammalian Protein Metabolism. Edited by: Munro HN. 1969, 21-32. New York Academic Press"},{"issue":"5","key":"46_CR14","doi-asserted-by":"publisher","first-page":"767","DOI":"10.1080\/10635150701627304","volume":"56","author":"FA Matsen","year":"2007","unstructured":"Matsen FA, Steel M: Phylogenetic mixtures on a single tree can mimic a tree of another topology. Systematic Biology. 2007, 56 (5): 767-775.","journal-title":"Systematic Biology"},{"key":"46_CR15","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1007\/PL00008277","volume":"25","author":"K Atteson","year":"1999","unstructured":"Atteson K: The performance of neighbor-joining methods of phylogenetic reconstruction. Algorithmica. 1999, 25: 251-278. 10.1007\/PL00008277.","journal-title":"Algorithmica"},{"issue":"9","key":"46_CR16","doi-asserted-by":"publisher","first-page":"1401","DOI":"10.1093\/oxfordjournals.molbev.a026423","volume":"17","author":"S Ota","year":"2000","unstructured":"Ota S, Li WH: NJML: A hybrid algorithm for the neighbor-joining and maximum likelihood methods. Molecular Biology and Evolution. 2000, 17 (9): 1401-1409.","journal-title":"Molecular Biology and Evolution"},{"key":"46_CR17","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1093\/qmath\/hal008","volume":"58","author":"Q Sat\u00f4","year":"2007","unstructured":"Sat\u00f4 Q: Spherical simplicies and their polars. Quarterly J Math. 2007, 58: 107-126. 10.1093\/qmath\/hal008.","journal-title":"Quarterly J Math"},{"key":"46_CR18","volume-title":"Algorithmica","author":"R Mihaescu","year":"2007","unstructured":"Mihaescu R, Levy D, Pachter L: Why neighbor-joining works. Algorithmica. 2007"},{"key":"46_CR19","volume-title":"NJBMEVolume: Software for computing volumes","author":"P Huggins","year":"2008","unstructured":"Huggins P: NJBMEVolume: Software for computing volumes. 2008, http:\/\/bio.math.berkeley.edu\/NJBME"},{"issue":"6","key":"46_CR20","first-page":"729","volume":"5","author":"JA Studier","year":"1988","unstructured":"Studier JA, Keppler KJ: A note on the neighbor-joining method of Saitou and Nei. Mol Biol Evol. 1988, 5 (6): 729-731.","journal-title":"Mol Biol Evol"},{"key":"46_CR21","first-page":"687","volume-title":"Journal of Computational Biology","author":"R Desper","year":"2002","unstructured":"Desper R, Gascuel O: Fast and accurate phylogeny reconstruction algorithms based on the minimum-evolution principle. Journal of Computational Biology. 2002, 687-705."},{"key":"46_CR22","first-page":"225","volume-title":"Theory of Computing","author":"A Deshpande","year":"2006","unstructured":"Deshpande A, Rademacher L, Vemapla S, Wang G: Matrix approximation and projective clustering via volume sampling. Theory of Computing. 2006, 225-247."}],"container-title":["Algorithms for Molecular Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/1748-7188-3-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,8,31]],"date-time":"2021-08-31T21:35:56Z","timestamp":1630445756000},"score":1,"resource":{"primary":{"URL":"https:\/\/almob.biomedcentral.com\/articles\/10.1186\/1748-7188-3-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,4,30]]},"references-count":22,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2008,12]]}},"alternative-id":["46"],"URL":"https:\/\/doi.org\/10.1186\/1748-7188-3-5","relation":{},"ISSN":["1748-7188"],"issn-type":[{"value":"1748-7188","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,4,30]]},"assertion":[{"value":"13 November 2007","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 April 2008","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 April 2008","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"5"}}