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

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},
}

Downloads: 0