title: A short proof that phylogenetic tree reconstruction by maximum likelihood is hard.
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.
authors.affiliation: Department of Statistics, University of California, 367 Evans Hall, Berkeley, CA 94720-3860, USA. sroch@stat.berkeley.edu
authors.forename: Sebastien
authors.initials: S
authors.lastname: Roch
mesh_terms: D000465:Algorithms; D003198:Computer Simulation; D019143:Evolution, Molecular; D005828:Genetics, Population; D016013:Likelihood Functions; D008957:Models, Genetic; D015233:Models, Statistical; D010802:Phylogeny; D011995:Recombination, Genetic / Q000235:genetics; D017422:Sequence Analysis, DNA / Q000379:methods*