Additive Approximation for Near-perfect Phylogeny Construction
Oct 26, 2011

We study the problem of constructing phylogenetic trees for a given set of species. The problem is formulated as that of finding a minimum Steiner tree on n points over the Boolean hypercube of dimension d. It is known that an optimal tree can be found in linear time if the cost of the optimal phylogeny is exactly d (a perfect phylogeny). Moreover, if the data is a near-perfect phylogeny, i.e., the cost of the optimal tree is d + q, it is known that an exact solution can be found in running time which is polynomial in the number of species and d, but exponential in q . In this work, we study the case of near-perfect phylogenies, where the optimal phylogenetic tree has cost d + q, and give a polynomial-time algorithm (polynomial in both d and q) that finds a phylogenetic tree of cost d + O(q^2 ). We also discuss the motivation and reasoning for studying such additive approximations.

Joint work with Pranjal Awasthi, Avrim Blum, and Or Sheffet