×

Enumeration of rooted binary unlabeled galled trees. (English) Zbl 1533.92145

Summary: Rooted binary galled trees generalize rooted binary trees to allow a restricted class of cycles, known as galls. We build upon the Wedderburn-Etherington enumeration of rooted binary unlabeled trees with \(n\) leaves to enumerate rooted binary unlabeled galled trees with \(n\) leaves, also enumerating rooted binary unlabeled galled trees with \(n\) leaves and \(g\) galls, \(0 \leq g \leq \lfloor \frac{n-1}{2} \rfloor\). The enumerations rely on a recursive decomposition that considers subtrees descended from the nodes of a gall, adopting a restriction on galls that amounts to considering only the rooted binary normal unlabeled galled trees in our enumeration. We write an implicit expression for the generating function encoding the numbers of trees for all \(n\). We show that the number of rooted binary unlabeled galled trees grows with \(0.0779(4.8230^n) n^{-\frac{3}{2}}\), exceeding the growth \(0.3188(2.4833^n) n^{-\frac{3}{2}}\) of the number of rooted binary unlabeled trees without galls. However, the growth of the number of galled trees with only one gall has the same exponential order \(2.4833\) as the number with no galls, exceeding it only in the subexponential term, \(0.3910n^{\frac{1}{2}}\) compared to \(0.3188n^{-\frac{3}{2}}\). For a fixed number of leaves \(n\), the number of galls \(g\) that produces the largest number of rooted binary unlabeled galled trees lies intermediate between the minimum of \(g=0\) and the maximum of \(g=\lfloor \frac{n-1}{2}\rfloor\). We discuss implications in mathematical phylogenetics.

MSC:

92D15 Problems related to evolution
05C05 Trees

References:

