Related Experiment Video
Updated: Jun 16, 2026

A Practical Guide to Phylogenetics for Nonexperts
Published on: February 5, 2014
Approximate maximum parsimony and ancestral maximum likelihood
Noga Alon1, Benny Chor, Fabio Pardi
1Schools of Mathematics and Computer Science,Raymond and Beverly Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv, Israel. nogaa@post.tau.ac.il
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.
Related Concept Videos
Phylogenetic Trees
Phylogenetic Trees
Microbial Phylogeny
Evolutionary Relationships through Genome Comparisons
Phylogeny
Synteny and Evolution
Around 80 million years ago, the human and mice lineages diverged from the common ancestor. During the course of evolution, the ancestral chromosome underwent...

