colPlaLab: Calculation of the Colijn-Plazzotta rank for rooted trees

Description Usage Arguments Value Author(s) References Examples

View source: R/colPlaLab.R

Description

This function calculates the Colijn-Plazzotta rank CP(T) for a given rooted 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)=1/2*CP(T1)(CP(T1)-1)+CP(T2)+1

with CP(T1)>=CP(T2) 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 an arbitrary tree T whose maximal number of children of any vertex is l, the Colijn-Plazzotta rank CP(T) is recursively defined as CP(T)=0 if T is the empty tree (with no vertices), CP(T)=1 if T consists of only one leaf and otherwise CP(T)=āˆ‘_{i=1,...,l} binom{CP(T_i)+i-1,i} (with CP(T_1)<=...<=CP(T_l)). If there are only k<l pending subtrees rooted at the children of the root of T, then T_1,...,T_{l-k} are empty trees, i.e. CP(T_1)=...=CP(T_{l-k})=0, and CP(T_{l-k+1}),...,CP(T_l) are the increasingly ordered CP-ranks of the k pending subtrees rooted at the children of the root of T. Note that if k=l there are no empty trees.

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

Usage

1
colPlaLab(tree, method)

Arguments

tree

A rooted tree in phylo format.

method

The method must be one of: "binary" or "arbitrary". Note that (only) in the arbitrary case vertices of out-degree 1 are allowed.

Value

colPlaLab returns the Colijn-Plazotta rank of the given tree according to the chosen method.

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

1
2
3
4
tree <- ape::read.tree(text="((((,),),(,)),(((,),),(,)));")
colPlaLab(tree, method="binary")
tree <- ape::read.tree(text="(((,),(,)),(,),(,));")
colPlaLab(tree, method="arbitrary")

treebalance documentation built on Oct. 17, 2021, 5:06 p.m.