Open Access

Comparing the topology of phylogenetic network generators

Remie Janssen

Delft University of Technology, Delft Institute of Applied Mathematics, Mekelweg 4, 2628 CD, Delft, The Netherlands

E-mail Address: [email protected]

Search for more papers by this author

and

Pengyu Liu

Simon Fraser University, Department of Mathematics, 8888 University Drive, Burnaby, BC V5A 1S6, Canada

E-mail Address: [email protected]

Corresponding author.

Search for more papers by this author

https://doi.org/10.1142/S0219720021400126Cited by:8 (Source: Crossref)

This article is part of the issue:

Special Issue: Selected Papers from the 18th Annual International RECOMB Satellite Workshop on Comparative Genomics (RECOMB-CG)
Guest Editors: Rohan B. H. Williams and Louxin Zhang

Abstract

Phylogenetic networks represent evolutionary history of species and can record natural reticulate evolutionary processes such as horizontal gene transfer and gene recombination. This makes phylogenetic networks a more comprehensive representation of evolutionary history compared to phylogenetic trees. Stochastic processes for generating random trees or networks are important tools in evolutionary analysis, especially in phylogeny reconstruction where they can be utilized for validation or serve as priors for Bayesian methods. However, as more network generators are developed, there is a lack of discussion or comparison for different generators. To bridge this gap, we compare a set of phylogenetic network generators by profiling topological summary statistics of the generated networks over the number of reticulations and comparing the topological profiles.

Keywords:

References

