AI Article Synopsis
- The text discusses methods for reconstructing phylogenetic trees using maximum parsimony (MP) and ancestral maximum likelihood (AML), both of which are computationally difficult (NP-hard).
- The authors propose framing these problems as Steiner tree problems to find approximate solutions, which simplifies the analysis.
- Their approach delivers a 16/9 approximation ratio for AML and an asymptotic ratio of 1.55 for MP, indicating improved efficiency in solving these complex issues.
Article 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.
Download full-text PDF |
Source |
|---|---|
| http://dx.doi.org/10.1109/TCBB.2008.13 | DOI Listing |
Publication Analysis
Top Keywords
maximum parsimony
8
parsimony ancestral
8
ancestral maximum
8
maximum likelihood
8
steiner tree
8
approximation ratio
8
approximate maximum
4
likelihood explore
4
explore maximum
4
likelihood aml
4
Similar Publications
Want AI Summaries of new PubMed Abstracts delivered to your In-box?
Enter search terms and have AI summaries delivered each week - change queries or unsubscribe any time!