Why neighbor-joining works

2006/02/10 by Radu Mihaescu, Dan Lévy, Mihaescu, Radu +3 · 2 citations
Computer Science · Engineering · Environmental Science · #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #F.2.0 #FOS: Computer and information sciences #Multi-Agent Systems and Negotiation #Transportation and Mobility Innovations #Urban Planning and Valuation

paper · pdf · doi:10.48550/arxiv.cs/0602041

openalex publication_date 2006/02/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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.

Cited by

• On the optimality of the neighbor-joining algorithm
• A General Substitution Matrix for Structural Phylogenetics

Related

• Neighbor Joining And Leaf Status
• The Neighbor-Net Algorithm
• Neighbor joining with phylogenetic diversity estimates
• On the optimality of the neighbor-joining algorithm
• Combinatorial and computational investigations of Neighbor-Joining bias