# PLG

## Seminar

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

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