[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

Constructing the Simplest Possible Phylogenetic Network from Triplets

  • Conference paper
Algorithms and Computation (ISAAC 2008)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 5369))

Included in the following conference series:

Abstract

A phylogenetic network is a directed acyclic graph that visualises an evolutionary history containing so-called reticulations such as recombinations, hybridisations or lateral gene transfers. Here we consider the construction of a simplest possible phylogenetic network consistent with an input set T, where T contains at least one phylogenetic tree on three leaves (a triplet) for each combination of three taxa. To quantify the complexity of a network we consider both the total number of reticulations and the number of reticulations per biconnected component, called the level of the network. We give polynomial-time algorithms for constructing a level-1 respectively a level-2 network that contains a minimum number of reticulations and is consistent with T (if such a network exists). In addition, we show that if T is precisely equal to the set of triplets consistent with some network, then we can construct such a network, which minimises both the level and the total number of reticulations, in time O(|T|k + 1), if k is a fixed upper bound on the level.

Part of this research has been funded by the Dutch BSIK/BRICKS project.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Aho, A.V., Sagiv, Y., Szymanski, T.G., Ullman, J.D.: Inferring a Tree from Lowest Common Ancestors with an Application to the Optimization of Relational Expressions. SIAM Journal on Computing 10(3), 405–421 (1981)

    Article  MathSciNet  MATH  Google Scholar 

  2. Baroni, M., Grünewald, S., Moulton, V., Semple, C.: Bounding the Number of Hybridisation Events for a Consistent Evolutionary History. Mathematical Biology 51, 171–182 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  3. Baroni, M., Semple, C., Steel, M.: A Framework for Representing Reticulate Evolution. Annals of Combinatorics 8, 391–408 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  4. Bordewich, M., Semple, C.: Computing the Minimum Number of Hybridization Events for a Consistent Evolutionary History. Discrete Applied Mathematics 155(8), 914–928 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  5. Choy, C., Jansson, J., Sadakane, K., Sung, W.-K.: Computing the Maximum Agreement of Phylogenetic Networks. Theoretical Computer Science 335(1), 93–107 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  6. Gusfield, D., Eddhu, S., Langley, C.: Optimal, Efficient Reconstructing of Phylogenetic Networks with Constrained Recombination. Journal of Bioinformatics and Computational Biology 2(1), 173–213 (2004)

    Article  MATH  Google Scholar 

  7. He, Y.-J., Huynh, T.N.D., Jansson, J., Sung, W.-K.: Inferring Phylogenetic Relationships Avoiding Forbidden Rooted Triplets. Journal of Bioinformatics and Computational Biology 4(1), 59–74 (2006)

    Article  Google Scholar 

  8. Hein, J.: Reconstructing Evolution of Sequences Subject to Recombination Using Parsimony. Mathematical Biosciences 98, 185–200 (1990)

    Article  MathSciNet  MATH  Google Scholar 

  9. Huson, D.H., Bryant, D.: Application of Phylogenetic Networks in Evolutionary Studies. Molecular Biology and Evolution 23(2), 254–267 (2006)

    Article  Google Scholar 

  10. Huynh, T.N.D., Jansson, J., Nguyen, N.B., Sung, W.-K.: Constructing a Smallest Refining Galled Phylogenetic Network. In: Miyano, S., Mesirov, J., Kasif, S., Istrail, S., Pevzner, P.A., Waterman, M. (eds.) RECOMB 2005. LNCS (LNBI), vol. 3500, pp. 265–280. Springer, Heidelberg (2005)

    Chapter  Google Scholar 

  11. van Iersel, L.J.J., Keijsper, J.C.M., Kelk, S.M., Stougie, L., Hagen, F., Boekhout, T.: Constructing Level-2 Phylogenetic Networks from Triplets. In: Vingron, M., Wong, L. (eds.) RECOMB 2008. LNCS (LNBI), vol. 4955, pp. 450–462. Springer, Heidelberg (2008)

    Chapter  Google Scholar 

  12. van Iersel, L.J.J., Kelk, S.M., Mnich, M.: Uniqueness, Intractability and Exact Algorithms: Reflections on Level-k Phylogenetic Networks, arXiv:0712.2932v3 [q-bio.PE] (2008)

    Google Scholar 

  13. Jansson, J., Nguyen, N.B., Sung, W.-K.: Algorithms for Combining Rooted Triplets into a Galled Phylogenetic Network. SIAM Journal on Computing 35(5), 1098–1121 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  14. Jansson, J., Sung, W.-K.: Inferring a Level-1 Phylogenetic Network from a Dense Set of Rooted Triplets. Theoretical Computer Science 363, 60–68 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  15. Makarenkov, V., Kevorkov, D., Legendre, P.: Phylogenetic Network Reconstruction Approaches. In: Applied Mycology and Biotechnology. International Elsevier Series 6, Bioinformatics, pp. 61–97 (2006)

    Google Scholar 

  16. MARLON: Constructing Level One Phylogenetic Networks with a Minimum Amount of Reticulation, http://homepages.cwi.nl/~kelk/marlon.html

  17. Morrison, D.A.: Networks in Phylogenetic Analysis: New Tools for Population Biology. International Journal for Parasitology 35(5), 567–582 (2005)

    Article  Google Scholar 

  18. Moret, B.M.E., Nakhleh, L., Warnow, T., Linder, C.R., Tholse, A., Padolina, A., Sun, J., Timme, R.: Phylogenetic Networks: Modeling, Reconstructibility, and Accuracy. IEEE/ACM Transactions on Computational Biology and Bioinformatics 1(1), 13–23 (2004)

    Article  Google Scholar 

  19. Song, Y.S., Hein, J.: On the Minimum Number of Recombination Events in the Evolutionary History of DNA Sequences. Journal of Mathematical Biology 48, 160–186 (2004)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics and Computer Science, Technische Universiteit Eindhoven, P.O. Box 513, 5600 MB, Eindhoven, The Netherlands

    Leo van Iersel

  2. Centrum voor Wiskunde en Informatica (CWI), P.O. Box 94079, 1090 GB, Amsterdam, The Netherlands

    Steven Kelk

Authors
  1. Leo van Iersel
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Steven Kelk
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. School of Information Technologies, University of Sydney, Australia

    Seok-Hee Hong

  2. Graduate School of Informatics, Kyoto University, 606-8501, Kyoto, Japan

    Hiroshi Nagamochi

  3. Graduate School of Informatics, Kyoto University, Japan

    Takuro Fukunaga

Rights and permissions

Reprints and permissions

Copyright information

© 2008 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

van Iersel, L., Kelk, S. (2008). Constructing the Simplest Possible Phylogenetic Network from Triplets. In: Hong, SH., Nagamochi, H., Fukunaga, T. (eds) Algorithms and Computation. ISAAC 2008. Lecture Notes in Computer Science, vol 5369. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-92182-0_43

Download citation

  • DOI: https://doi.org/10.1007/978-3-540-92182-0_43

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-92181-3

  • Online ISBN: 978-3-540-92182-0

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation