Constructing Level-2 Phylogenetic Networks from Triplets

Abstract

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 [24]. 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 nontree-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.

References

1. A.V. Aho, Y. Sagiv, T.G. Szymanski, and J.D. Ullman, "Inferring a Tree from Lowest Common Ancestors with an Application to the Optimization of Relational Expressions," SIAM J. Computing, vol. 10, no. 3, pp. 405-421, 1981.
2. D. Bryant, "Building Trees, Hunting for Trees, and Comparing Trees: Theory and Methods in Phylogenetic Analysis," PhD dissertation, Univ. of Canterbury, 1997.
3. D. Bryant and V. Moulton, "Neighbor-Net: An Agglomerative Method for the Construction of Phylogenetic Networks," Molecular Biology and Evolution, vol. 21, no. 2, pp. 255-265, 2004.
4. D. Bryant and M. Steel, "Constructing Optimal Trees from Quartets," J. Algorithms, vol. 38, no. 1, pp. 237-259, 2001.
5. J. Byrka, P. Gawrychowski, K.T. Huber, and S. Kelk, "Worst-Case Optimal Approximation Algorithms for Maximizing Triplet Consistency within Phylogenetic Networks," arXiv:0710.3258v3 {q-bio.PE}, 2008.
6. H.-L. Chan, J. Jansson, T.W. Lam, and S.-M. Yiu, "Reconstructing an Ultrametric Galled Phylogenetic Network from a Distance Matrix," J. Bioinformatics and Computational Biology, vol. 4, no. 4, pp. 807-832, 2006.
7. P.L. Erdös, M.A. Steel, L.A. Szekely, and T. Warnow, "A Few Logs Suffice to Build (Almost) All Trees (Part II)," Theoretical Computer Science, vol. 221, no. 1, pp. 77-118, 1999.
8. L. Gaasieniec, J. Jansson, A. Lingas, and A. Östlin, "On the Complexity of Constructing Evolutionary Trees," J. Combinatorial Optimization, vol. 3, pp. 183-197, 1999.
9. S. Guindon and O. Gascuel, "A Simple, Fast, and Accurate Algorithm to Estimate Large Phylogenies by Maximum Likelihood," Systematic Biology, vol. 52, no. 5, pp. 696-704, 2003.
10. D. Gusfield, S. Eddhu, and C. Langley, "Optimal, Efficient Reconstruction of Phylogenetic Networks with Constrained Recombination," J. Bioinformatics and Computational Biology, vol. 2, pp. 173-213, 2004.
11. Y.-J. He, T.N.D. Huynh, J. Jansson, and W.-K. Sung, "Inferring Phylogenetic Relationships Avoiding Forbidden Rooted Triplets," J. Bioinformatics and Computational Biology, vol. 4, no. 1, pp. 59-74, 2006.
12. M. Holder and P.O. Lewis, "Phylogeny Estimation: Traditional and Bayesian Approaches," Nature Rev. Genetics, vol. 4, pp. 275- 284, 2003.
13. K.T. Huber, B. Oxelman, M. Lott, and V. Moulton, "Reconstructing the Evolutionary History of Polyploids from Multilabeled Trees," Molecular Biology and Evolution, vol. 23, no. 9, pp. 1784- 1791, 2006.
14. D.H. Huson and D. Bryant, "Application of Phylogenetic Networks in Evolutionary Studies," Molecular Biology and Evolution, vol. 23, no. 2, pp. 254-267, 2006.
15. D.H. Huson and T.H. Klöpper, "Beyond Galled Trees--Decomposition and Computation of Galled Networks," Proc. Int'l Conf. Research in Computational Molecular Biology (RECOMB '07), pp. 211- 225, 2007.
16. L.J.J. van Iersel, J.C.M. Keijsper, S.M. Kelk, and L. Stougie, "Constructing Level-2 Phylogenetic Networks from Triplets," arXiv:0707.2890v1 {q-bio.PE}, 2007.
17. L.J.J. van Iersel, J.C.M. Keijsper, S.M. Kelk, L. Stougie, F. Hagen, and T. Boekhout, "Constructing Level-2 Phylogenetic Networks from Triplets," Proc. 12th Ann. Int'l Conf. Research in Computational Molecular Biology (RECOMB '08), pp. 450-462, 2008.
18. L.J.J. van Iersel, S.M. Kelk, and M. Mnich, "Uniqueness, Intractability and Exact Algorithms: Reflections on Level-k Phylogenetic Networks," to be published in J. Bioinformatics and Computational Biology.
19. J. Jansson, personal communication, Kyushu Univ., 2007.
20. J. Jansson, "On the Complexity of Inferring Rooted Evolutionary Trees," Proc. Brazilian Symp. Graphs, Algorithms and Combinatorics (GRACO '01), pp. 121-125, 2001.
21. J. Jansson, J.H.-K. Ng, K. Sadakane, and W.-K. Sung, "Rooted Maximum Agreement Supertrees," Algorithmica, vol. 43, pp. 293- 307, 2005.
22. J. Jansson, N.B. Nguyen, and W.-K. Sung, "Algorithms for Combining Rooted Triplets into a Galled Phylogenetic Network," SIAM J. Computing, vol. 35, no. 5, pp. 1098-1121, 2006.
23. J. Jansson and W.-K. Sung, "Inferring a Level-1 Phylogenetic Network from a Dense Set of Rooted Triplets," Proc. Conf. Computing and Combinatorics (COCOON '04), pp. 462-472, 2004.
24. J. Jansson and W.-K. Sung, "Inferring a Level-1 Phylogenetic Network from a Dense Set of Rooted Triplets," Theoretical Computer Science, vol. 363, pp. 60-68, 2006.
25. T. Jiang, P.E. Kearney, and M. Li, "A Polynomial Time Approximation Scheme for Inferring Evolutionary Trees from Quartet Topologies and Its Application," SIAM J. Computing, vol. 30, no. 6, pp. 1942-1961, 2000.
26. S. Kidd, F. Hagen, R. Tscharke, M. Huynh, K. Bartlett, M. Fyfe, L. MacDougall, T. Boekhout, K.J. Kwon-Chung, and W. Meyer, "A Rare Genotype of Cryptococcus Gattii Caused the Cryptococcosis Outbreak on Vancouver Island (British Columbia, Canada)," Proc. Nat'l Academy of Sciences USA, vol. 101, pp. 17258-17263, 2004.
27. "LEVEL2: A Fast Method for Constructing Level-2 Phylogenetic Networks from Dense Sets of Rooted Triplets," http://home pages.cwi.nl/~kelk/level2triplets.html and http://level2.source forge.net/, 2009.
28. V. Makarenkov, "T-REX: Reconstructing and Visualizing Phylogenetic Trees and Reticulation Networks," Bioinformatics, vol. 17, no. 7, pp. 664-668, 2001.
29. V. Makarenkov, D. Kevorkov, and P. Legendre, "Phylogenetic Network Reconstruction Approaches," Applied Mycology and Biotechnology, vol. 6. pp. 61-97, 2006.
30. B.M.E. Moret, L. Nakhleh, T. Warnow, C.R. Linder, A. Tholse, A. Padolina, J. Sun, and R. Timme, "Phylogenetic Networks: Modeling, Reconstructibility, and Accuracy," IEEE/ACM Trans. Computational Biology and Bioinformatics, vol. 1, no. 1, pp. 13-23, Jan.-Mar. 2004.
31. C. Semple and M. Steel, Phylogenetics. Oxford Univ. Press, 2003.
32. M. Steel, "The Complexity of Reconstructing Trees from Qualitative Characters and Subtrees," J. Classification, vol. 9, pp. 91-116, 1992.
33. R.E. Tarjan and U. Vishkin, "An Efficient Parallel Biconnectivity Algorithm," SIAM J. Computing, vol. 14, no. 4, pp. 862-874, 1985.
34. L. Wang, K. Zhang, and L. Zhang, "Perfect Phylogenetic Networks with Recombination," J. Computational Biology, vol. 8, no. 1, pp. 69-78, 2001.
35. B.Y. Wu, "Constructing the Maximum Consensus Tree from Rooted Triples," J. Combinatorial Optimization, vol. 8, pp. 29-39, 2004.

Index Terms

• Applied computing

  • Life and medical sciences

    • Computational biology

    • Genetics

    • Systems biology

• Theory of computation

  • Computational complexity and cryptography

    • Complexity classes

  • Design and analysis of algorithms