{"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":1781119569782,"version":"3.54.1"},"reference-count":12,"publisher":"Springer Science and Business Media LLC","issue":"1","content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Bioinformatics"],"published-print":{"date-parts":[[2006,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:sec><jats:title>Background<\/jats:title><jats:p>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 \u0398(<jats:italic>n<\/jats:italic><jats:sup>3<\/jats:sup>) algorithm upon which all existing implementations are based.<\/jats:p><\/jats:sec><jats:sec><jats:title>Results<\/jats:title><jats:p>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<jats:italic>O<\/jats:italic>(<jats:italic>n<\/jats:italic><jats:sup>2<\/jats:sup>) but the worst-case remains<jats:italic>O<\/jats:italic>(<jats:italic>n<\/jats:italic><jats:sup>3<\/jats:sup>). We empirically evaluate the performance of our algoritms on distance matrices obtained from the Pfam collection of alignments. The experiments indicate that the running time of our algorithms evolve as \u0398(<jats:italic>n<\/jats:italic><jats:sup>2<\/jats:sup>) 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.<\/jats:p><\/jats:sec><jats:sec><jats:title>Conclusion<\/jats:title><jats:p>The experiments show that our algorithms also yield a significant speed-up, already for medium sized instances.<\/jats:p><\/jats:sec>","DOI":"10.1186\/1471-2105-7-29","type":"journal-article","created":{"date-parts":[[2006,1,23]],"date-time":"2006-01-23T13:04:29Z","timestamp":1138021469000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":45,"title":["Recrafting the neighbor-joining method"],"prefix":"10.1186","volume":"7","author":[{"given":"Thomas","family":"Mailund","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Gerth S","family":"Brodal","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rolf","family":"Fagerberg","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Christian NS","family":"Pedersen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Derek","family":"Phillips","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2006,1,19]]},"reference":[{"issue":"4","key":"768_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\u2013425.","journal-title":"Mol Biol Evol"},{"issue":"6","key":"768_CR2","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\u2013731.","journal-title":"Mol Biol Evol"},{"key":"768_CR3","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1016\/S0196-6774(03)00049-X","volume":"48","author":"K St John","year":"2003","unstructured":"St John K, Warnow T, Moret B, Vawter L: Performance Study of Phylogenetic Methods: (Unweighted) Quartet Methods and Neighbor-Joining. J Algorithms 2003, 48: 173\u2013193. [(Special issue on best papers from SODA'01.)]. 10.1016\/S0196-6774(03)00049-X","journal-title":"J Algorithms"},{"key":"768_CR4","volume-title":"Silico Biology","author":"G Fuellen","year":"2003","unstructured":"Fuellen G, Spitzer M, Cullen P, Lorkowski S: BLASTing Proteomes, Yielding Phylogenies. Silico Biology 2003., 3: [To appear.]."},{"issue":"6","key":"768_CR5","first-page":"961","volume":"11","author":"O Gascuel","year":"1994","unstructured":"Gascuel O: A note on Sattath and Tversky's, Saitou and Nei's, and Studier and Keppler's algorithms for inferring phylogenies from evolutionary distances. Mol Biol Evol 1994, 11(6):961\u2013963.","journal-title":"Mol Biol Evol"},{"key":"768_CR6","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1093\/oso\/9780195135848.001.0001","volume-title":"Molecular Evolution and Phylogenetics","author":"N Nei","year":"2000","unstructured":"Nei N, Kumar S: Molecular Evolution and Phylogenetics. Volume chap 6.4. Oxford University Press; 2000:103\u2013110."},{"key":"768_CR7","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1016\/S0076-6879(96)66027-3","volume":"266","author":"N Saitou","year":"1996","unstructured":"Saitou N: Reconstruction of Gene Trees from Sequence Data. Methods in Enzymology 1996, 266: 427\u2013448.","journal-title":"Methods in Enzymology"},{"key":"768_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF00288933","volume":"4","author":"RA Finkel","year":"1974","unstructured":"Finkel RA, Bentley JL: Quad Trees: A Data Structure for Retrieval by Composite Key. Acta Informatica 1974, 4: 1\u20139. 10.1007\/BF00288933","journal-title":"Acta Informatica"},{"key":"768_CR9","doi-asserted-by":"publisher","first-page":"276","DOI":"10.1093\/nar\/30.1.276","volume":"30","author":"A Bateman","year":"2002","unstructured":"Bateman A, Birney E, Cerruti L, Durbin R, Etwiller L, Eddy S, Griffiths-Jones S, Howe K, Marshall M, Sonnhammer E: The Pfam Protein Families Database. Nucleic Acids Res 2002, 30: 276\u2013280. 10.1093\/nar\/30.1.276","journal-title":"Nucleic Acids Res"},{"key":"768_CR10","unstructured":"Pfam: Protein Families Database of Alignments and HMMs[http:\/\/www.sanger.ac.uk\/Software\/Pfam\/]"},{"issue":"11","key":"768_CR11","doi-asserted-by":"publisher","first-page":"1546","DOI":"10.1093\/bioinformatics\/18.11.1546","volume":"18","author":"K Howe","year":"2002","unstructured":"Howe K, Bateman A, Durbin R: QuickTree: Building Huge Neighbour-Joining Trees of Protein Sequences. Bioinformatics 2002, 18(11):1546\u20131547. 10.1093\/bioinformatics\/18.11.1546","journal-title":"Bioinformatics"},{"key":"768_CR12","unstructured":"QuickJoin[http:\/\/www.birc.dk\/Software\/QuickJoin\/index.html]"}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/1471-2105-7-29.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,2]],"date-time":"2024-02-02T11:44:15Z","timestamp":1706874255000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/1471-2105-7-29"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,1,19]]},"references-count":12,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2006,12]]}},"alternative-id":["768"],"URL":"https:\/\/doi.org\/10.1186\/1471-2105-7-29","relation":{},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,1,19]]},"assertion":[{"value":"29 April 2005","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 January 2006","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 January 2006","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"29"}}