A short proof that phylogenetic tree reconstruction by maximum likelihood is hard. Roch, S. 3(1):92–94, 2006. doi abstract bibtex 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.
@Article{roch06short,
author = {Sebastien Roch},
title = {A short proof that phylogenetic tree reconstruction by maximum likelihood is hard.},
journal = TCBB,
year = {2006},
volume = {3},
number = {1},
pages = {92--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.},
doi = {10.1109/TCBB.2006.4},
keywords = {Computer Simulation; Genetics, Population; Likelihood Functions; Phylogeny; Recombination; Sequence Analysis, DNA},
owner = {Sebastian},
pmid = {17048396},
timestamp = {2006.12.29},
}