Beyond Evolutionary Trees | SpringerLink
Skip to main content
Springer Nature Link
Log in

Beyond Evolutionary Trees

  • Reference work entry
  • First Online:
Encyclopedia of Algorithms

  • 208 Accesses

Years and Authors of Summarized Original Work

  • 2005; Choy, Jansson, Sadakane, Sung

  • 2010; Della Vedova, Dondi, Jiang, Pavesi, Pirola, Wang

  • 2011; Tofigh, Hallett, Lagergren

  • 2011; van Iersel, Kelk

  • 2014; Kelk, Scornavacca

Problem Definition

Recent developments in phylogenetics have provided evidences that evolutionary histories cannot always be represented as a single tree; thus, more sophisticated representations are needed. Phylogenetic networks are natural extensions of phylogenetic trees that recently gathered general consensus in literature. Let \(\varLambda\) be a finite set of labels, representing a set of extant species (taxa). A rooted phylogenetic N over\(\varLambda\) (or, simply, phylogenetic network or network) is a directed acyclic connected graph \(N =\langle V (N),A(N)\rangle\) containing a unique vertex with no incoming arcs, called root of N, and a labeling function from the set L(N) of leaves of N to the set of labels \(\varLambda\). The set of labels associated with the...

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

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 285999
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Hardcover Book
JPY 285999
Price includes VAT (Japan)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Recommended Reading

  1. Bansal MS, Alm EJ, Kellis M (2012) Efficient algorithms for the reconciliation problem with gene duplication, horizontal transfer and loss. Bioinformatics 28(12):283–291. doi:10.1093/bioinformatics/ bts225

    Article  Google Scholar 

  2. Bonizzoni P, Della Vedova G, Dondi R (2005) Reconciling a gene tree to a species tree under the duplication cost model. Theor Comput Sci 347(1–2):36–53. doi:10.1016/j.tcs.2005.05.016

    Article  MathSciNet  MATH  Google Scholar 

  3. Burleigh JG, Bansal MS, Wehe A, Eulenstein O (2008) Locating multiple gene duplications through reconciled trees. In: Proceedings of the 12th annual international conference on research in computational molecular biology, RECOMB 2008, Singapore. LNCS, vol 4955. Springer, pp 273–284. doi:10.1007/978-3-540-78839-3_24

    Google Scholar 

  4. Chang WC, Eulenstein O (2006) Reconciling gene trees with apparent polytomies. In: Proceedings of the 12th annual international conference on computing and combinatorics, COCOON 2006, Taipei. LNCS, vol 4112. Springer, pp 235–244. doi:10.1007/11809678_26

    Google Scholar 

  5. Chauve C, El-Mabrouk N (2009) New perspectives on gene family evolution: losses in reconciliation and a link with supertrees. In: Proceedings of the 13th annual international conference on research in computational molecular biology, RECOMB 2009, Tucson. LNCS, vol 5541. Springer, pp 46–58. doi:10.1007/978-3-642-02008-7_4

    Google Scholar 

  6. Choy C, Jansson J, Sadakane K, Sung WK (2005) Computing the maximum agreement of phylogenetic networks. Theor Comput Sci 335(1):93–107. doi:10.1016/j.tcs.2004.12.012

    Article  MathSciNet  MATH  Google Scholar 

  7. Della Vedova G, Dondi R, Jiang T, Pavesi G, Pirola Y, Wang L (2010) Beyond evolutionary trees. Nat Comput 9(2):421–435. doi:10.1007/s11047-009-9156-6

    Article  MathSciNet  MATH  Google Scholar 

  8. Gambette P, Berry V, Paul C (2012) Quartets and unrooted phylogenetic networks. J Bioinform Comput Biol 10(4). doi:10.1142/S0219720012500047

    Google Scholar 

  9. Goodman M, Czelusniak J, Moore GW, Romero-Herrera AE, Matsuda G (1979) Fitting the gene lineage into its species lineage, a parsimony strategy illustrated by cladograms constructed from globin sequences. Syst Zool 28(2):132–163. doi:10.1093/sysbio/28.2.132

    Article  Google Scholar 

  10. Gòrecki P (2004) Reconciliation problems for duplication, loss and horizontal gene transfer. In: Proceedings of the 8th annual international conference on computational molecular biology, RECOMB 2004, San Diego. ACM, pp 316–325. doi:10.1145/974614.974656

    Google Scholar 

  11. Gòrecki P, Tiuryn J (2006) DLS-trees: a model of evolutionary scenarios. Theor Comput Sci 359(1–3):378–399. doi:10.1016/j.tcs.2006.05.019

    Article  MathSciNet  MATH  Google Scholar 

  12. Guigò R, Muchnik I, Smith T (1996) Reconstruction of ancient molecular phylogeny. Mol Phylogenet Evol 6(2):189–213. doi:10.1006/mpev.1996.0071

    Article  Google Scholar 

  13. Gusfield D, Eddhu S, Langley CH (2004) Optimal, efficient reconstruction of phylogenetic networks with constrained recombination. J Bioinform Comput Biol 2(1):173–214. doi:10.1142/S0219720004000521

    Article  MATH  Google Scholar 

  14. Habib M, To TH (2012) Constructing a minimum phylogenetic network from a dense triplet set. J Bioinform Comput Biol 10(5). doi:10.1142/S0219720012500138

    Google Scholar 

  15. Huson DH, Klöpper TH (2007) Beyond galled trees – decomposition and computation of galled networks. In: Proceedings of the 11th annual international conference on research in computational molecular biology, RECOMB 2007, Oakland. LNCS, vol 4453. Springer, pp 211–225. doi:10.1007/978-3-540-71681-5_15

    Google Scholar 

  16. Huson DH, Rupp R (2008) Summarizing multiple gene trees using cluster networks. In: Proceedings of the 8th international workshop on algorithms in bioinformatics, WABI 2008, Karlsruhe. LNCS, vol 5251. Springer, pp 296–305. doi:10.1007/978-3-540-87361-7_25

    Google Scholar 

  17. Jansson J, Sung WK (2004) The maximum agreement of two nested phylogenetic networks. In: Proceedings of the 15th international symposium on algorithms and computation, ISAAC 2004, Hong Kong. LNCS, vol 3341. Springer, pp 581–593. doi:10.1007/978-3-540-30551-4_51

    Google Scholar 

  18. Jansson J, Nguyen NB, Sung WK (2006) Algorithms for combining rooted triplets into a galled phylogenetic network. SIAM J Comput 35(5):1098–1121. doi:10.1137/S0097539704446529

    Article  MathSciNet  MATH  Google Scholar 

  19. Kelk S, Scornavacca C (2014) Constructing minimal phylogenetic networks from softwired clusters is fixed parameter tractable. Algorithmica 68(4):886–915. doi:10.1007/s00453-012-9708-5

    Article  MathSciNet  MATH  Google Scholar 

  20. Libeskind-Hadas R, Charleston MA (2009) On the computational complexity of the reticulate cophylogeny reconstruction problem. J Comput Biol 16(1):105–117. doi:10.1089/ cmb.2008.0084

    Article  MathSciNet  Google Scholar 

  21. Ma B, Li M, Zhang L (2000) From gene trees to species trees. SIAM J Comput 30(3):729–752. doi:10.1137/S0097539798343362

    Article  MathSciNet  MATH  Google Scholar 

  22. Ovadia Y, Fielder D, Conow C, Libeskind-Hadas R (2011) The cophylogeny reconstruction problem is NP-complete. J Comput Biol 18(1):59–65. doi:10.1089/cmb.2009.0240

    Article  MathSciNet  Google Scholar 

  23. Page R (1994) Maps between trees and cladistic analysis of historical associations among genes. Syst Biol 43(1):58–77. doi:10.1093/sysbio/43.1.58

    Google Scholar 

  24. To TH, Habib M (2009) Level-k phylogenetic networks are constructable from a dense triplet set in polynomial time. In: Proceedings of the 20th annual symposium on combinatorial pattern matching, CPM 2009, Lille. LNCS, vol 5577. Springer, pp 275–288. doi:10.1007/978-3-642-02441-2_25

    Google Scholar 

  25. Tofigh A, Hallett MT, Lagergren J (2011) Simultaneous identification of duplications and lateral gene transfers. IEEE/ACM Trans Comput Biol Bioinform 8(2):517–535. doi:10.1109/TCBB.2010.14

    Article  Google Scholar 

  26. van Iersel L, Kelk S (2011) Constructing the simplest possible phylogenetic network from triplets. Algorithmica 60(2):207–235. doi:10.1007/s00453-009-9333-0

    Article  MathSciNet  MATH  Google Scholar 

  27. van Iersel L, Keijsper J, Kelk S, Stougie L, Hagen F, Boekhout T (2009) Constructing level-2 phylogenetic networks from triplets. IEEE/ACM Trans Comput Biol Bioinform 6(4):667–681. doi:10.1145/1671403.1671415

    Article  Google Scholar 

  28. van Iersel L, Kelk S, Mnich M (2009) Uniqueness, intractability and exact algorithms: reflections on level-k phylogenetic networks. J Bioinform Comput Biol 7(4):597–623. doi:10.1142/S0219720009004308

    Article  Google Scholar 

  29. van Iersel L, Kelk S, Rupp R, Huson D (2010) Phylogenetic networks do not need to be complex: using fewer reticulations to represent conflicting clusters. Bioinformatics 26(12):i124–i131. doi:10.1093/bioinformatics/btq202

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Università degli Studi di Bergamo, Bergamo, Italy

    Riccardo Dondi

  2. Università degli Studi di Milano-Bicocca, Milan, Italy

    Yuri Pirola

Authors
  1. Riccardo Dondi
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Yuri Pirola
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Department of Electrical Engineering and Computer Science, Northwestern University, Evanston, IL, USA

    Ming-Yang Kao

Rights and permissions

Reprints and permissions

Copyright information

© 2016 Springer Science+Business Media New York

About this entry

Cite this entry

Dondi, R., Pirola, Y. (2016). Beyond Evolutionary Trees. In: Kao, MY. (eds) Encyclopedia of Algorithms. Springer, New York, NY. https://doi.org/10.1007/978-1-4939-2864-4_599

Download citation

Publish with us

Policies and ethics