[1] Bienvenu, F.; Lambert, A.; Steel, M., Combinatorial and stochastic properties of ranked tree-child networks, Random Struct Algorithms, 60, 653-689, 2022 · Zbl 1526.92034 · doi:10.1002/rsa.21048
[2] Bouvel, M.; Gambette, P.; Mansouri, M., Counting phylogenetic networks of level 1 and 2, J Math Biol, 81, 1357-1395, 2020 · Zbl 1455.05006 · doi:10.1007/s00285-020-01543-5
[3] Cardona, G.; Zhang, L., Counting and enumerating tree-child networks and their subclasses, J Comput Syst Sci, 114, 84-104, 2020 · Zbl 1448.92147 · doi:10.1016/j.jcss.2020.06.001
[4] Chang K-Y, Hon W-K, Thankachan SV (2018) Compact encoding for galled-trees and its applications. In: 2018 Data Compression Conference, Snowbird, UT, pp 297-306
[5] Colijn, C.; Plazzotta, G., A metric on phylogenetic tree shapes, Syst Biol, 67, 113-126, 2018 · doi:10.1093/sysbio/syx046
[6] Comtet, L., Advanced combinatorics, 1974, Boston: Reidel, Boston · Zbl 0283.05001 · doi:10.1007/978-94-010-2196-8
[7] Drmota, M., Random trees, 2009, Vienna: Springer, Vienna · Zbl 1170.05022 · doi:10.1007/978-3-211-75357-6
[8] Felsenstein, J., Inferring phylogenies, 2004, Sunderland, MA: Sinauer, Sunderland, MA
[9] Flajolet, P.; Sedgewick, R., Analytic combinatorics, 2009, Cambridge: Cambridge University Press, Cambridge · Zbl 1165.05001 · doi:10.1017/CBO9780511801655
[10] Fuchs, M.; Gittenberger, B.; Mansouri, M., Counting phylogenetic networks with few reticulation vertices: tree-child and normal networks, Australas J Comb, 73, 385-423, 2019 · Zbl 1411.05240
[11] Fuchs, M.; Huang, E-Y; Yu, G-R, Counting phylogenetic networks with few reticulation vertices: a second approach, Discr Appl Math, 320, 140-149, 2022 · Zbl 1498.92131 · doi:10.1016/j.dam.2022.03.026
[12] Gascuel, O., Mathematics of evolution and phylogeny, 2005, Oxford: Oxford University Press, Oxford · Zbl 1104.92332 · doi:10.1093/oso/9780198566106.001.0001
[13] Gunawan, AD; Rathin, J.; Zhang, L., Counting and enumerating galled networks, Discrete Appl Math, 283, 644-654, 2020 · Zbl 1442.05093 · doi:10.1016/j.dam.2020.03.005
[14] Gusfield, D., Optimal, efficient reconstruction of root-unknown phylogenetic networks with constrained and structured recombination, J Comput Syst Sci, 70, 381-398, 2005 · Zbl 1068.92035 · doi:10.1016/j.jcss.2004.12.009
[15] Gusfield, D., ReCombinatorics, 2014, Cambridge: MIT Press, Cambridge · doi:10.7551/mitpress/9432.001.0001
[16] Gusfield D, Eddhu S, Langley C (2003) Efficient reconstruction of phylogenetic networks with constrained recombination. In: Computational Systems Bioinformatics, CSB2003. Proceedings of the 2003 IEEE Bioinformatics Conference, Stanford, CA, pp 363-374
[17] Gusfield D, Eddhu S, Langley C (2004a) The fine structure of galls in phylogenetic networks. INFORMS J Comput 16:459-469 · Zbl 1402.92313
[18] Gusfield D, Eddhu S, Langley C (2004b) Optimal, efficient reconstruction of phylogenetic networks with constrained recombination. J Bioinform Comput Biol 2:173-213
[19] Harding, EF, The probabilities of rooted tree-shapes generated by random bifurcation, Adv Appl Prob, 3, 44-77, 1971 · Zbl 0241.92012 · doi:10.2307/1426329
[20] Huson, DH; Rupp, R.; Scornavacca, C., Phylogenetic networks: concepts, algorithms and applications, 2010, Cambridge: Cambridge University Press, Cambridge · doi:10.1017/CBO9780511974076
[21] Kong, S.; Pons, JC; Kubatko, L.; Wicke, K., Classes of explicit phylogenetic networks and their biological and mathematical significance, J Math Biol, 84, 47, 2022 · Zbl 1491.92088 · doi:10.1007/s00285-022-01746-y
[22] Landau, BV, An asymptotic expansion for the Wedderburn-Etherington sequence, Mathematika, 24, 262-265, 1977 · Zbl 0365.05008 · doi:10.1112/S0025579300009177
[23] Mathur, S.; Rosenberg, NA, All galls are divided into three or more parts: recursive enumeration of labeled histories for galled trees, Algorithms Mol Biol, 18, 1, 2023 · doi:10.1186/s13015-023-00224-4
[24] Matsen, FA; Evans, SN, Ubiquity of synonymity: almost all large binary trees are not uniquely identified by their spectra or their immanantal polynomials, Algorithms Mol Biol, 7, 14, 2012 · doi:10.1186/1748-7188-7-14
[25] Meir, A.; Moon, JW, On an asymptotic method in enumeration, J Comb Theory Ser A, 51, 77-89, 1989 · Zbl 0683.05001 · doi:10.1016/0097-3165(89)90078-2
[26] Meir, A.; Moon, JW, Erratum: on an asymptotic method in enumeration, J Comb Theory Ser A, 52, 163, 1989 · Zbl 0709.05010 · doi:10.1016/0097-3165(89)90071-X
[27] Rosenberg, NA, On the Colijn-Plazzotta numbering scheme for unlabaled binary rooted trees, Discrete Appl Math, 291, 88-98, 2021 · Zbl 1469.05033 · doi:10.1016/j.dam.2020.11.021
[28] Semple, C.; Steel, M., Phylogentics, 2003, Oxford: Oxford University Press, Oxford · Zbl 1043.92026 · doi:10.1093/oso/9780198509424.001.0001
[29] Semple, C.; Steel, M., Unicyclic networks: compatibility and enumeration, IEEE/ACM Trans Comput Biol Bioinform, 3, 84-91, 2006 · doi:10.1109/TCBB.2006.14
[30] Sievers, F.; Hughes, GM; Higgins, DG, Systematic exploration of guide-tree topology effects for small protein alignments, BMC Bioinform, 15, 338, 2014 · doi:10.1186/1471-2105-15-338
[31] Song, YS, A concise necessary and sufficient condition for the existence of a galled-tree, IEEE/ACM Trans Comput Biol Bioinform, 3, 186-191, 2006 · doi:10.1109/TCBB.2006.15
[32] Steel, M., Phylogeny: discrete and random processes in evolution, 2016, Philadelphia: Society for Industrial and Applied Mathematics, Philadelphia · Zbl 1361.92001 · doi:10.1137/1.9781611974485
[33] Wang, L.; Zhang, K.; Zhang, L., Perfect phylogenetic networks with recombination, J Comput Biol, 8, 69-78, 2001 · doi:10.1089/106652701300099119
[34] Warnow, T., Computational phylogenetics, 2018, Cambridge: Cambridge University Press, Cambridge
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.