Counting phylogenetic networks with few reticulation vertices: tree-child and normal networks. (English) Zbl 1411.05240
Summary: In recent decades, phylogenetic networks have become a standard tool in modeling evolutionary processes. Nevertheless, basic combinatorial questions about them are still largely open. For instance, even the asymptotic counting problem for the class of phylogenetic networks and subclasses is unsolved. In this paper, we propose a method based on generating functions to count networks with few reticulation vertices for two subclasses which are important in applications: tree-child networks and normal networks. In particular, our method can be used to completely solve the asymptotic counting problem for these network classes when the number of reticulation vertices remains fixed while the network size tends to infinity.
MSC:
| 05C82 | Small world graphs, complex networks (graph-theoretic aspects) |
| 05C90 | Applications of graph theory |
| 92D15 | Problems related to evolution |
Keywords:
evolutionary processes modelingReferences:
| [1] | N. Alexeev and M. A. Alekseyev, Combinatorial scoring of phylogenetic networks, In Computing and Combinatorics, Lec. Notes in Comp. Sci. Vol. 9797, Springer, [Cham], 2016, 560-572. · Zbl 1480.92140 |
| [2] | E. A. Bender, L. B. Richmond, R. W. Robinson and N. C. Wormald, The asymptotic number of acyclic digraphs I, Combinatorica 6 (1) (1986), 15-22. · Zbl 0601.05025 |
| [3] | E. A. Bender and R. W. Robinson, The asymptotic number of acyclic digraphs II, J. Combin. Theory Ser. B 44 (3) (1988), 363-369. · Zbl 0654.05035 |
| [4] | M. B´ona, On the number of vertices of each rank in k-phylogenetic trees, Discrete Math. Theor. Comput. Sci. 18 (3) (2016), Paper No. 7. · Zbl 1400.05118 |
| [5] | M. B´ona and P. Flajolet, Isomorphism and symmetries in random phylogenetic trees, J. Appl. Probab. 46 (4) (2009), 1005-1019. · Zbl 1231.60009 |
| [6] | M. Bordewich, S. Linz and C. Semple, Lost in space? Generalising subtree prune and regraft to spaces of phylogenetic networks, J. Theoret. Biol. 423 (2017), 1-12. · Zbl 1370.92100 |
| [7] | M. Bordewich and C. Semple, Determining phylogenetic networks from inter-taxa distances, J. Math. Biol. 73 (2) (2016), 283-303. · Zbl 1343.05147 |
| [8] | M. Bordewich and C. Semple, Reticulation-visible networks, Adv. in Appl. Math. 78 (2016), 114-141. · Zbl 1335.05170 |
| [9] | G. Cardona, F. Rossello and G. Valiente, Comparison of tree-child phylogenetic networks, IEEE/ACM Trans. Comput. Biol. Bioinform. 6 (2009), 552-569. |
| [10] | Z.-Z. Chen and L. Wang, Algorithms for reticulate networks of multiple phylogenetic trees, IEEE/ACM Trans. Comput. Biol. Bioinform. 9 (2) (2012), 372-384. |
| [11] | P. Cordue, S. Linz and C. Semple, Phylogenetic networks that display a tree twice, Bull. Math. Biol. 76 (10) (2014), 2664-2679. · Zbl 1330.92085 |
| [12] | ´E. Czabarka, P. L. Erd˝os, V. Johnson and V. Moulton, Generating functions for multi-labeled trees, Discrete Appl. Math. 161 (1-2) (2013), 107-117. · Zbl 1255.05044 |
| [13] | F. Disanto and N. A. Rosenberg, Enumeration of ancestral configurations for matching gene trees and species trees, J. Comput. Biol. 24 (9) (2017), 831-850. |
| [14] | P. Flajolet and A. Odlyzko, The average height of binary trees and other simple trees, J. Comput. System Sci. 25 (2) (1982), 171-213. · Zbl 0499.68027 |
| [15] | P. Flajolet and A. Odlyzko, Singularity analysis of generating functions, SIAM J. Discrete Math. 3 (2) (1990), 216-240. · Zbl 0712.05004 |
| [16] | P. Flajolet and H. Prodinger, Register allocation for unary-binary trees, SIAM J. Comput. 15 (3) (1986), 629-640. · Zbl 0612.68065 |
| [17] | P. Flajolet and R. Sedgewick, Analytic Combinatorics, Cambridge University Press, Cambridge, 2009. · Zbl 1165.05001 |
| [18] | P. Flajolet and J.-M. Steyaert,On the analysis of tree-matching algorithms,In Automata, Languages and Programming (Proc. Seventh Internat. Colloq., Noordwijkerhout, 1980), Lec. Notes in Comp. Sci. Vol. 85, Springer, Berlin-New York, 1980, 208-219. · Zbl 0444.68054 |
| [19] | L. R. Foulds and R. W. Robinson, Determining the asymptotic number of phylogenetic trees,In Combinatorial Mathematics VII (Proc. Seventh Australian Conf., Univ. Newcastle, Newcastle, 1979), Lec. Notes in Math. Vol. 829, Springer, Berlin, 1980, 110-126. · Zbl 0444.05046 |
| [20] | L. R. Foulds and R. W. Robinson, Enumerating phylogenetic trees with multiple labels, In Proceedings of the First Japan Conference on Graph Theory and Applications (Hakone, 1986), Vol. 72, 1988, 129-139. · Zbl 0661.05023 |
| [21] | A. R. Francis and M. Steel, Tree-like reticulation networks—when do tree-like distances also support reticulate evolution?, Math. Biosci. 259 (2015), 12-19. · Zbl 1315.92053 |
| [22] | S. Kelk and C. Scornavacca, Constructing minimal phylogenetic networks from softwired clusters is fixed parameter tractable, Algorithmica 68 (4) (2014), 886-915. · Zbl 1350.92036 |
| [23] | S. Linz, K. St. John and C. Semple, Counting trees in a phylogenetic network is #P-complete, SIAM J. Comput. 42 (4) (2013), 1768-1776. · Zbl 1276.05028 |
| [24] | V. A. Liskovec, The number of maximal vertices of a random acyclic digraph, Teor. Verojatnost. i Primenen. 20 (2) (1975), 412-421. · Zbl 0362.60030 |
| [25] | C. McDiarmid, C. Semple and D. Welsh, Counting phylogenetic networks, Ann. Comb. 19 (1) (2015), 205-224. · Zbl 1310.05120 |
| [26] | B. D. McKay, On the shape of a random acyclic digraph, Math. Proc. Cambridge Philos. Soc. 106 (3) (1989), 459-465. · Zbl 0702.05040 |
| [27] | R. W. Robinson, Counting labeled acyclic digraphs, In Directions in the Theory of Graphs (Ed. F. Harary), Academic Press, New York, 1973, 239-273. · Zbl 0259.05116 |
| [28] | R. W. Robinson, Counting unlabeled acyclic digraphs, In Combinatorial Mathematics V (Ed. C.H.C. Little), Lec. Notes in Math. Vol. 622, Springer, Berlin, Heidelberg, 1977, 28-43. · Zbl 0376.05031 |
| [29] | V. I. Rodionov, On the number of labeled acyclic digraphs, Discrete Math. 105 (1-3) (1992), 319-321. · Zbl 0761.05050 |
| [30] | N. A. Rosenberg, Counting coalescent histories, J. Comput. Biol. 14 (3) (2007), 360- 377. |
| [31] | E. Schr¨oder, Vier kombinatorische Probleme, Z. Math. Phys. 15 (1870), 361-376. · JFM 02.0108.04 |
| [32] | C. Semple, Phylogenetic networks with every embedded phylogenetic tree a base tree, Bull. Math. Biol. 78 (1) (2016), 132-137. · Zbl 1356.92067 |
| [33] | C. Semple, Size of a phylogenetic network, Discrete Appl. Math. 217 (2) (2017), 362-367. · Zbl 1358.05266 |
| [34] | C. Semple and M. Steel,Unicyclic networks:compatibility and enumeration, IEEE/ACM Trans. Comput. Biology Bioinform. 3 (2016), 84-91. |
| [35] | L. van Iersel, S. Kelk and C. Scornavacca, Kernelizations for the hybridization number problem on multiple nonbinary trees, J. Comput. System Sci. 82 (6) (2016), 1075- 1089. · Zbl 1342.68170 |
| [36] | S. J. Willson, Properties of normal phylogenetic networks, Bull. Math. Biol. 72 (2) (2010), 340-358. · Zbl 1185.92085 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
