skip to content
 

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

Presented by: 
S Kelk [CWI Amsterdam]
Date: 
Tuesday 13th November 2007 - 14:00 to 15:00
Venue: 
INI Seminar Room 2
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

University of Cambridge Research Councils UK
    Clay Mathematics Institute The Leverhulme Trust London Mathematical Society Microsoft Research NM Rothschild and Sons