CaltechAUTHORS
  A Caltech Library Service

Why neighbor-joining works

Mihaescu, Radu and Levy, Dan and Pachter, Lior (2009) Why neighbor-joining works. Algorithmica, 54 (1). pp. 1-24. ISSN 0178-4617. doi:10.1007/s00453-007-9116-4. https://resolver.caltech.edu/CaltechAUTHORS:20170307-094400293

[img] PDF - Submitted Version
See Usage Policy.

477kB

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20170307-094400293

Abstract

We show that the neighbor-joining algorithm is a robust quartet method for constructing trees from distances. This leads to a new performance guarantee that contains Atteson's optimal radius bound as a special case and explains many cases where neighbor-joining is successful even when Atteson's criterion is not satisfied. We also provide a proof for Atteson's conjecture on the optimal edge radius of the neighbor-joining algorithm. The strong performance guarantees we provide also hold for the quadratic time fast neighbor-joining algorithm, thus providing a theoretical basis for inferring very large phylogenies with neighbor-joining.


Item Type:Article
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.1007/s00453-007-9116-4DOIArticle
https://link.springer.com/article/10.1007%2Fs00453-007-9116-4PublisherArticle
https://arxiv.org/abs/cs/0602041arXivDiscussion Paper
http://rdcu.be/pSO6PublisherFree ReadCube access
ORCID:
AuthorORCID
Pachter, Lior0000-0002-9164-6231
Additional Information:© 2007 Springer Science+Business Media, LLC. Received: 25 December 2006 / Accepted: 15 October 2007 / Published online: 4 December 2007. Radu Mihaescu was supported by a National Science Foundation graduate fellowship, and partially by the Fannie and John Hertz Foundation. Lior Pachter was partially supported by NIH grant R01HG2362 and NSF grant CCF0347992. Dan Levy was supported by NIH grant GM68423.
Funders:
Funding AgencyGrant Number
NSF Graduate Research FellowshipUNSPECIFIED
Fannie and John Hertz FoundationUNSPECIFIED
NIHR01HG2362
NSFCCF-0347992
NIHGM68423
Subject Keywords:Distance methods; Edge radius; Neighbor-joining; Quartets
Issue or Number:1
DOI:10.1007/s00453-007-9116-4
Record Number:CaltechAUTHORS:20170307-094400293
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20170307-094400293
Official Citation:Mihaescu, R., Levy, D. & Pachter, L. Algorithmica (2009) 54: 1. doi:10.1007/s00453-007-9116-4
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:74834
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:07 Mar 2017 17:47
Last Modified:11 Nov 2021 05:30

Repository Staff Only: item control page