2012/06/14 by Awasthi, Pranjal, Blum, Avrim, Morgenstern, Jamie +1
#Computational Engineering #Data Structures and Algorithms (cs.DS) #FOS: Biological sciences #FOS: Computer and information sciences #Finance #Populations and Evolution (q-bio.PE) #and Science (cs.CE)
paper · doi:10.48550/arxiv.1206.3334
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 given dataset has a perfect phylogeny, i.e. cost of the optimal phylogeny is exactly d. Moreover, if the data has a near-perfect phylogeny, i.e. the cost of the optimal Steiner 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, yet exponential in q. In this work, we give a polynomial-time algorithm (in both d and q) that finds a phylogenetic tree of cost d+O(q2). This provides the best guarantees known - namely, a (1+o(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.