Approximate maximum parsimony and ancestral maximum likelihood.
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.
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
Noga
N
Alon
Benny
B
Chor
Fabio
F
Pardi
Anat
A
Rapoport
D000465:Algorithms; D001483:Base Sequence; D003198:Computer Simulation; D004252:DNA Mutational Analysis / Q000379:methods*; D003627:Data Interpretation, Statistical; D019143:Evolution, Molecular; D016013:Likelihood Functions; D008957:Models, Genetic; D015233:Models, Statistical; D008969:Molecular Sequence Data; D017422:Sequence Analysis, DNA / Q000379:methods*