On the minimum value of the Colless index and the bifurcating trees that achieve it

Tomás M. Coronado, Mareike Fischer, Lina Herbst, Francesc Rosselló, Kristina Wicke

Research output: Contribution to journalArticlepeer-review

9 Scopus citations

Abstract

Measures of tree balance play an important role in the analysis of phylogenetic trees. One of the oldest and most popular indices in this regard is the Colless index for rooted bifurcating trees, introduced by Colless (Syst Zool 31:100–104, 1982). While many of its statistical properties under different probabilistic models for phylogenetic trees have already been established, little is known about its minimum value and the trees that achieve it. In this manuscript, we fill this gap in the literature. To begin with, we derive both recursive and closed expressions for the minimum Colless index of a tree with n leaves. Surprisingly, these expressions show a connection between the minimum Colless index and the so-called Blancmange curve, a fractal curve. We then fully characterize the tree shapes that achieve this minimum value and we introduce both an algorithm to generate them and a recurrence to count them. After focusing on two extremal classes of trees with minimum Colless index (the maximally balanced trees and the greedy from the bottom trees), we conclude by showing that all trees with minimum Colless index also have minimum Sackin index, another popular balance index.

Original languageEnglish (US)
Pages (from-to)1993-2054
Number of pages62
JournalJournal of Mathematical Biology
Volume80
Issue number7
DOIs
StatePublished - Jun 1 2020
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Modeling and Simulation
  • Agricultural and Biological Sciences (miscellaneous)
  • Applied Mathematics

Keywords

  • Blancmange curve
  • Colless index
  • Phylogenetic tree
  • Sackin index
  • Takagi curve
  • Tree balance

Fingerprint

Dive into the research topics of 'On the minimum value of the Colless index and the bifurcating trees that achieve it'. Together they form a unique fingerprint.

Cite this