A short proof that phylogenetic tree reconstruction by maximum likelihood is hard

Author

Roch, S.

Author_Institution

Dept. of Stat., California Univ., Berkeley, CA

Volume

3

Issue

1

fYear

2006

Firstpage

92

Lastpage

94

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;

fLanguage

English

Journal_Title

Computational Biology and Bioinformatics, IEEE/ACM Transactions on

Publisher

ieee

ISSN

1545-5963

Type

jour

DOI

10.1109/TCBB.2006.4

Filename

1588849