# Computing RF Tree Distance over Succinct Representations
## 2 Background
The RF distance given in Definition 1 can be extended  
Figure 1: An unrooted phylogenetic tree (**a**) and a rooted phylogenetic tree (**b**) that resulted from transforming the unrooted one. \(e\) denotes the equivalent edge in both trees. The set of labels of \(T_{1}\), \(L(T_{1})\) is \(\{A,B,C,D,E\}\). (**a**) Unrooted phylogenetic tree \(T\) with labels only on the leaves. (**b**) Rooted version of tree \(T\), \(T_{1}\), by choosing \(X\) as root, and where \(u_{1},\ldots,u_{4}\) denote \(T_{1}\) internal nodes. to fully labelled trees by just noting that, given \(v\in V(T)\), \(c(v)=L(T(v))\) includes now the labels of all nodes in subtree \(T(v)\); and hence the clusters in \(C(T)\) include the labels for all nodes as well. **Definition 2**. : _The extended Robinson-Foulds (RF) distance between two fully labelled rooted trees \(T_{1}\) and \(T_{2}\), with unique labelling in all nodes, is defined by_  
\[eRF(T_{1},T_{2})=|C(T_{1})\setminus C(T_{2})|\cup|C(T_{2})\setminus C(T_{1})|.\]  
Let us consider trees \(T_{2}\) and \(T_{3}\) in Figure 2; \(eRF(T_{2},T_{3})=2\) since there are only two distinct clusters in \(T_{2}\) and \(T_{3}\), namely \(\{B,C,F\}\) and \(\{C,D,F\}\). Even though RF can offer a very reliable distance between two trees in terms of their topology, sometimes it is convenient to consider weights. A version of Robinson-Foulds distance for weighted trees (wRF) takes then into account the branch weights of both trees [7]. These weights represent, for instance, the varying levels of correction for DNA sequencing errors. We let \(T\) be a phylogenetic rooted tree, \(v\in V(T)\), \(w:E(T)\to\mathbf{R}\), \(e\in E(T)\) the edge with target \(v\), and \(c(v)\) the cluster at \(v\) in \(T\) as before; the weight of cluster \(c(v)\) in \(T\), \(w_{T}(c(v))\) is defined as \(w(e)\). **Definition 3** ([PERSON], 1979 [7]). : _The weighted Robinson-Foulds (wRF) distance between two rooted trees \(T_{1}\) and \(T_{2}\), with unique labelling in leaves, is defined as_  
\[wRF(T_{1},T_{2})=\sum_{c\in C(T_{1})\cap C(T_{2})}|w_{T_{1}}(c)-w_{T_{2}}(c)|+ \sum_{c\in C(T_{1})\setminus C(T_{2})}w_{T_{1}}(c)+\sum_{c\in C(T_{2})\setminus C (T_{1})}w_{T_{2}}(c).\]  
In fact, at lower levels of sequencing error, RF distance usually exhibits a consistent pattern, showcasing the superiority of proper correction for both over- and undercorrection for DNA sequencing error. Interestingly, in this context, correction had no impact on RF scores. Conversely, at extremely high levels of sequencing error, wRF results suggested that proper correction and overcorrection were equivalent, while the RF scores demonstrated that overcorrection led to the destruction of topological recovery. Then, both measures complement themselves [2]. Definition 4 extends wRF to labelled rooted phylogenetic trees assuming the extension of \(c(v)\) and \(C(T)\) as before. **Definition 4**. : _The weighted labelled Robinson-Foulds (weRF) distance between two fully labelled rooted trees \(T_{1}\) and \(T_{2}\), with unique labelling in all nodes, is defined as follows:_  
\[weRF(T_{1},T_{2})=\sum_{c\in C(T_{1})\cap C(T_{2})}|w_{T_{1}}(c)-w_{T_{2}}(c)| +\sum_{c\in C(T_{1})\setminus C(T_{2})}w_{T_{1}}(c)+\sum_{c\in C(T_{2}) \setminus C(T_{1})}w_{T_{2}}(c).\]  
Let us consider trees \(T_{2}\) and \(T_{3}\) in Figure 3; \(wRF(T_{2},T_{3})=19\). Figure 2: Two rooted labelled phylogenetic trees, \(T_{2}\) and \(T_{3}\). Both have a unique set of labels \(\{A,B,C,D,E,F,G,H,1\}\). (**a**) A rooted labelled phylogenetic tree \(T_{2}\). (**b**) A rooted labelled phylogenetic tree \(T_{3}\). Phylogenetic trees are commonly represented and stored using the well-known Newick tree format. For instance, the rooted tree in Figure 1 can be represented as (((B, C), D),(A, E));. In this example, we only have labels on the leaves and we do not have edge weights. The Newick format also supports edge weights. For instance, in Figure 3, tree \(T_{2}\) can be represented as (((B:2.5,C:2.5):2,D:4.5):3,(A:1,E:1):6.5);.