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.
, , , ,
M. Vingron , L. Wong (Limsoon)
IEEE/ACM Transactions on Computational Biology and Bioinformatics
Combinatorial Algorithms in Bio-informatics
Annual International Conference on Computational Molecular Biology
Evolutionary Intelligence

van Iersel, L., Keijsper, J. C. M., Kelk, S., 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.