Constructing level-2 phylogenetic networks from triplets
IEEE/ACM Transactions on Computational Biology and Bioinformatics , Volume 6 p. 667- 681
Presented at the Annual International Conference on Computational Molecular Biology , Singapore
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.
|Keywords||phylogenetic networks, polynomial-time, triplets, level-2, density|
|MSC||Mathematical biology in general (msc 92Bxx)|
|THEME||Life Sciences (theme 5), Energy (theme 4)|
|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.