Approximate Maximum Parsimony and Ancestral Maximum Likelihood

Author

Alon, Noga ; Chor, Benny ; Pardi, Fabio ; Rapoport, Anat

Author_Institution

Schools of Math. & Comput. Sci., Tel Aviv Univ., Tel Aviv, Israel

Volume

7

Issue

1

fYear

2010

Firstpage

183

Lastpage

187

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.

Keywords

bioinformatics; genetics; maximum likelihood estimation; optimisation; NP-hard problem; Steiner tree problems; ancestral maximum likelihood; approximate maximum parsimony; phylogenetic tree reconstruction; Algorithm design and analysis; Biology and genetics; Combinatorial algorithms; Computations on discrete structures; Constrained optimization; Phylogenetic reconstruction; Steiner trees; Trees; ancestral maximum likelihood; approximation algorithms.; maximum parsimony; Algorithms; Base Sequence; Computer Simulation; DNA Mutational Analysis; Data Interpretation, Statistical; Evolution, Molecular; Likelihood Functions; Models, Genetic; Models, Statistical; Molecular Sequence Data; Sequence Analysis, DNA;

fLanguage

English

Journal_Title

Computational Biology and Bioinformatics, IEEE/ACM Transactions on

Publisher

ieee

ISSN

1545-5963

Type

jour

DOI

10.1109/TCBB.2008.13

Filename

4429176