Jansson and Sung showed that, given a dense set of input triplets T (representing hypotheses about the local evolutionary relationships of triplets of taxa), it is possible to determine in polynomial time whether there exists a level-1 network consistent with T, and if so to construct such a network (Inferring a Level-1 Phylogenetic Network from a Dense Set of Rooted Triplets, Theoretical Computer Science, 363, pp. 60-68 (2006)). Here we extend this work by showing that this problem is even polynomial-time solvable for the construction of level-2 networks. This shows that, assuming density, it is tractable to construct plausible evolutionary histories from input triplets even when such histories are heavily non-tree like. This further strengthens the case for the use of triplet-based methods in the construction of phylogenetic networks. We also implemented the algorithm and applied it to yeast data.
Additional Metadata
Keywords phylogenetic networks, polynomial-time, triplets, level-2, density
MSC Mathematical biology in general (msc 92Bxx)
THEME Life Sciences (theme 5), Energy (theme 4)
Publisher I.E.E.E.
Editor M. Vingron , L. Wong
Journal IEEE/ACM Transactions on Computational Biology and Bioinformatics
Project Combinatorial Algorithms in Bio-informatics
Conference Annual International Conference on Computational Molecular Biology
van Iersel, L.J.J, Keijsper, J.C.M, Kelk, S.M, Stougie, L, Hagen, F, & Boekhout, T. (2009). Constructing level-2 phylogenetic networks from triplets. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 6, 667–681.