Title :
A short proof that phylogenetic tree reconstruction by maximum likelihood is hard
Author_Institution :
Dept. of Stat., California Univ., Berkeley, CA
Abstract :
Maximum likelihood is one of the most widely used techniques to infer evolutionary histories. Although it is thought to be intractable, a proof of its hardness has been lacking. Here, we give a short proof that computing the maximum likelihood tree is NP-hard by exploiting a connection between likelihood and parsimony observed by Tuffley and Steel
Keywords :
biology computing; cellular biophysics; computational complexity; evolution (biological); genetics; maximum likelihood estimation; molecular biophysics; trees (mathematics); NP-hard; evolutionary histories; maximum likelihood; parsimony; phylogenetic tree reconstruction; Biology computing; Evolution (biology); Genetics; History; Phylogeny; Probability; Sequences; Statistics; Steel; Systematics; Analysis of algorithms and problem complexity; biology and genetics.; probability and statistics; Algorithms; Computer Simulation; Evolution, Molecular; Genetics, Population; Likelihood Functions; Models, Genetic; Models, Statistical; Phylogeny; Recombination, Genetic; Sequence Analysis, DNA;
Journal_Title :
Computational Biology and Bioinformatics, IEEE/ACM Transactions on
DOI :
10.1109/TCBB.2006.4
