# Computing RF Tree Distance over Succinct Representations
## 2 Background  
A phylogenetic tree, denoted as \(T=(V,E)\), is defined as a connected acyclic graph. The set \(V\), also denoted as \(V(T)\), represents the vertices (nodes) of tree \(T\). The set \(E\subseteq V\times V\), also denoted as \(E(T)\), represents the edges (links) of tree \(T\). The leaves of the tree, which are the vertices of degree one, are labelled with data that represent species, strains or even genes. A phylogenetic tree represents then the evolutionary relationships among taxonomical groups, or taxa. In most phylogenetic inference methods, the internal vertices of the tree represent hypothetical or inferred common ancestors of the entities represented by the leaves. These internal vertices do not typically have a specific label or represent direct data. However, there are some distance based phylogenetic inference methods that infer a fully labelled phylogenetic tree [24]. In such cases, the internal vertices may also have labels associated with them, providing additional information about the inferred common ancestors. We denote the labels of a phylogenetic tree \(T\) by \(L(T)\). The inferred phylogenetic trees can be rooted or unrooted, depending on whether or not a specific root node is assigned. In the rooted ones, there exists a distinguished vertex called the root of \(T\). To calculate the Robinson-Foulds (RF) distance on a rooted or unrooted tree, comparison of the clades or bipartitions of the trees is needed, respectively. As mentioned before, a clade is a group on a tree that includes a node and all of the lineages descended from that node. Thus, clades can be seen as the subtrees of a phylogenetic tree. A bipartition of a tree is induced by edge removal [1]. Nevertheless, we can convert an unrooted tree into a rooted one by adding an arbitrary root node [25] (see Figure 1). A measure based on Robison-Foulds distance to compare unrooted with rooted trees was also proposed [26]. In this work, we consider rooted trees. Let \(T\) be a rooted tree. A _sub-tree_\(S\) of \(T\), which we denote by \(S(T)\), is a tree such that \(V(S)\subseteq V(T)\), \(E(S)\subseteq E(T)\), and the endpoints of any edge in \(E(S)\) must belong to \(V(S)\). We denote by \(T(v)\) the _maximum sub-tree_ of \(T\) that is rooted at \(v\). Thus, for each \(v\in V(T)\), we define the _cluster_ at \(v\) in \(T\) as \(c(v)=L(T(v))\). For instance, the rooted tree in Figure 1 contains nine clusters, namely \(c(B)=\{B\}\), \(c(C)=\{C\}\), \(c(D)=\{D\}\), \(c(A)=\{A\}\), \(c(E)=\{E\}\), \(c(u_{1})=\{B,C\}\), \(c(u_{2})=\{B,C,D\}\), \(c(u_{3})=\{A,E\}\) and \(c(u_{4})=\{B,C,D,A,E\}\), with \(u_{i}\) denoting unnamed or unlabelled nodes in \(T\). We notice that nodes labelled by symbol \(u\) represent hypothetical taxonomic units and thus they are not included on the cluster. The set of all clusters present in \(T\) is denoted by \(C(T)\), i.e., \(C(T)=\cup_{v\in V(T)}\{c(v)\}\). In Figure 1, \(C(T_{1})\) contains the previous nine clusters. The Robison-Foulds distance measures the dissimilarity between two trees by counting the differences in the clades they contain if rooted. **Definition 1** ([PERSON], 1981 [6]). : _The Robinson-Foulds (RF) distance between two rooted trees \(T_{1}\) and \(T_{2}\), with unique labelling in leaves, is defined by_  
\[RF(T_{1},T_{2})=|C(T_{1})\setminus C(T_{2})|\cup|C(T_{2})\setminus C(T_{1})|.\]  
We notice that this definition is equivalent to \(RF(T_{1},T_{2})=|C(T_{1})|+|C(T_{2})|-2|C(T_{1})\cap C(T_{2})|\), commonly found in the literature. We also note that most software implementations usually divide the RF distance by 2 [2], and further normalize it. When dealing with fully labelled phylogenetic trees, labels are present not only in leaves but also in internal nodes. Figure 2 depicts two rooted and fully labelled phylogenetic trees. The clusters of tree \(T_{2}\) are \(C(A)=\{A\}\), \(C(B)=\{B\}\), \(C(C)=\{C\}\), \(C(D)=\{D\}\), \(C(E)=\{E\}\), \(C(F)=\{B,C,F\}\), \(C(G)=\{B,C,F,D,G\}\), \(C(H)=\{A,E,H\}\) and \(C(I)=\{B,C,F,D,G,A,E,H,I\}\).