# A Linear-Time Algorithm for the Isometric Reconciliation of Unrooted Trees
## 1 Introduction
### Definition of Reconciliation  
Consider a rooted or unrooted tree \(G\) (the input gene tree), rooted or unrooted tree \(S\) (the input species tree) and input mapping \(\mu:L(G)\to L(S)\), which gives for each gene its species of origin. Both trees have edges weighted by non-negative weights. An isometric reconciliation of the triple \((G,S,\mu)\) is a triple \((G_{O},S_{O},\Phi)\), where \(G_{O}\) and \(S_{O}\) are weighted rooted trees and \(\Phi\) is a mapping from \(V(G_{O})\) to \(V(S_{O})\) such that the following holds:  
Figure 2: An example of an isometric reconciliation of two unrooted trees. On the left, the input gene tree \(G\) and species tree \(S\) are shown, both unrooted. On the right is one possible solution, consisting of rooted trees \(G_{O}\) and \(S_{O}\) and a mapping between them. The species tree is rooted on edge \(\{x,c\}\) at distance 4 from \(c\). Once the root of \(S\) is fixed, the rest of the solution is given uniquely. All possible roots in \(S\) are located on the edge \(\{x,c\}\) in distances from \(0\) to \(5\) from \(c\). Note that in our algorithm, we preprocess tree \(S\) to have two leaves \(b_{1}\) and \(b_{2}\) instead of leaf \(b\), so that the leaves of \(G\) and \(S\) are in one-to-one correspondence (see Sections 2.1 and 2.8). * The output gene tree \(G_{O}\) is either \(G\), if \(G\) is rooted, or a rooted version of \(G\) obtained by subdividing some edge and rooting the tree in this newly created node. * The output species tree \(S_{O}\) is obtained from \(S\) by rooting it if \(S\) is unrooted and optionally subdividing some edges by additional nodes and also optionally adding a new path leading from above to the original root of \(S\). * Mapping \(\Phi\) agrees with input mapping \(\mu\) on all leaves. * Mapping \(\Phi\) preserves the ancestor/descendant relationships and the distances between ancestors and descendants. For each \(u\) and \(v\) such that \(u\) is a parent of \(v\) in \(G_{O}\), we have that \(\Phi(u)\) is an ancestor of \(\Phi(v)\) and \(d_{S_{O}}(\Phi(u),\Phi(v))=d_{G_{O}}(u,v)\). * Nodes are not added to \(S_{O}\) and \(G_{O}\) unnecessarily. For each node \(x\) which was added to \(S_{O}\) except for the root, there is some node \(u\) from \(G_{O}\) such that \(\Phi(u)=x\). The edges incident to \(x\) have strictly positive weights. Note that when subdividing a weighted edge \(\{u,v\}\), we divide the original edge length between the new edges so that the distance of \(u\) and \(v\) remains the same. The new nodes added to the output species tree \(S_{O}\) represent duplication events; the path above the root of \(S\) corresponds to ancient duplications happening before the first speciation represented in the species tree. Figure 3 shows an example of an isometric reconciliation where the root of \(G_{O}\) maps above the original root of \(S_{O}\). A more detailed discussion of the isometric reconciliation model can be found in the article by [PERSON] et al. [4]. For algorithmic simplicity, we allow rooting trees only in points located on edges, not in the original nodes. To root a tree in an existing node \(u\), we choose one of the edges incident to \(u\) and subdivide it by a new node in the distance \(0\) from \(u\). This is the only exception where we are allowed to create new edges of zero length. In this paper, we do not compute the full reconciliation which includes mapping \(\Phi\) and new nodes added to the input trees. Instead, we output all pairs of valid roots in the two trees, that is, pairs of points in \(G\) and \(S\) such that when the trees are rooted in these points, they can be reconciled. If desired, the full reconciliation can be easily computed for any particular pair of valid roots in \(O(N\log N)\) time. Figure 3: An example of two unrooted trees and their isometric reconciliation, in which the root of \(G_{O}\) is mapped to a point above the original root of \(S\). Both input trees consist of only a single edge; the length of the edge is greater in \(G\).