| Approximate maximum parsimony and ancestral maximum likelihood. | |
| | |
MedLine Citation:
|
PMID: 20150680 Owner: NLM Status: MEDLINE |
Abstract/OtherAbstract:
|
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. |
| | |
Authors:
|
Noga Alon; Benny Chor; Fabio Pardi; Anat Rapoport |
Publication Detail:
|
Type: Journal Article; Research Support, Non-U.S. Gov't; Research Support, U.S. Gov't, Non-P.H.S. |
Journal Detail:
|
Title: IEEE/ACM transactions on computational biology and bioinformatics / IEEE, ACM Volume: 7 ISSN: 1557-9964 ISO Abbreviation: IEEE/ACM Trans Comput Biol Bioinform Publication Date: 2010 Jan-Mar |
Date Detail:
|
Created Date: 2010-02-12 Completed Date: 2010-05-06 Revised Date: - |
Medline Journal Info:
|
Nlm Unique ID: 101196755 Medline TA: IEEE/ACM Trans Comput Biol Bioinform Country: United States |
Other Details:
|
Languages: eng Pagination: 183-7 Citation Subset: IM |
Affiliation:
|
Schools of Mathematics and Computer Science,Raymond and Beverly Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv, Israel. nogaa@post.tau.ac.il |
Export Citation:
|
APA/MLA Format Download EndNote Download BibTex |
| MeSH Terms | |
Descriptor/Qualifier:
|
Algorithms* Base Sequence Computer Simulation DNA Mutational Analysis / methods* Data Interpretation, Statistical Evolution, Molecular* Likelihood Functions Models, Genetic* Models, Statistical Molecular Sequence Data Sequence Analysis, DNA / methods* |
From MEDLINE®/PubMed®, a database of the U.S. National Library of Medicine
Previous Document: On the importance of comprehensible classification models for protein function prediction.
Next Document: Comparison of anatomic coordinate systems with rigid multi-resolution 3D registration for the reprod...