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

Fast and accurate phylogeny reconstruction algorithms based on the minimum-evolution principle.

Richard Desper1, Olivier Gascuel

  • 1National Center for Biotechnology Information, National Library of Medicine, National Institutes of Health, 45 Center Drive, Bethesda, MD 20892, USA.

Journal of Computational Biology : a Journal of Computational Molecular Cell Biology
|December 19, 2002
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

PhyloCNN: Improving Tree Representation and Neural Network Architecture for Deep Learning from Trees in Phylodynamics and Diversification Studies.

Systematic biology·2025
Same author

Accelerating Maximum Likelihood Phylogenetic Inference via Early Stopping to Evade (Over-)optimization.

Systematic biology·2025
Same author

Accounting for contact tracing in epidemiological birth-death models.

PLoS computational biology·2025
Same author

multistrap: boosting phylogenetic analyses with structural information.

Nature communications·2025
Same author

The Bayesian Phylogenetic Bootstrap and its Application to Short Trees and Branches.

Molecular biology and evolution·2024
Same author

Integrating Contact Tracing Data to Enhance Outbreak Phylodynamic Inference: A Deep Learning Approach.

Molecular biology and evolution·2024

A new Greedy Minimum Evolution (GME) algorithm offers faster phylogeny estimation than traditional methods. This approach, especially with balanced weighting, significantly improves topological accuracy for large phylogenetic trees.

Area of Science:

  • Computational Biology
  • Phylogenetics
  • Bioinformatics

Background:

  • The Minimum Evolution (ME) approach is a statistically consistent method for phylogeny estimation when combined with ordinary least-squares (OLS) fitting.
  • Traditional ME methods often start with Neighbor Joining (NJ) and involve computationally intensive topological searches (O(n^3) or higher).
  • Existing methods face challenges with scalability and efficiency for large datasets.

Purpose of the Study:

  • To develop a more efficient greedy approach to Minimum Evolution (ME) for faster phylogeny estimation.
  • To introduce and evaluate a balanced weighting scheme (BME) for ME, aiming for improved topological accuracy.
  • To compare the performance and accuracy of the new algorithms against existing methods like NJ.

Main Methods:

Related Experiment Videos

  • Developed a greedy algorithm for ME that generates an initial topology in O(n^2) time.
  • Implemented a nearest neighbor interchange (NNI) search algorithm with a practical time complexity of O(n^2) for topological refinement.
  • Introduced and analyzed a balanced minimum evolution (BME) scheme with a complexity of O(n^2 * diam(T)) for tree building and O(pn * diam(T)) for NNIs.

Main Results:

  • The Greedy Minimum Evolution (GME) algorithm produces starting topologies comparable in accuracy to NJ trees.
  • The GME algorithm combined with NNIs offers a significant speed improvement over traditional ME methods.
  • The Balanced Minimum Evolution (BME) scheme demonstrates substantial improvements in topological accuracy, particularly for large phylogenetic trees, outperforming NJ and other distance-based methods.

Conclusions:

  • The developed greedy approach provides a computationally efficient alternative for ME-based phylogeny estimation.
  • The balanced weighting scheme in ME significantly enhances the accuracy of phylogenetic tree reconstruction, especially for large datasets.
  • These advancements offer practical benefits for large-scale phylogenetic analyses in bioinformatics and computational biology.