The INI has a new website!

This is a legacy webpage. Please visit the new site to ensure you are seeing up to date information.

Skip to content



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


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 ∧