A simple derivation of the mean of the Sackin index of tree balance under the uniform model on rooted binary labeled trees. (English) Zbl 1480.92149
Summary: In mathematical phylogenetics, the Sackin index, measuring the sum of path lengths between leaves and the root, is one of the most frequently used measures of balance for phylogenetic trees. The uniform model, in which all rooted binary labeled trees for a given set of leaf labels are assumed to be equiprobable, is one of the most frequently used models for describing a probability distribution on the set of rooted binary labeled trees. This note provides a simple new derivation of the mean value of the Sackin index of tree balance under the uniform model on rooted binary labeled trees. The new derivation suggests a simple form of the mean Sackin index in terms of the Catalan numbers, quickly enabling a verification of the asymptotic value for the mean.
MSC:
| 92D15 | Problems related to evolution |
References:
| [1] | Mir, A.; Rosselló, F.; Rotger, L., A new balance index for phylogenetic trees, Math. Biosci., 241, 125-136 (2013) · Zbl 1303.92084 |
| [2] | Cardona, G.; Mir, A.; Rosselló, F.; Rotger, L., The expected value of the squared cophrenetic metric under the Yule and the uniform models, Math. Biosci., 295, 73-85 (2018) · Zbl 1380.92045 |
| [3] | Bartoszek, K.; Coronado, T. M.; Mir, A.; Rosselló, F., Squaring within the Colless index yields a better balance index, Math. Biosci., 331, Article 108503 pp. (2021) · Zbl 1457.92123 |
| [4] | Cardona, G.; Mir, A.; Rosselló, F., Exact formulas for the variances of several balance indices under the Yule model, J. Math. Biol., 67, 1833-1846 (2013) · Zbl 1281.92051 |
| [5] | Coronado, T. M.; Fischer, M.; Herbst, L.; Rosselló, F.; Wicke, K., On the minimum value of the Colless index and the bifurcating trees that achieve it, J. Math. Biol., 80, 1993-2054 (2020) · Zbl 1443.92126 |
| [6] | Coronado, T. M.; Mir, A.; Rosselló, F.; Rotger, L., On Sackin’s original proposal: the variance of the leaves’ depths as a phylogenetic balance index, BMC Bioinformatics, 21, 154 (2020) |
| [7] | Sackin, M., ’Good’ and ’bad’ phenograms, Syst. Zool., 21, 225-226 (1972) |
| [8] | Colless, D., Review of “Phylogenetics: the theory and practice of phylogenetic systematics”, Syst. Zool., 31, 100-104 (1982) |
| [9] | 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 |
| [10] | Heard, S. B., Patterns in tree balance among cladistic, phenetic, and randomly generated phylogenetic trees, Evolution, 46, 1818-1826 (1992) |
| [11] | Kirkpatrick, M.; Slatkin, M., Searching for evolutionary patterns in the shape of a phylogenetic tree, Evolution, 47, 1171-1181 (1993) |
| [12] | Rogers, J. S., Response of Colless’s tree imbalance to number of terminal taxa, Syst. Biol., 42, 102-105 (1993) |
| [13] | Rogers, J. S., Central moments and probability distribution of Colless’s coefficient of tree imbalance, Evolution, 48, 2026-2036 (1994) |
| [14] | Rogers, J. S., Central moments and probability distributions of three measures of phylogenetic tree imbalance, Syst. Biol., 45, 99-110 (1996) |
| [15] | 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 |
| [16] | Blum, M. G.B.; François, O.; Janson, S., The mean, variance and limiting distribution of two statistics sensitive to phylogenetic tree balance, Ann. Appl. Probab., 16, 2195-2214 (2006) · Zbl 1124.05025 |
| [17] | Aldous, D., Probability distributions on cladograms, (Aldous, D.; Pemantle, R., Random Discrete Structures (1996), Springer-Verlag: Springer-Verlag New York), 1-18 · Zbl 0841.92015 |
| [18] | Than, C. V.; Rosenberg, N. A., Mean deep coalescence cost under exchangeable probability distributions, Discrete Appl. Math., 174, 11-26 (2014) · Zbl 1297.92056 |
| [19] | Graham, R. L.; Knuth, D. E.; Patashnik, O., Concrete Mathematics (1994), Addison-Wesley: Addison-Wesley Boston · Zbl 0836.00001 |
| [20] | Fuchs, M.; Jin, E. Y., Equality of Shapley value and fair proportion index in phylogenetic trees, J. Math. Biol., 71, 1133-1147 (2015) · Zbl 1355.92074 |
| [21] | Chang, H.; Fuchs, M., Limit theorems for patterns in phylogenetic trees, J. Math. Biol., 60, 481-512 (2012) · Zbl 1311.92135 |
| [22] | Fill, J. A.; Kapur, N., Limiting distributions for additive functionals on Catalan trees, Theoret. Comput. Sci., 326, 69-102 (2004) · Zbl 1071.68102 |
| [23] | Sedgewick, R.; Flajolet, P., An Introduction To the Analysis of Algorithms (2013), Addison-Wesley: Addison-Wesley Upper Saddle River, NJ |
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.