1. Huson DH, Rupp R, Scornavacca C, Phylogenetic Networks: Concepts, Algorithms and Applications, Cambridge University Press, 2010. Crossref, Google Scholar
2. Elworth RL, Ogilvie HA, Zhu J, Nakhleh L, Advances in computational methods for phylogenetic networks in the presence of hybridization, in Bioinformatics and Phylogenetics, Springer, pp. 317–360, 2019. Crossref, Google Scholar
3. Blair C, Ané C, Phylogenetic trees and networks can serve as powerful and complementary approaches for analysis of genomic data, System Biol 69(3) :593–601, 2020. Crossref, Medline, Google Scholar
4. Blais C, Archibald JM, The past, present and future of the tree of life, Current Biol 31(7) :R314–R321, 2021. Crossref, Medline, Google Scholar
5. Bordewich M, Semple C, Determining phylogenetic networks from inter-taxa distances, J Math Biol 73(2) :283–303, 2016. Crossref, Medline, Google Scholar
6. Bordewich M et al., Recovering normal networks from shortest inter-taxa distance information, J. Math Biol 77(3) :571–594, 2018. Crossref, Medline, Google Scholar
7. van Iersel L, Moulton V, Murakami Y, Reconstructibility of unrooted level-k phylogenetic networks from distances, Adv Appl Math 120 :102075, 2020. Crossref, Google Scholar
8. Baroni M et al., Bounding the number of hybridisation events for a consistent evolutionary history, J Math Biol 51(2) :171–182, 2005. Crossref, Medline, Google Scholar
9. Linz S, Semple C, Attaching leaves and picking cherries to characterise the hybridisation number for a set of phylogenies, Adv Appl Math 105 :102–129, 2019. Crossref, Google Scholar
10. Whidden C, Beiko RG, Zeh N, Fixed-parameter algorithms for maximum agreement forests, SIAM J Comput 42(4) :1431–1466, 2013. Crossref, Google Scholar
11. van Iersel L, Janssen R, Jones M, Murakami Y, Zeh N, A practical fixed-parameter algorithm for constructing tree-child networks from multiple binary trees, arXiv:190708474. Google Scholar
12. van Iersel L, Janssen R, Jones M, Murakami Y, Zeh N, Polynomial-time algorithms for phylogenetic inference problems involving duplication and reticulation, IEEE/ACM Transac Comput Biol Bioinf 17(1) :14–26, 2019. Crossref, Google Scholar
13. Zhang C, Ogilvie HA, Drummond AJ, Stadler T, Bayesian inference of species networks from multilocus sequence data, Molecular Biol Evol 35(2) :504–517, 2018. Crossref, Medline, Google Scholar
14. Zhu J, Wen D, Yu Y, Meudt HM, Nakhleh L, Bayesian inference of phylogenetic networks from bi-allelic genetic markers, PLoS Comput Biol 14(1) :e1005932, 2018. Crossref, Medline, Google Scholar
15. Yu Y, Nakhleh L, A maximum pseudo-likelihood approach for phylogenetic networks, BMC Genom 16(10) :1–10, 2015. Medline, Google Scholar
16. Solís-Lemus C, Ané C, Inferring phylogenetic networks with maximum pseudolikelihood under incomplete lineage sorting, PLoS Gen 12(3) :e1005896, 2016. Crossref, Medline, Google Scholar
17. van Iersel L, Keijsper J, Kelk S, Stougie L, Hagen F, Boekhout T, Constructing level-2 phylogenetic networks from triplets, IEEE/ACM Trans Comput Biol Bioinf 6(4) :667–681, 2009. Crossref, Medline, Google Scholar
18. Pons JC, Scornavacca C, Cardona G, Generation of level-k lgt networks, IEEE/ACM Trans Comput Biol Bioinf 17(1) :158–164, 2019. Medline, Google Scholar
19. Harding EF, The probabilities of rooted tree-shapes generated by random bifurcation, Advances in Applied Probability 3(1) :44–77, 1971. Crossref, Google Scholar
20. Morin MM, Moret BM, Netgen: generating phylogenetic networks with diploid hybrids, Bioinformatics 22(15) :1921–1923, 2006. Crossref, Medline, Google Scholar
21. Zhang L, On tree-based phylogenetic networks, J Comput Biol 23(7) :553–565, 2016. Crossref, Medline, Google Scholar
22. Gambette P, van Iersel L, Jones M, Lafond M, Pardi F, Scornavacca C, Rearrangement moves on rooted phylogenetic networks, PLoS Comput Biol 13(8) :e1005611, 2017. Crossref, Medline, Google Scholar
23. Janssen R, Rearranging phylogenetic networks, Ph.D. thesis, Delft University of Technology, 2021. Google Scholar
24. Aldous D, Probability distributions on cladograms, in Random discrete structures, Springer, pp. 1–18, 1996. Crossref, Google Scholar
25. Heath TA, Zwickl DJ, Kim J, Hillis DM, Taxon sampling affects inferences of macroevolutionary processes from phylogenetic trees, System Biol 57(1) :160–166, 2008. Crossref, Medline, Google Scholar
26. Blum MG, François O, Which random processes describe the tree of life? a large-scale study of phylogenetic tree imbalance, System Biol 55(4) :685–691, 2006. Crossref, Medline, Google Scholar
27. Steel M, Phylogeny: Discrete and Random Processes in Evolution, SIAM, 2016. Crossref, Google Scholar
28. Liu P, Biller P, Gould M, Colijn C, Polynomial phylogenetic analysis of tree shapes, bioRxiv:2020. Google Scholar
29. Choi KP, Thompson A, Wu T, On cherry and pitchfork distributions of random rooted and unrooted phylogenetic trees, Theor. Population Biol 132 :92–104, 2020. Crossref, Medline, Google Scholar
30. Bienvenu F, Cardona G, Scornavacca C, Revisiting shao and sokal’s $b 2$ index of phylogenetic balance, arXiv:201008079. Google Scholar
31. Liu P, A tree distinguishing polynomial, Discrete Appl Math 288 :1–8, 2021. Crossref, Google Scholar
32. Francis A, Moulton V, Identifiability of tree-child phylogenetic networks under a probabilistic recombination-mutation model of evolution, J Theor Biol 446 :160–167, 2018. Crossref, Medline, Google Scholar
33. Lance GN, Williams WT, Computer programs for hierarchical polythetic classification (“Similarity Analyses”), Comput J 9(1) :60–64, 1966. Crossref, Google Scholar
34. Cox M, Cox M, Multidimensional Scaling, Chapman and Hall, 2001. Google Scholar
35. Kaufman L, Rousseeuw PJ, Finding Groups in Data: An Introduction to Cluster Analysis, Hoboken, New Jersey: John Wiley & Sons, Inc., 2009. Google Scholar
36. Bryant D, Tupper PF, Hyperconvexity and tight-span theory for diversities, Adv Math 231(6) :3172–3198, 2012. Crossref, Google Scholar
37. Morando M et al., Phylogenomic data resolve higher-level relationships within south american liolaemus lizards, Molecul Phylogen Evol 147 :106781, 2020. Crossref, Medline, Google Scholar
38. Yang W et al., Extensive introgression and mosaic genomes of mediterranean endemic lizards, Nat Commun 12(1) :1–8, 2021. Medline, Google Scholar
39. Cuypers T, Hogeweg P, Endless evolutionary paths to virtual microbes, Workshop, First EvoEvo Workshop, Satellite Workshop of ECAL2015, 2015. Google Scholar
40. van Dijk B, Cuypers T, Hogeweg P, Evolution of r-and k-selected species of virtual microbes: A case study in a simple fluctuating 2-resource environment, 2nd EvoEvo Workshop, Satellite Workshop of CCS2016, 2016. Google Scholar
41. van Dijk B, Hogeweg P, Doekes HM, Takeuchi N, Slightly beneficial genes are retained by bacteria evolving dna uptake despite selfish elements, Elife 9 :e56801, 2020. Crossref, Medline, Google Scholar
42. Wen D, Yu Y, Nakhleh L, Bayesian inference of reticulate phylogenies under the multispecies network coalescent, PLoS Gen 12(5) :e1006006, 2016. Crossref, Medline, Google Scholar
43. Bordewich M, Linz S, Semple C, Lost in space? generalising subtree prune and regraft to spaces of phylogenetic networks, J Theo Biol 423 :1–12, 2017. Crossref, Medline, Google Scholar
44. Klawitter J, Spaces of phylogenetic networks, Ph.D. thesis, University of Auckland, in preparation, 2020. Google Scholar
45. Shao KT, Tree balance, System Zool 39(3) :266–276, 1990. Google Scholar
46. Gusfield D, Bansal V, A fundamental decomposition theory for phylogenetic networks and incompatible characters, Ann Int Conf Res Comput Molecul Biol, Springer, pp. 217–232, 2005. Crossref, Google Scholar
47. Francis AR, Steel M, Which phylogenetic networks are merely trees with additional arcs?, System Biol 64(5) :768–777, 2015. Crossref, Medline, Google Scholar
48. Janssen R, Murakami Y, On cherry-picking and network containment, Theor Comput Sci 856 :121–150, 2021. Crossref, Google Scholar
49. Erdős PL, Semple C, Steel M, A class of phylogenetic networks reconstructable from ancestral profiles, Math Biosci 313 :33–40, 2019. Crossref, Medline, Google Scholar
50. Semple C, Simpson J, When is a phylogenetic network simply an amalgamation of two trees?, Bull Math Biol 80(9) :2338–2348, 2018. Crossref, Medline, Google Scholar
51. Cardona G, Rosselló F, Valiente G, Comparison of tree-child phylogenetic networks, IEEE/ACM Trans Comput Biol Bioinf 6(4) :552–569, 2008. Crossref, Google Scholar
52. Huber KT, van Iersel L, Janssen R, Jones M, Moulton V, Murakami Y, Semple C, Rooting for phylogenetic networks, arXiv:190607430. Google Scholar
53. van Iersel L, Janssen R, Jones M, Murakami Y, Zeh N, A unifying characterization of tree-based networks and orchard networks using cherry covers, arXiv:200407677. Google Scholar
54. Sainudiin R, Véber A, A beta-splitting model for evolutionary trees, Roy Soc Open Sci 3(5): 160016, 2016. Crossref, Medline, Google Scholar
55. Janssen R, Jones M, Erdős PL, van Iersel L, Scornavacca C, Exploring the tiers of rooted phylogenetic network space using tail moves, Bull Math Biol 80(8) :2177–2208, 2018. Crossref, Medline, Google Scholar

Vol. 19, No. 06

Metrics

History

Received 5 September 2021

Accepted 20 September 2021

Published: 6 December 2021

Information

This is an Open Access article published by World Scientific Publishing Company. It is distributed under the terms of the Creative Commons Attribution 4.0 (CC BY) License which permits use, distribution and reproduction in any medium, provided the original work is properly cited.

Keywords

PDF download

System Upgrade on Tue, May 28th, 2024 at 2am (EDT)

Comparing the topology of phylogenetic network generators

Abstract

References

Recommended