Approximate Maximum Parsimony and Ancestral Maximum Likelihood

作者：Alon Noga^*; Chor Benny; Pardi Fabio; Rapoport Anat

来源：IEEE/ACM Transactions on Computational Biology and Bioinformatics, 2010, 7(1): 183-187.

DOI：10.1109/TCBB.2008.13

• Phylogenetic reconstruction
• ancestral maximum likelihood
• maximum parsimony
• Steiner trees
• approximation algorithms

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.

• 出版日期2010-3