Related Experiment Videos
Ancestral maximum likelihood of evolutionary trees is hard.
Louigi Addario-Berry1, Benny Chor, Mike Hallett
1School of Computer Science, McGill University, Montreal, Quebec, Canada. laddar@cs.mcgill.ca
Journal of Bioinformatics and Computational Biology
|August 7, 2004
Summary
Maximum Likelihood (ML) tree selection is computationally intensive. This study proves Ancestral Maximum Likelihood (AML) is NP-complete, a significant step in understanding ML
Area of Science:
- Computational Biology
- Phylogenetics
- Evolutionary Biology
Background:
- Maximum Likelihood (ML) is a popular criterion for selecting evolutionary trees.
- ML tree inference is computationally challenging, with algorithms often slower than Maximum Parsimony (MP).
- While MP is NP-complete, ML's computational hardness has remained unproven.
Purpose of the Study:
- To investigate the computational complexity of Maximum Likelihood in phylogenetics.
- To provide a hardness result for ML tree selection.
- To prove that Ancestral Maximum Likelihood (AML) is NP-complete.
Main Methods:
- Utilized a reduction from the Vertex Cover problem, similar to proofs for MP.
- Developed a novel and complex proof of correctness for the reduction in the context of AML.
- Focused on finding an optimal tree and ancestral sequence assignments to maximize likelihood.
Main Results:
- Demonstrated that Ancestral Maximum Likelihood (AML) is an NP-complete problem.
- Established a formal computational hardness result for a key aspect of ML tree selection.
- The proof of correctness for the Vertex Cover reduction to AML is substantially more involved than for MP.
Conclusions:
- The NP-completeness of AML signifies a significant advancement in understanding the computational complexity of ML phylogenetics.
- This finding contributes to the theoretical foundation of evolutionary tree selection methods.
- Further research may explore other ML-related problems and their computational complexity.