Robust, Universal Tree Balance Indices

Jeanne Lemant; Cécile Le Sueur; Veselin Manojlović; Robert Noble

doi:10.1093/sysbio/syac027

journal article Open Access Apr 12, 2022

Robust, Universal Tree Balance Indices

Jeanne Lemant

Cécile Le Sueur Veselin Manojlović Robert Noble

Systematic Biology Vol. 71 No. 5 pp. 1210-1224 · Oxford University Press (OUP)

View at Publisher Save 10.1093/sysbio/syac027

Abstract

Abstract
Balance indices that quantify the symmetry of branching events and the compactness of trees are widely used to compare evolutionary processes or tree-generating algorithms. Yet, existing indices are not defined for all rooted trees, are unreliable for comparing trees with different numbers of leaves, and are sensitive to the presence or absence of rare types. The contributions of this article are twofold. First, we define a new class of robust, universal tree balance indices. These indices take a form similar to Colless’ index but can account for population sizes, are defined for trees with any degree distribution, and enable meaningful comparison of trees with different numbers of leaves. Second, we show that for bifurcating and all other full m-ary cladograms (in which every internal node has the same out-degree), one such Colless-like index is equivalent to the normalized reciprocal of Sackin’s index. Hence, we both unify and generalize the two most popular existing tree balance indices. Our indices are intrinsically normalized and can be computed in linear time. We conclude that these more widely applicable indices have the potential to supersede those in current use. [Cancer; clone tree; Colless index; Sackin index; species tree; tree balance.]

Topics

No keywords indexed for this article. Browse by subject →

References

23

[1]

Agapow "Power of eight tree shape statistics to detect nonrandom diversification: a comparison by simulation of two models of cladogenesis" Syst. Biol. (2002) 10.1080/10635150290102564

[2]

Blum "The mean, variance and limiting distribution of two statistics sensitive to phylogenetic tree balance" Ann. Appl. Prob. (2006) 10.1214/105051606000000547

[3]

Chao "Unifying species diversity, phylogenetic diversity, functional diversity, and related similarity and differentiation measures through hill numbers" Annu. Rev. Ecol. Evol. Syst. (2014) 10.1146/annurev-ecolsys-120213-091540

[4]

Chen "A new family of Markov branching trees: the alpha-gamma model" Electron. J. Prob. (2009) 10.1214/ejp.v14-616

[5]

Chkhaidze "Spatially constrained tumour growth affects the patterns of clonal selection and neutral drift in cancer genomic data" PLoS Comput. Biol. (2019) 10.1371/journal.pcbi.1007243

[6]

Colless "Review of phylogenetics: the theory and practice of phylogenetic systematics" Syst. Zool. (1982) 10.2307/2413420

[7]

Davis "Tumor evolution: linear, branching, neutral or punctuated?" Biochim. Biophys. Acta (2017)

[8]

Fischer "Tree balance indices: a comprehensive survey" (2021)

[9]

Tracking the Evolution of Non–Small-Cell Lung Cancer

Mariam Jamal-Hanjani, Gareth A. Wilson, Nicholas McGranahan et al.

New England Journal of Medicine 2017 10.1056/nejmoa1616288

[10]

King "A simple derivation of the mean of the Sackin index of tree balance under the uniform model on rooted binary labeled trees" Math. Biosci. (2021) 10.1016/j.mbs.2021.108688

[11]

Kirkpatrick "Searching for evolutionary patterns in the shape of a phylogenetic tree" Evolution (1993) 10.2307/2409983

[12]

Maley "Classifying the evolutionary and ecological features of neoplasms" Nat. Rev. Cancer (2017) 10.1038/nrc.2017.69

[13]

A new balance index for phylogenetic trees

Arnau Mir, Francesc Rosselló, Lucı´a Rotger

Mathematical Biosciences 2013 10.1016/j.mbs.2012.10.005

[14]

Mir "Sound Colless-like balance indices for multifurcating trees" PLoS One (2018) 10.1371/journal.pone.0203401

[15]

Mooers "Inferring evolutionary process from phylogenetic tree shape" Q. Rev. Biol. (1997) 10.1086/419657

[16]

Noble "RUtreebalance: robust, universal tree balance indices" (2021)

[17]

Noble "Spatial structure governs the mode of tumour evolution" Nat. Ecol. Evol. (2022) 10.1038/s41559-021-01615-9

[18]

Podani "Tree thinking, time and topology: comments on the interpretation of tree diagrams in evolutionary/phylogenetic systematics" Cladistics (2013) 10.1111/j.1096-0031.2012.00423.x

[19]

Rényi "On measures of entropy and information" Proceedings of the Fourth Berkeley Symposium on Mathematical Statistics and Probability (1961)

[20]

"Good" and "Bad" Phenograms

M. J. Sackin

Systematic Biology 1972 10.1093/sysbio/21.2.225

[21]

Scott "Inferring tumor proliferative organization from phylogenetic tree measures in a computational model" Syst. Biol. (2020) 10.1093/sysbio/syz070

[22]

Shao "Tree balance" Syst. Zool. (1990)

[23]

Turajlic "Deterministic evolutionary trajectories influence primary tumor growth: TRACERx renal" Cell (2018) 10.1016/j.cell.2018.03.043

Metrics

24

Citations

23

References

Details

Published: Apr 12, 2022
Vol/Issue: 71(5)
Pages: 1210-1224
License: View

Authors

J

Jeanne Lemant

ETH Zurich Department of Biosystems Science and Engineering, , Mattenstrasse 26, 4058 Basel, Switzerland; Swiss Tropical and Public Health Institute Department of Epidemiology and Public Health, , Kreuzstrasse 2, 4123 Allschwil, Switzerland; University of Basel , Petersplatz 1, 4001 Basel, Switzerland

C

Cécile Le Sueur

ETH Zurich Department of Biosystems Science and Engineering, , Mattenstrasse 26, 4058 Basel, Switzerland

V

Veselin Manojlović

University of London Department of Mathematics, City, , Northampton Square, London EC1V 0HB, UK

R

Robert Noble

ETH Zurich Department of Biosystems Science and Engineering, , Mattenstrasse 26, 4058 Basel, Switzerland; University of London Department of Mathematics, City, , Northampton Square, London EC1V 0HB, UK

Funding

National Institutes of Health

NIH

Cite This Article

Jeanne Lemant, Cécile Le Sueur, Veselin Manojlović, et al. (2022). Robust, Universal Tree Balance Indices. Systematic Biology, 71(5), 1210-1224. https://doi.org/10.1093/sysbio/syac027

Robust, Universal Tree Balance Indices

You May Also Like