Additive Approximation for Near-Perfect Phylogeny Construction

<p>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 <em>n</em> points over the Boolean hypercube of dimension <em>d</em>. It is known that an optimal tree can be found in linear time [1] if the given dataset has a perfect phylogeny, i.e. cost of the optimal phylogeny is exactly <em>d</em>. Moreover, if the data has a near-perfect phylogeny, i.e. the cost of the optimal Steiner tree is<em>d</em> + <em>q</em>, it is known [2] that an exact solution can be found in running time which is polynomial in the number of species and <em>d</em>, yet exponential in <em>q</em>. In this work, we give a polynomial-time algorithm (in both <em>d</em> and <em>q</em>) that finds a phylogenetic tree of cost <em>d</em> + <em>O</em>(<em>q</em> 2). This provides the best guarantees known—namely, a (1 + <em>o</em>(1))-approximation—for the case log(d)≪q≪d√, broadening the range of settings for which near-optimal solutions can be efficiently found. We also discuss the motivation and reasoning for studying such additive approximations.</p>