Additive approximation for near-perfect phylogeny construction

DOI10.1007/978-3-642-32512-0_3zbMATH1358.68317OpenAlexW1875940007MaRDI QIDQ3167382FDOQ3167382

Authors Pranjal Awasthi, Jamie Morgenstern, Or Sheffet, Avrim Blum

Publication date 2 November 2012

Published in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1206.3334

Mathematics Subject Classification ID

Problems related to evolution (92D15) Approximation algorithms (68W25)

Abstract: 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(q^2)$. This provides the best guarantees known - namely, a $(1+o(1))$-approximation - for the case $log(d)llqllsqrtd$, 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.

Recommendations

• Simple Reconstruction of Binary Near-Perfect Phylogenetic Trees
• scientific article; zbMATH DE number 2102787
• Fixed Parameter Tractability of Binary Near-Perfect Phylogenetic Tree Reconstruction
• A Polynomial-Time Algorithm for Near-Perfect Phylogeny
• An optimal algorithm to reconstruct trees from additive distance data

Cited in

(3)

• Simple Reconstruction of Binary Near-Perfect Phylogenetic Trees
• Fixed Parameter Tractability of Binary Near-Perfect Phylogenetic Tree Reconstruction
• Parameterized algorithms for the Steiner arborescence problem on a hypercube

This page was built for publication: Additive approximation for near-perfect phylogeny construction

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3167382)