Jove
Visualize
Contact Us
JoVE
x logofacebook logolinkedin logoyoutube logo
ABOUT JoVE
OverviewLeadershipBlogJoVE Help Center
AUTHORS
Publishing ProcessEditorial BoardScope & PoliciesPeer ReviewFAQSubmit
LIBRARIANS
TestimonialsSubscriptionsAccessResourcesLibrary Advisory BoardFAQ
RESEARCH
JoVE JournalMethods CollectionsJoVE Encyclopedia of ExperimentsArchive
EDUCATION
JoVE CoreJoVE BusinessJoVE Science EducationJoVE Lab ManualFaculty Resource CenterFaculty Site
Terms & Conditions of Use
Privacy Policy
Policies

Related Experiment Videos

On the optimality of the neighbor-joining algorithm.

Kord Eickmeyer1, Peter Huggins, Lior Pachter

  • 1Department of Mathematics, University of California at Berkeley Berkeley, CA 94720-3840, USA. eickmeye@informatik.hu-berlin.de

Algorithms for Molecular Biology : AMB
|May 2, 2008
PubMed
Summary
This summary is machine-generated.

Related Concept Videos

You might also read

Related Articles

Articles linked to this work by shared authors, journal, and citation graph.

Sort by
Same author

TCIA Radiology Image Processing for AI and Radiomics.

medRxiv : the preprint server for health sciences·2026
Same author

Transcriptomic responses to endurance exercise training in rats.

BMC genomic data·2026
Same author

Systems genetics reveals ITIH5 as a key mediator of adipocyte-Endothelial crosstalk.

Molecular metabolism·2026
Same author

The Rayleigh Quotient and Contrastive Principal Component Analysis II.

bioRxiv : the preprint server for biology·2026
Same author

Hybrid crosses reveal a cell-type-specific landscape of mouse regulatory variation.

bioRxiv : the preprint server for biology·2026
Same author

The impact of package selection and versioning on single-cell RNA-seq analysis.

Cell systems·2026
Same journal

A k-mer-based estimator of the substitution rate between repetitive sequences.

Algorithms for molecular biology : AMB·2026
Same journal

Haplotype-aware long-read error correction.

Algorithms for molecular biology : AMB·2026
Same journal

Extension of partial atom-to-atom maps: uniqueness and algorithms.

Algorithms for molecular biology : AMB·2026
Same journal

Lossless pangenome indexing using tag arrays.

Algorithms for molecular biology : AMB·2026
Same journal

Dolphyin: a combinatorial algorithm for identifying 1-Dollo phylogenies in cancer.

Algorithms for molecular biology : AMB·2026
Same journal

Probing transcription factor subsets in gene regulatory networks.

Algorithms for molecular biology : AMB·2026
See all related articles

The neighbor-joining (NJ) algorithm is a greedy method for phylogenetic tree reconstruction. This study reveals NJ

Area of Science:

  • Phylogenetics and evolutionary biology
  • Computational biology
  • Discrete geometry and optimization

Background:

  • The neighbor-joining (NJ) algorithm is a widely used heuristic for constructing phylogenetic trees from distance data.
  • NJ aims to find the tree that minimizes the sum of branch lengths, approximating the Balanced Minimum Evolution (BME) criterion.
  • The optimality of NJ is linked to its ability to recover the true BME tree topology.

Purpose of the Study:

  • To investigate the topological optimality of the neighbor-joining algorithm in phylogenetic tree reconstruction.
  • To analyze the relationship between NJ and Balanced Minimum Evolution (BME) tree topologies using polyhedral geometry.
  • To explore the geometric properties of the spaces of dissimilarity maps for small numbers of taxa (n ≤ 8).

Main Methods:

Related Experiment Videos

  • Utilizing the connection between NJ/BME tree topologies and polyhedral subdivisions of dissimilarity map spaces.
  • Employing a combination of Monte Carlo methods and polyhedral algorithms to measure volumes of high-dimensional spherical polytopes.
  • Comparing polyhedral subdivisions for NJ and BME trees for n up to 8 taxa.

Main Results:

  • Demonstrated that distinct, unrelated tree topologies can be co-optimal under the BME criterion.
  • Showed that the regions corresponding to NJ solutions are not convex within the space of dissimilarity maps.
  • Calculated the l2 radius for the neighbor-joining algorithm for n = 5 taxa.

Conclusions:

  • The study provides geometric insights into the optimality of the neighbor-joining algorithm.
  • Conjectures that the success of NJ in recovering the BME tree depends on the diameter of the BME tree.
  • Highlights the complexity of phylogenetic tree reconstruction and the limitations of greedy algorithms like NJ.