doi: 10.1109/TCBB.2008.13.
Approximate maximum parsimony and ancestral maximum likelihood
Affiliations
- PMID: 20150680
- DOI: 10.1109/TCBB.2008.13
Item in Clipboard
Approximate maximum parsimony and ancestral maximum likelihood
IEEE/ACM Trans Comput Biol Bioinform.
2010 Jan-Mar.
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.
Similar articles
-
A short proof that phylogenetic tree reconstruction by maximum likelihood is hard.IEEE/ACM Trans Comput Biol Bioinform. 2006 Jan-Mar;3(1):92-4. doi: 10.1109/TCBB.2006.4. IEEE/ACM Trans Comput Biol Bioinform. 2006. PMID: 17048396
-
Reconstruction of ancestral genomic sequences using likelihood.J Comput Biol. 2007 Mar;14(2):216-37. doi: 10.1089/cmb.2006.0101. J Comput Biol. 2007. PMID: 17456016
-
Reconstructing ancestral genomic sequences by co-evolution: formal definitions, computational issues, and biological examples.J Comput Biol. 2010 Sep;17(9):1327-44. doi: 10.1089/cmb.2010.0112. J Comput Biol. 2010. PMID: 20874411
-
Homology assessment and molecular sequence alignment.J Biomed Inform. 2006 Feb;39(1):18-33. doi: 10.1016/j.jbi.2005.11.005. Epub 2005 Dec 9. J Biomed Inform. 2006. PMID: 16380300 Review.
-
Coalescent methods for estimating phylogenetic trees.Mol Phylogenet Evol. 2009 Oct;53(1):320-8. doi: 10.1016/j.ympev.2009.05.033. Epub 2009 Jun 6. Mol Phylogenet Evol. 2009. PMID: 19501178 Review.
Cited by
-
Algorithms for reconstruction of chromosomal structures.BMC Bioinformatics. 2016 Jan 19;17:40. doi: 10.1186/s12859-016-0878-z. BMC Bioinformatics. 2016. PMID: 26780836 Free PMC article.
-
On parsimony and clustering.PeerJ Comput Sci. 2023 Apr 20;9:e1339. doi: 10.7717/peerj-cs.1339. eCollection 2023. PeerJ Comput Sci. 2023. PMID: 37346541 Free PMC article.
-
Scelestial: Fast and accurate single-cell lineage tree inference based on a Steiner tree approximation algorithm.PLoS Comput Biol. 2022 Aug 11;18(8):e1009100. doi: 10.1371/journal.pcbi.1009100. eCollection 2022 Aug. PLoS Comput Biol. 2022. PMID: 35951662 Free PMC article.
Publication types
MeSH terms
LinkOut - more resources
Full Text Sources
Miscellaneous
