colPlaLab {treebalance}

Calculation of the Colijn-Plazzotta rank for rooted binary trees

Description

This function calculates the Colijn-Plazzotta rank CP(T) for a given rooted binary tree T.

For a binary tree T, the Colijn-Plazzotta rank CP(T) is recursively defined as CP(T)=1 if T consists of only one leaf and otherwise

CP(T)=\frac{1}{2}\cdot CP(T_1)\cdot(CP(T_1)-1)+CP(T_2)+1

with CP(T_1) \geq CP(T_2) being the ranks of the two pending subtrees rooted at the children of the root of T. This rank of T corresponds to its position in the lexicographically sorted list of (i,j): (1),(1,1),(2,1),(2,2),(3,1),... The Colijn-Plazzotta rank of binary trees has been shown to be an imbalance index.

For n=1 the function returns CP(T)=1 and a warning.

Note that problems can sometimes arise even for trees with small leaf numbers due to the limited range of computable values (ranks can reach INF quickly).

For details on the Colijn-Plazzotta rank, see also Chapter 21 in "Tree balance indices: a comprehensive survey" (https://doi.org/10.1007/978-3-031-39800-1_21).

Usage

colPlaLab(tree)

Arguments

tree

A rooted binary tree in phylo format.

Value

colPlaLab returns the Colijn-Plazotta rank of the given tree. Since the values can get quite large, the function returns them in big.z format (package gmp).

Author(s)

Sophie Kersting, Luise Kuehn

References

C. Colijn and G. Plazzotta. A Metric on Phylogenetic Tree Shapes. Systematic Biology, doi: 10.1093/sysbio/syx046.

N. A. Rosenberg. On the Colijn-Plazzotta numbering scheme for unlabeled binary rooted trees. Discrete Applied Mathematics, 2021. doi: 10.1016/j.dam.2020.11.021.

Examples

tree <- ape::read.tree(text="((((,),),(,)),(((,),),(,)));")
colPlaLab(tree)