18.12.2008

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.