Institut für Informatik
Abteilung V

Universität Bonn -> Institut für Informatik -> Abteilung V
CS-Reports 2008 Copyright 2008 Universität Bonn, Institut für Informatik, Abt. V


Approximability of Selected Phylogenetic Tree Problems
Mathias Hauptmann and Marlis Lamp
[Download PostScript] [Download PDF]

We study the approximability of the reconstruction problem of phylogenetic trees with respect to three different cost measures and give the first explicit lower bounds, under standard complexity-theoretic assumptions. For the Steiner Tree Problem in Phylogeny (STPP) and the Generalized Tree Alignment (GTA) problem, we show that unless P = NP, no polynomial-time algorithm can approximate these problems with an approximation ratio below 359/358. For the Ancestral Maximum Likelihood (AML) problem we give a lower bound of 1577/1576. Furthermore we construct a polynomial-time approximation scheme (Aε)ε>0 for the AML problem, such that for each ε > 0, Aε is a polynomial time approximation algorithm with ratio (1 + ε) ⋅ (1 + ln(3)/2). This result is based on the Steiner tree algorithm of Robins and Zelikovsky [RZ00] and on a new exact algorithm for AML instances of constant size. This improves upon recent results by Alon et al. [ACPR08] who gave a 1.78-approximation algorithm for the AML problem.

Last Change: 11/05/14 at 10:39:58
Universität Bonn -> Institut für Informatik -> Abteilung V