# Computing RF Tree Distance over Succinct Representations
## Appendix A  
The succint data structure library already provided implementation for most of the used operations on the bp.support.sada.hpp file. We extended this library to support other operations needed to compute the distances, namely PreOrderMap, PreOrderSelect, PostOrderSelect, IsLeaf, LCA, ClusterSize and NumLeaves, and their implementation can be seen below. Moreover, we added two operations that were already in the SDSL library but not present in the bp.support.sada.hpp file. These operations were the rank10 operation to enable us to count the number of leaves and the select0 operation to enable us to go through a tree in a post-order traversal. ```
procedurePreOrderMap(\(bv,p\)): int returnrank1(\(bv,p\)) endprocedureprocedurePreOrderSelect(\(bv,i\)): int returnselect1(\(bv,i\)) endprocedureprocedurePostOrderSelect(\(bv,i\)): int returnfindOpen(Select0(\(bv,i\)))
``````
1:Input:\(bv_{1},bv_{2},CodeMap\)
2:\(\triangleright\) Let \(numInternalNodes1\) and \(numInternalNodes2\) be the number of internal nodes of both trees. 3:Output: Robinson-Foulds distance for fully labelled trees
4:
5:\(equalClusters\gets 0\)
6:for\(i\gets 1\) to \(N\)do
7:\(p\leftarrow\texttt{PostOrderSelect}(bv_{1},i)\)
8:\(lca\leftarrow\texttt{PreOrderSelect}(bv_{2},CodeMap[\texttt{PreOrderMap}(bv_{1},p)-1]+1)\)
9:\(size\gets 1\)
10:push(\(s\), \(\langle lca,size\rangle\)) \(\triangleright\) Let \(s\) be a stack. 11:if\(\texttt{IsLeaf}(p)\)) then
12:\(cs\leftarrow\texttt{ClusterSize}(bv_{1},p)\)
13:while\(cs\
eq 0\)do
14:\(\langle lcas,size\rangle\leftarrow\texttt{pop}(s)\)
15:if\(lca!=null\)then
16:\(\langle lca,size\rangle\leftarrow\texttt{pop}(s)\)
17:\(lcas\leftarrow\texttt{LCA}(bv_{2},lcas,lca)\)
18:endif
19:\(cs=cs-size\)
20:endwhile
21:if\(\texttt{ClusterSize}(bv_{1},p)=\texttt{ClusterSize}(bv_{2},lcas)\)then
22:\(equalClusters\gets equalClusters+1\)
23:endif
24:push(\(s\), \(\langle lcas,\texttt{ClusterSize}(bv_{1},p)\rangle\))
25:\(lcas\leftarrow-1\)
26:endif
27:endfor
28:\(distance\leftarrow(numInternalNodes1+numInternalNodes2-2\times equalClusters)/2\)
29:returndistance
```

**Algorithm A1** Extended Robinson-Foulds (eRF)

## Appendix B

The algorithms presented in this appendix depict the RF variations, namely the extended Robinson-Foulds distance (eRF) and the weighted Robinson-Foulds distance (wRF). ```
1:Input:\(bv_{1},bv_{2},CodeMap\)
2:\(\triangleright\) Let \(numInternalNodes1\) and \(numInternalNodes2\) be the number of internal nodes of both trees. 3:Output: Robinson-Foulds distance for fully labelled trees
4:
5:\(equalClusters\gets 0\)
6:for\(i\gets 1\) to \(N\)do
7:\(p\leftarrow\texttt{PostOrderSelect}(bv_{1},i)\)
8:\(lca\leftarrow\texttt{PreOrderSelect}(bv_{2},CodeMap[\texttt{PreOrderMap}(bv_{1},p)-1]+1)\)
9:\(size\gets 1\)
10:push(\(s\), \(\langle lca,size\rangle\)) \(\triangleright\) Let \(s\) be a stack. 11:if\(\texttt{IsLeaf}(p)\)) then
12:\(cs\leftarrow\texttt{ClusterSize}(bv_{1},p)\)
13:while\(cs\
eq 0\)do
14:\(\langle lcas,size\rangle\leftarrow\texttt{pop}(s)\)
15:if\(lca!=null\)then
16:\(\langle lca,size\rangle\leftarrow\texttt{pop}(s)\)
17:\(lcas\leftarrow\texttt{LCA}(bv_{2},lcas,lca)\)
18:endif
19:\(cs=cs-size\)
20:endwhile
21:if\(\texttt{ClusterSize}(bv_{1},p)=\texttt{ClusterSize}(bv_{2},lcas)\)then
22:\(equalClusters\gets equalClusters+1\)
23:endif
24:push(\(s\), \(\langle lcas,\texttt{ClusterSize}(bv_{1},p)\rangle\))
25:\(lcas\leftarrow-1\)
26:endif
27:endfor
28:\(distance\leftarrow(numInternalNodes1+numInternalNodes2-2\times equalClusters)/2\)
29:returndistance
```

**Algorithm A2** Extended Robinson-Foulds (eRF)

## References

* (1) [PERSON] _Inferring Phylogenies_; Sinauer Associates: Sunderland, MA, USA, 2004; Volume 2. * (2) [PERSON]; [PERSON] Practical performance of tree comparison metrics. _Syst. Biol._**2015**, 64, 205-214. [CrossRef] [PubMed]
* (3) [PERSON]; [PERSON] Twist-rotation transformations of binary trees and arithmetic expressions. _J. Algorithms_**1999**, _32_, 155-166. [CrossRef]
* (4) [PERSON]; [PERSON] Subtree transfer operations and their induced metrics on evolutionary trees.