Top

Published in:

2020 | OriginalPaper | Chapter

Recent Progresses in the Combinatorial and Algorithmic Study of Rooted Phylogenetic Networks

Author : Louxin Zhang

Published in: WALCOM: Algorithms and Computation

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Galled trees are studied as a recombination model in theoretical population genetics. Tree-child networks, reticulation-visible networks and tree-based networks can be considered as the generalizations of galled trees through relaxing a structural condition. Although these networks are simple, their topological structures have yet to be fully understood. Here, recent progresses in the tree and cluster containment problems and network counting problems are summarized.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Space Efficient Separator Algorithms for Planar Graphs

next chapter Optimum Algorithm for the Mutual Visibility Problem

Cardona, G., Rossello, F., Valiente, G.: Comparison of tree-child phylogenetic networks. IEEE/ACM Trans. Comput. Biol. Bioinform. 6(4), 552–569 (2009)CrossRef

Doolittle, W.F.: Phylogenetic classification and the universal tree. Science 284, 2124–2128 (1999)CrossRef

Francis, A., Steel, M.: Which phylogenetic networks are merely trees with additional arcs? Syst. Biol. 64(5), 768–777 (2015)CrossRef

Gambette, P., Gunawan, A.D., Labarre, A., Vialette, S., Zhang, L.: Solving the tree containment problem in linear time for nearly stable phylogenetic networks. Discret. Appl. Math. 246, 62–79 (2018)MathSciNetCrossRef

Gunawan, A.D.M.: Solving the tree containment problem for reticulation-visible networks in linear time. In: Jansson, J., Martín-Vide, C., Vega-Rodríguez, M.A. (eds.) AlCoB 2018. LNCS, vol. 10849, pp. 24–36. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-91938-6_3CrossRef

Gunawan, A.D., DasGupta, B., Zhang, L.: A decomposition theorem and two algorithms for reticulation-visible networks. Inform. Comput. 252, 161–175 (2017)MathSciNetCrossRef

Gunawan, A.D., Lu, B., Zhang, L.: A program for verification of phylogenetic network models. Bioinformatics 32, i503–i510 (2016)CrossRef

Gunawan, A.D., Yan, H., Zhang, L.: Compression of phylogenetic networks and algorithm for the tree containment problem. J. Comput. Biol. 26, 285–294 (2019)MathSciNetCrossRef

Gusfield, D.: ReCombinatorics: The Algorithmics of Ancestral Recombination Graphs and Explicit Phylogenetic Networks. MIT Press, Boston (2014)CrossRef

10.

Gusfield, D., Eddhu, S., Langley, C.: The fine structure of galls in phylogenetic networks. INFORMS J. Comput. 16(4), 459–469 (2004)MathSciNetCrossRef

11.

Huson, D.H., Klöpper, T.H.: Beyond galled trees - decomposition and computation of galled networks. In: Speed, T., Huang, H. (eds.) RECOMB 2007. LNCS, vol. 4453, pp. 211–225. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-71681-5_15CrossRef

12.

Huson, D.H., Rupp, R., Scornavacca, C.: Phylogenetic Networks: Concepts Algorithms and Applications. Cambridge University Press, Cambridge (2010)CrossRef

13.

Steel, M.: Phylogeny: Discrete and Random Processes in Evolution. SIAM, Philadelphia (2016)CrossRef

14.

Wang, L., Zhang, K., Zhang, L.: Perfect phylogenetic networks with recombination. J. Comput. Biol. 8(1), 69–78 (2001)CrossRef

15.

Weller, M.: Linear-time tree containment in phylogenetic networks. In: Blanchette, M., Ouangraoua, A. (eds.) RECOMB-CG 2018. LNCS, vol. 11183, pp. 309–323. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-00834-5_18CrossRef

16.

Willson, S.J.: Unique determination of some homoplasies at hybridization events. Bull. Math. Biol. 69, 1709–1725 (2007)MathSciNetCrossRef

17.

Yan, H., Gunawan, A.D., Zhang, L.: S-cluster++: a fast program for solving the cluster containment problem for phylogenetic networks. Bioinformatics 34(17), i680–i686 (2018)CrossRef

18.

Zhang, L.: On tree-based phylogenetic networks. J. Comput. Biol. 23(7), 553–565 (2016)MathSciNetCrossRef

19.

Zhang, L.: Clusters, trees, and phylogenetic network classes. In: Warnow, T. (ed.) Bioinformatics and Phylogenetics. CB, vol. 29, pp. 277–315. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-10837-3_12CrossRef

20.

Zhang, L.: Generating normal networks via leaf insertion and nearest neighbor interchange. BMC Bioinform. 20, article no. 642 (2019)

21.

Zhang, L.: Counting tree-child networks and their subclasses. arXiv preprint arXiv:1908.01917 (2019)

Title: Recent Progresses in the Combinatorial and Algorithmic Study of Rooted Phylogenetic Networks
Author: Louxin Zhang
Publisher: Springer International Publishing
Book: WALCOM: Algorithms and Computation
Print ISBN: 978-3-030-39880-4

Electronic ISBN: 978-3-030-39881-1

Copyright Year: 2020
DOI: https://doi.org/10.1007/978-3-030-39881-1_3

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner