×

On the Colijn-Plazzotta numbering scheme for unlabeled binary rooted trees. (English) Zbl 1469.05033

Summary: C. Colijn and G. Plazzotta [“A metric on phylogenetic tree shapes”, Syst. Biol. 67, 113–126 (2018; doi:10.1093/sysbio/syx046)] introduced a scheme for bijectively associating the unlabeled binary rooted trees with the positive integers. First, the rank 1 is associated with the 1-leaf tree. Proceeding recursively, ordered pair \(( k_1 , k_2 )\), \(k_1 \geqslant k_2 \geqslant 1\), is then associated with the tree whose left subtree has rank \(k_1\) and whose right subtree has rank \(k_2\). Following dictionary order on ordered pairs, the tree whose left and right subtrees have the ordered pair of ranks \(( k_1 , k_2 )\) is assigned rank \(k_1 ( k_1 - 1 ) / 2 + 1 + k_2\). With this ranking, given a number of leaves \(n\), we determine recursions for \(a_n\), the smallest rank assigned to some tree with \(n\) leaves, and \(b_n\), the largest rank assigned to some tree with \(n\) leaves. The smallest rank \(a_n\) is assigned to the maximally balanced tree, and the largest rank \(b_n\) is assigned to the caterpillar. For \(n\) equal to a power of 2, the value of \(a_n\) is seen to increase exponentially with \(2 \alpha^n\) for a constant \(\alpha \approx 1 . 24602\); more generally, we show it is bounded \(a_n < 1 . 5^n\). The value of \(b_n\) is seen to increase with \(2 \beta^{( 2^n )}\) for a constant \(\beta \approx 1 . 05653\). The great difference in the rates of increase for \(a_n\) and \(b_n\) indicates that as the index \(v\) is incremented, the number of leaves for the tree associated with rank \(v\) quickly traverses a wide range of values. We interpret the results in relation to applications in evolutionary biology.

MSC:

05C05 Trees
05C30 Enumeration in graph theory
92D15 Problems related to evolution

References:

[1] Aho, A. V.; Sloane, N. J.A., Some doubly exponential sequences, Fibonacci Q., 11, 429-437 (1973) · Zbl 0277.10011
[2] Blum, M. G.B.; François, O., On statistical tests of phylogenetic tree imbalance: the Sackin and other indices revisited, Math. Biosci., 195, 141-153 (2005) · Zbl 1065.62183
[3] Cardona, G.; Mir, A.; Rosselló, F., Exact formulas for the variance of several balance indices under the Yule model, J. Math. Biol., 67, 1833-1846 (2013) · Zbl 1281.92051
[4] Colijn, C.; Plazzotta, G., A metric on phylogenetic tree shapes, Syst. Biol., 67, 113-126 (2018)
[5] Colless. Phylogenetics, D. H., The theory and practice of phylogenetic systematics, Syst. Zool., 31, 100-104 (1982)
[6] Coronado, T. M.; Fischer, M.; Herbst, L.; Rosselló, F.; Wicke, K., On the minimium value of the Colless index and the bifurcating trees that achieve it, J. Math. Biol., 80, 1993-2054 (2020) · Zbl 1443.92126
[7] Disanto, F.; Rosenberg, N. A., Enumeration of ancestral configurations for matching gene trees and species trees, J. Comput. Biol., 24, 831-850 (2017)
[8] Disanto, F.; Rosenberg, N. A., Enumeration of compact coalescent histories for matching gene trees and species trees, J. Math. Biol., 78, 155-188 (2019) · Zbl 1407.05129
[9] Disanto, F.; Rosenberg, N. A., On the number of non-equivalent ancestral configurations for matching gene trees and species trees, Bull. Math. Biol., 81, 384-407 (2019) · Zbl 1410.92072
[10] Felsenstein, J., Inferring Phylogenies (2004), Sinauer: Sinauer Sunderland, MA
[11] Furnas, G. W., The generation of random, binary unordered trees, J. Classification, 1, 187-233 (1984) · Zbl 0582.62052
[12] Heard, S. B., Patterns in tree balance among cladistic, phenetic, and randomly generated phylogenetic trees, Evolution, 46, 1818-1826 (1992)
[13] Mir, A.; Rosselló, F.; Rotger, L., A new balance index for phylogenetic trees, Math. Biosci., 241, 125-136 (2013) · Zbl 1303.92084
[14] Mir, A.; Rotger, L.; Rosselló, F., Sound Colless-like balance indices for multifurcating trees, PLoS One, 13, Article e0203401 pp. (2018)
[15] Steel, M., Phylogeny: Discrete and Random Processes in Evolution (2016), Society for Industrial and Applied Mathematics: Society for Industrial and Applied Mathematics Philadelphia · Zbl 1361.92001
[16] Wu, Y., Coalescent-based species tree inference from gene tree topologies under incomplete lineage sorting by maximum likelihood, Evolution, 66, 763-775 (2012)
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.