City Research Online

Robust, Universal Tree Balance Indices

Lemant, J., Le Sueur, C., Manojlović, V. & Noble, R. ORCID: 0000-0002-8057-4252 (2022). Robust, Universal Tree Balance Indices. Systematic Biology, doi: 10.1093/sysbio/syac027

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 normalised reciprocal of Sackin’s index. Hence we both unify and generalise the two most popular existing tree balance indices. Our indices are intrinsically normalised and can be computed in linear time. We conclude that these more widely applicable indices have potential to supersede those in current use.

Publication Type: Article
Additional Information: © The Author(s) 2022. Published by Oxford University Press, on behalf of the Society of Systematic Biologists. This is an Open Access article distributed under the terms of the Creative Commons Attribution Non-Commercial License (http://creativecommons.org/licenses/by-nc/4.0/), which permits non-commercial re-use, distribution, and reproduction in any medium, provided the original work is properly cited.
Publisher Keywords: Tree balance, Sackin index, Colless index, cancer, species tree, clone tree
Subjects: Q Science > QA Mathematics
Q Science > QH Natural history > QH426 Genetics
Q Science > QK Botany
Departments: School of Mathematics, Computer Science & Engineering > Mathematics
[img]
Preview
Text - Accepted Version
Available under License Creative Commons Attribution Non-commercial.

Download (1MB) | Preview

Export

Downloads

Downloads per month over past year

View more statistics

Actions (login required)

Admin Login Admin Login