Skip to content

PLG

Seminar

Worst-case optimal approximation algorithims for maximising triplet consistency within phylogenetic networks

Kelk, S (CWI Amsterdam)
Tuesday 13 November 2007, 14:00-15:00

Seminar Room 2, Newton Institute Gatehouse

Abstract

This article concerns the following question. Assuming that we restrict the set of phylogenetic networks to some subclass, what is the maximum value of 0 <= p <= 1 such that for every input set T of rooted triplets, there exists some network N(T) from the subclass such that at least p|T| of the triplets are consistent with N(T)? Here we prove that the set containing all triplets (the full triplet set) in some sense defines p, and moreover that any network N achieving a ratio p' for the full triplet set can be converted in polynomial time into an isomorphic network N'(T) achieving ratio >= p' for an arbitrary triplet set T. The result also holds for weighted triplet sets. We demonstrate the power of this technique for the field of phylogenetics by giving worst-case optimal algorithms for the set of level-1 phylogenetic networks, improving considerably upon the 5/12 ratio obtained recently by Jansson, Nguyen and Sung. For level-2 phylogenetic networks we show that p >= 0.61

Back to top ∧