# Auxiliary functions `getDescMatrix` - Creates a matrix that contains the descendants of node $i$ in row $i$. `getAncVec` - Creates a vector that contains the parent (direct ancestor) of node $i$ at position $i$. `getNodesOfDepth` - Creates a matrix that contains the nodes of depth $i$ in row $i$. `symBucketLexicoSort` - Sorts the pairs of numbers lexicographically and returns ranking. Uses bucket sort. `getAllAncestors` - Returns all ancestors of $v$ including $v$ itself. `cPL_inv` - Returns the binary tree that belongs to the input label in an incomplete Newick format. `maxDepthLeaf` - Returns the maximumy< depth of a leaf in the subtree that is rooted at $v$. `get.subtreesize` - Creates a vector that contains at the $i$-th position the number of leaves in the pending subtree rooted at $i$. `getlca` - Returns the name of the lowest common ancestor of the two input vertices $v$ and $w$. `we_eth` - Returns the Wedderburn-Etherington number $we(n)$ for a given non-negative integer $n$. `getfurranks` - Returns for each vertex $i$ the Furnas rank of the subtree rooted at $i$. `getsubtree` - Returns the pending subtree (in phylo format) that is rooted at the input vertex. If the input vertex is a leaf, the function returns the standard tree for $n=1$ (with 1 edge). `is_binary` - Returns TRUE if the input tree is binary and FALSE otherwise. `is_phylo` - Tests all requirements of the phylo format, and returns TRUE if the tree is correctly formatted, else FALSE with detailed feedback on the features that are not met. `tree_decomposition` - Returns a list of length two, which contains the two pending subtrees that are rooted at the children of the root of the input tree. The smaller one (according to the number of leaves) is stated first. `tree_merge` - Returns a rooted tree $T$ in phylo format, which contains the input trees $tree1$ and $tree2$ as "left" and "right" maximal pending subtrees. `treenumber` - Returns the unique tree number $tn(T)$ of the given tree. $tn(T)$ is the rank of the tree $T$ among all rooted binary trees in the left-light rooted ordering. It can be calculated as follows: [REMOVE_ME]$$ tn(T)=F(T) + \sum_{i=1}^{n-1} we(i)tn(T)=F(T) + \sum we(i) over 1=i<=n-1 [REMOVE_ME_2]$$ in which $n$ is the number of leaves in $T$, $F(T)$ is the Furnas rank of $T$, i.e. the rank of $T$ in the left-light rooted ordering of all rooted binary trees with $n$ leaves, and $we(i)$ is the Wedderburn-Etherington number of $i$. The concept of assigning each rooted binary tree a unique tree number allows to store many trees with minimal storage use. For $n=1$ the function returns $tn(T)=1$ and a warning. `treenumber_inv` - Returns the unique tree (in phylo format) for the given tree number. `auxE_l_X` - Returns the sum of all products of l different values in X. ```r getDescMatrix(tree) getAncVec(tree) getNodesOfDepth(mat, root, n) symBucketLexicoSort(workLabs) getAllAncestors(tree, v) cPL_inv(label) maxDepthLeaf(tree, v = length(tree$tip.label) + 1) get.subtreesize(tree) getlca(tree, v, w) we_eth(n) getfurranks(tree) getsubtree(tree, subroot) is_binary(tree) is_phylo(tree) tree_decomposition(tree) tree_merge(tree1, tree2) treenumber(tree) treenumber_inv(treenum) auxE_l_X(subX, Xset) ``` ## Arguments - `tree`: A rooted tree in phylo format, >= 2 leaves - `mat`: Descendants matrix from `getDescMatrix` - `root`: Number (label) of the root of the tree - `n`: Number of leaves of the tree - `workLabs`: numeric matrix (2 columns) - `v`: A vertex of the tree. - `label`: A Colijn-Plazotta label of desired tree, a positive integer. - `w`: A vertex of the tree. - `subroot`: A vertex of the tree. It is not recommended to use leaves as subroots. - `tree1`: A rooted tree in phylo format. - `tree2`: A rooted tree in phylo format. - `treenum`: An integer denoting the tree number of the sought tree. - `subX`: integer >=1, size of the subsets of X. - `Xset`: Vector (multiset) of numeric values. ## Returns `desc_mat` numeric matrix `anc_vec` numeric vector `nodes_of_depth` numeric matrix `ranking` numeric vector `vectorWithAncs` numeric vector ## Description `getDescMatrix` - Creates a matrix that contains the descendants of node $i$ in row $i$. `getAncVec` - Creates a vector that contains the parent (direct ancestor) of node $i$ at position $i$. `getNodesOfDepth` - Creates a matrix that contains the nodes of depth $i$ in row $i$. `symBucketLexicoSort` - Sorts the pairs of numbers lexicographically and returns ranking. Uses bucket sort. `getAllAncestors` - Returns all ancestors of $v$ including $v$ itself. `cPL_inv` - Returns the binary tree that belongs to the input label in an incomplete Newick format. `maxDepthLeaf` - Returns the maximumy< depth of a leaf in the subtree that is rooted at $v$. `get.subtreesize` - Creates a vector that contains at the $i$-th position the number of leaves in the pending subtree rooted at $i$. `getlca` - Returns the name of the lowest common ancestor of the two input vertices $v$ and $w$. `we_eth` - Returns the Wedderburn-Etherington number $we(n)$ for a given non-negative integer $n$. `getfurranks` - Returns for each vertex $i$ the Furnas rank of the subtree rooted at $i$. `getsubtree` - Returns the pending subtree (in phylo format) that is rooted at the input vertex. If the input vertex is a leaf, the function returns the standard tree for $n=1$ (with 1 edge). `is_binary` - Returns TRUE if the input tree is binary and FALSE otherwise. `is_phylo` - Tests all requirements of the phylo format, and returns TRUE if the tree is correctly formatted, else FALSE with detailed feedback on the features that are not met. `tree_decomposition` - Returns a list of length two, which contains the two pending subtrees that are rooted at the children of the root of the input tree. The smaller one (according to the number of leaves) is stated first. `tree_merge` - Returns a rooted tree $T$ in phylo format, which contains the input trees $tree1$ and $tree2$ as "left" and "right" maximal pending subtrees. `treenumber` - Returns the unique tree number $tn(T)$ of the given tree. $tn(T)$ is the rank of the tree $T$ among all rooted binary trees in the left-light rooted ordering. It can be calculated as follows: $$ tn(T)=F(T) + \sum_{i=1}^{n-1} we(i)tn(T)=F(T) + \sum we(i) over 1=i<=n-1 $$ in which $n$ is the number of leaves in $T$, $F(T)$ is the Furnas rank of $T$, i.e. the rank of $T$ in the left-light rooted ordering of all rooted binary trees with $n$ leaves, and $we(i)$ is the Wedderburn-Etherington number of $i$. The concept of assigning each rooted binary tree a unique tree number allows to store many trees with minimal storage use. For $n=1$ the function returns $tn(T)=1$ and a warning. `treenumber_inv` - Returns the unique tree (in phylo format) for the given tree number. `auxE_l_X` - Returns the sum of all products of l different values in X. ## Examples ```r mat <- cbind(c(7,7,6,5,5,6),c(1,2,3,4,6,7)) tree <- list(edge=mat, tip.label=c("","","",""), Nnode=3) getDescMatrix(tree) mat <- cbind(c(5,5,5,5),c(1,2,3,4)) tree <- list(edge=mat, tip.label=c("","","",""), Nnode=1) getDescMatrix(tree) getAncVec(tree) getNodesOfDepth(mat=getDescMatrix(tree),root=length(tree$tip.label)+1, n=length(tree$tip.label)) myWorkLabs <- cbind(c(0,1,2,3,1,0),c(0,2,2,4,1,0)) symBucketLexicoSort(myWorkLabs) getAllAncestors(tree,v=6) cPL_inv(label=6) maxDepthLeaf(tree,v=6) get.subtreesize(tree) getlca(tree,1,2) we_eth(5) getfurranks(tree) getsubtree(tree,4) is_binary(ape::read.tree(text="((((,),),(,)),(((,),),(,)));")) is_phylo(ape::read.tree(text="((((,),),(,)),(((,),),(,)));")) tree_decomposition(ape::read.tree(text="((((,),),(,)),(((,),),(,)));")) treeA <- ape::read.tree(text="(((,),),(,));") treeB <- ape::read.tree(text="((,),);") tree_merge(treeA, treeB) treenumber(ape::read.tree(text="((((,),),(,)),(((,),),(,)));")) treenumber_inv(192) auxE_l_X(subX=3,Xset=c(1,1,2,2)) ``` ## Author(s) Sophie Kersting, Luise Kuehn and Lina Herbst

auxFuncs function