Robust, Universal Tree Balance Indices

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.].

Figure 1.

Contrasting trees. a) Caterpillar tree with , , , , , . b) Fully symmetric bifurcating tree with , , , , . c) Star tree with , , and undefined, . d) Clone tree of the lung tumor CRUK0065 in the TRACERx cohort (Jamal-Hanjani et al. 2017). In the clone tree, nodes represented by empty circles correspond to extinct clones, and the diameters of other nodes are proportional to the corresponding clone population sizes.

Figure 2.

Muller plots (left column), taxon or clone trees (middle column), and cladograms (right column) representing evolution by splitting only (a) and both splitting and budding (b). In a Muller plot, polygons represent proportional subpopulation sizes (vertical axis) over time (horizontal axis), and each descendant is shown emerging from its parent polygon. In the trees, nodes represented by empty circles correspond to extinct types.

Figure 3.

a) A tree in which each internal node has null size and splits its descendants into subtrees of equal magnitude, and hence . This tree can be considered balanced only according to an index that accounts for node size. b) A linear tree, for which . c–e) A robust, universal tree balance index is insensitive to the addition of a subtree of arbitrarily small magnitude if it is added to a leaf (a) or a nonroot node with out-degree 1 (b), but not necessarily if the subtree is added to a nonroot node with greater out-degree (c).

Figure 4.

a) An example calculation of . Numbers shown inside nodes are the node sizes. b) All multifurcating leafy trees on six leaves without linear parts and with equally sized leaves, sorted and labelled by value.

Figure 5.

a) values for caterpillar trees and random trees generated from the Yule and uniform models (1000 trees per data point). All internal nodes have null size and all leaves have equal size. Solid black curves are the means; dashed curves are the 5th and 95th percentiles; and gray curves are divided by the corresponding expectation of (where is the number of leaves). b) distributions for random trees on 64 leaves generated from the Yule and uniform models (1000 trees per model). c) values for 100 random trees on 16 leaves, before and after applying a 1 sensitivity threshold. These random trees were generated from the alpha-gamma model with and . d) values for the same set of random trees. e) Absolute change in normalized index values due to applying a 1 sensitivity threshold. Results are based on 100 random trees for each number of leaves, generated as in (c) and (d). here is the Colless-like index with and is the mean deviation from the median, as recommended by Mir et al. (2018). f) Values of versus for random multifurcating trees on 16 leaves, with node sizes drawn from a continuous uniform distribution. The dashed reference line has slope 1.

Figure 6.

Example values of versus the conservative tree balance index . The latter index takes account of the size of each internal node, relative to the sum of its descendant node sizes.

Figure 7.

Scatter plots of versus normalized Sackin’s, Colless-like, and total cophenetic indices for 2000 random multifurcating leafy trees with 100 equally sized leaves. Histograms in the margins show the marginal distributions. Dashed reference curves in the first panel are obtained by substituting into Equation 6 with and (upper curve) or (lower curve). We use the Colless-like index with and the mean deviation from the median, as recommended by Mir et al. (2018). Normalization of each index other than depends only on the number of leaves and so does not affect correlations. Trees were generated from the alpha-gamma model with and .