Description Usage Arguments Value Author(s) References Examples
View source: R/colPlaLab_inv.R
This function generates the unique rooted binary tree T (in phylo
format) that corresponds to the given Colijn-Plazzotta rank CP(T). It
is the inverse function of colPlaLab() with the method 'binary'.
colPlaLab()
:
For a given rooted binary tree T, CP(T) is recursively defined as
CP(T)=1 if T consists of only one vertex 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 T.
The rank CP(T) of T corresponds to its position in the
lexicographically sorted list of (i,j): (1),(1,1),(2,1),(2,2),(3,1),...
colPlaLab_inv()
:
For a given rank CP the corresponding tree T can be reconstructed
by starting from one vertex ρ (labelled CP) and recursively
splitting vertices whose labels h are greater than 1 into two children with the labels:
i=ceil((1+sqrt(8*h-7))/2)-1
and
j=h-(i*(i-1))/2-1
until there are no more vertices to split.
For CP=1 the function returns the smallest possible tree in the
phylo format: the tree consisting of a single edge.
Note that problems can arise for extremely high input values (>10e+18).
1 |
rank |
An integer denoting the Colijn-Plazzotta rank of the sought tree. |
colPlaLab_inv
returns the unique rooted binary tree for the given rank.
Sophie Kersting
C. Colijn and G. Plazzotta. A Metric on Phylogenetic Tree Shapes. Systematic Biology, 67(1):113-126,2018. doi: 10.1093/sysbio/syx046.
N. A. Rosenberg. On the Colijn-Plazzotta numbering scheme for unlabeled binary rooted trees. Discrete Applied Mathematics, 291:88-98, 2021. doi: 10.1016/j.dam.2020.11.021.
1 | colPlaLab_inv(22)
|
Add the following code to your website.
For more information on customizing the embed code, read Embedding Snippets.