On Sackin's original proposal: the variance of the leaves' depths as a phylogenetic balance index

Abstract

Background: The Sackin indexS of a rooted phylogenetic tree, defined as the sum of its leaves' depths, is one of the most popular balance indices in phylogenetics, and Sackin's paper (Syst Zool 21:225-6, 1972) is usually cited as the source for this index. However, what Sackin actually proposed in his paper as a measure of the imbalance of a rooted tree was not the sum of its leaves' depths, but their variation. This proposal was later implemented as the variance of the leaves' depths by Kirkpatrick and Slatkin in (Evolution 47:1171-81, 1993), where they also posed the problem of finding a closed formula for its expected value under the Yule model. Nowadays, Sackin's original proposal seems to have passed into oblivion in the phylogenetics literature, replaced by the index bearing his name, which, in fact, was introduced a decade later by Sokal. Results: In this paper we study the properties of the variance of the leaves' depths, V, as a balance index. Firstly, we prove that the rooted trees with n leaves and maximum V value are exactly the combs with n leaves. But although V achieves its minimum value on every space & x212c;Tn of bifurcating rooted phylogenetic trees with n <= 183 leaves at the so-called maximally balanced trees with n leaves, this property fails for almost every n >= 184. We provide then an algorithm that finds the trees in & x212c;Tnwith minimum V value in time O(n log(n)). Secondly, we obtain closed formulas for the expected V value of a bifurcating rooted tree with any number n of leaves under the Yule and the uniform models and, as a by-product of the computations leading to these formulas, we also obtain closed formulas for the variance under the uniform model of the Sackin index and the total cophenetic index (Mir et al., Math Biosci 241:125-36, 2013) of a bifurcating rooted tree, as well as of their covariance, thus filling this gap in the literature. Conclusion: The phylogenetics community has been wise in preferring the sum S(T) of the leaves' depths of a phylogenetic tree T over their variance V(T) as a balance index, because the latter does not seem to capture correctly the notion of balance of large bifurcating rooted trees. But it is still a valid and useful shape index.