Who is Who in Phylogenetic Networks

Publication no #400   Type :   Html | Bib | Both

Created: 2007-11-17 01:16:40     Modified: 2010-01-11 01:56:21

400 Jaroslaw Byrka, Pawel Gawrychowski, Katharina Huber and Steven Kelk. Worst-case optimal approximation algorithms for maximizing triplet consistency within phylogenetic networks. In Journal of Discrete Algorithms, Vol. 8(1):65-75, 2010. Keywords: approximation, explicit network, from triplets, galled tree, level k phylogenetic network, phylogenetic network, phylogeny, reconstruction. Note: http://arxiv.org/abs/0710.3258.         Toggle abstract "The study of phylogenetic networks is of great interest to computational evolutionary biology and numerous different types of such structures are known. This article addresses the following question concerning rooted versions of phylogenetic networks. What is the maximum value of p ∈ [0, 1] such that for every input set T of rooted triplets, there exists some network N such that at least p | T | of the triplets are consistent with N? We call an algorithm that computes such a network (where p is maximum) worst-case optimal. Here we prove that the set containing all triplets (the full triplet set) in some sense defines p. Moreover, given a network N that obtains a fraction p′ for the full triplet set (for any p′), we show how to efficiently modify N to obtain a fraction ≥ p′ for any given triplet set T. We demonstrate the power of this insight by presenting a worst-case optimal result for level-1 phylogenetic networks improving considerably upon the 5/12 fraction obtained recently by Jansson, Nguyen and Sung. For level-2 phylogenetic networks we show that p ≥ 0.61. We emphasize that, because we are taking | T | as a (trivial) upper bound on the size of an optimal solution for each specific input T, the results in this article do not exclude the existence of approximation algorithms that achieve approximation ratio better than p. Finally, we note that all the results in this article also apply to weighted triplet sets. © 2009 Elsevier B.V. All rights reserved." @Article{BGHK2010,       AUTHOR = {Byrka, Jaroslaw and Gawrychowski, Pawel and Huber, Katharina and Kelk, Steven},       TITLE = {Worst-case optimal approximation algorithms for maximizing triplet consistency within phylogenetic networks},       YEAR = {2010},       JOURNAL = {Journal of Discrete Algorithms},       VOLUME = {8},       NUMBER = {1},       PAGES = {65-75},       URL = {http://dx.doi.org/10.1016/j.jda.2009.01.004},       NOTE = {http://arxiv.org/abs/0710.3258},       ANNOTE = {BIBUPDATE : 20080312},       KEYWORDS = {approximation, explicit network, from triplets, galled tree, level k phylogenetic network, phylogenetic network, phylogeny, reconstruction} }