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 language||English (US)|
|Number of pages||5|
|Journal||IEEE/ACM Transactions on Computational Biology and Bioinformatics|
|State||Published - Jan 1 2010|
All Science Journal Classification (ASJC) codes
- Applied Mathematics
- Ancestral maximum likelihood
- Approximation algorithms.
- Biology and genetics
- Combinatorial algorithms
- Computations on discrete structures
- Constrained optimization
- Maximum parsimony
- Phylogenetic reconstruction
- Steiner trees