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

Maximum likelihood of evolutionary trees: hardness and approximation.

Benny Chor1, Tamir Tuller

  • 1School of Computer Science, Tel-Aviv University Tel-Aviv, Israel.

Bioinformatics (Oxford, England)
|June 18, 2005
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

Design of bacterial DNT sensors based on computational models.

Nucleic acids research·2026
Same author

Designing genetically stable multicopy gene constructs with the ChimeraUGEM web server.

NAR genomics and bioinformatics·2025
Same author

Yeast-derived low-purity FGF2 supports bovine ESC and MSC aggregates in suspension.

Frontiers in nutrition·2025
Same author

Silent mutations in coding regions of Hepatitis C virus affect patterns of HCV RNA structures and attenuate viral replication and pathogenesis.

Genome biology·2025
Same author

AI-directed gene fusing prolongs the evolutionary half-life of synthetic gene circuits.

Science advances·2025
Same author

The bioinformatics of the finding that the hepatitis delta virus RNA editing mechanism by a conformational switch exists in genotype 7 in addition to genotype 3.

Briefings in bioinformatics·2025

Maximum likelihood tree reconstruction remains computationally intractable, even with molecular clock assumptions or for sparse data. Approximating the ML score is also NP-hard, posing significant challenges for evolutionary biology.

Area of Science:

  • Computational Biology
  • Phylogenetics
  • Evolutionary Biology

Background:

  • Maximum Likelihood (ML) is a widely used criterion for constructing evolutionary trees.
  • The computational complexity of ML tree reconstruction was recently shown to be NP-hard.
  • This study extends previous findings on the intractability of ML tree reconstruction.

Purpose of the Study:

  • To investigate the computational complexity of Maximum Likelihood tree reconstruction under molecular clock assumptions.
  • To explore the difficulty of approximating ML scores.
  • To develop an approximation algorithm for ML reconstruction on sparse datasets.

Main Methods:

  • Proving NP-hardness for ML tree reconstruction with molecular clock.
  • Demonstrating the intractability of approximating the ML score.

Related Experiment Videos

  • Developing an approximation algorithm for sparse sequence data using parsimony algorithms.

    • Main Results:

    • ML tree reconstruction under the molecular clock assumption is NP-hard.
    • Approximating the ML score within a factor of 1.00175 is computationally intractable.
    • An algorithm is presented for approximating log-likelihood on sparse inputs, achieving similar approximation ratios to parsimony methods.

    Conclusions:

    • Maximum Likelihood tree reconstruction is computationally intractable in several important scenarios.
    • Approximation algorithms for ML on sparse data are feasible but the problem remains hard.
    • These findings highlight the computational challenges in phylogenetic inference using Maximum Likelihood.