Approximate maximum parsimony and ancestral maximum likelihood

Noga Alon, Benny Chor, Fabio Pardi, Anat Rapoport

Research output: Contribution to journalArticle

9 Scopus citations

Abstract

We explore the maximum parsimony (MP) and ancestral maximum likelihood (AML) criteria in phylogenetic tree reconstruction. Both problems are NP-hard, so we seek approximate solutions. We formulate the two problems as Steiner tree problems under appropriate distances. The gist of our approach is the succinct characterization of Steiner trees for a small number of leaves for the two distances. This enables the use of known Steiner tree approximation algorithms. The approach leads to a 16/9 approximation ratio for AML and asymptotically to a 1.55 approximation ratio for MP.

Original languageEnglish (US)
Article number4429176
Pages (from-to)183-187
Number of pages5
JournalIEEE/ACM Transactions on Computational Biology and Bioinformatics
Volume7
Issue number1
DOIs
StatePublished - Jan 1 2010
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Biotechnology
  • Genetics
  • Applied Mathematics

Keywords

  • Ancestral maximum likelihood
  • Approximation algorithms.
  • Biology and genetics
  • Combinatorial algorithms
  • Computations on discrete structures
  • Constrained optimization
  • Maximum parsimony
  • Phylogenetic reconstruction
  • Steiner trees
  • Trees

Fingerprint Dive into the research topics of 'Approximate maximum parsimony and ancestral maximum likelihood'. Together they form a unique fingerprint.

  • Cite this