# A Linear-Time Algorithm for the Isometric Reconciliation of Unrooted Trees
## 2 Algorithm
### Further Algorithmic Details  
In this section, we provide further details on the input preprocessing and tree primitives from Sections 2.1 and 2.2. First, we need to preprocess our trees so that they have the same set of leaves. Definition of reconciliation allows multiple leaves \(a_{1},\ldots,a_{k}\) of \(G\) to correspond to a single leaf \(a\) of \(S\) (this corresponds to multiple copies of a gene in a single species). In that case, we add new leaves \(a_{1},\ldots,a_{k}\) to \(S\), all connected to node \(a\) by edges of zero length. Each leaf \(a_{i}\) of \(G\) will naturally correspond to leaf \(a_{i}\) of \(S\). If, on the other hand, some leaf of \(S\) does not occur in \(G\), it can be deleted from \(S\). Leaves of \(G\) with no corresponding leaf of \(S\) are not considered in the reconciliation problem. Thus these changes will satisfy Assumption 1 from Section 2.1. Assumption 2 can be achieved by replacing nodes of higher degree in \(S\) with binary subtrees connected by zero-length edges. A node of degree two in both \(S\) and \(G\) can be bypassed by an edge connecting its two neighbors. The condition on non-zero lengths in \(G\) (Assumption 3) can be achieved by contracting edges of zero length. However, if some leaf \(a\) is connected to its neighbor in \(G\) by an edge of length 0, contracting this edge would remove the leaf. Therefore, we can instead lengthen the edge to \(a\) by some constant, and then also lengthen the edge leading to \(a\) in \(S\) by the same amount. It is easy to see that all these transformations leave the set of solutions practically unchanged; any reconciliation in the preprocessed trees can be easily mapped back to the original trees and vice versa. The only exceptions are reconciliations that root the modified trees on edges added or extended in the preprocessing phase. Such rootings have no counterpart in the original trees and can be simply omitted from the final output. Now let us consider efficient implementation of the tree primitives from Section 2.2 for each tree \(T\in\{G,S\}\). In the precomputation phase, we root the tree \(T\) in an arbitrary node. On the resulting rooted tree, we precompute data structures allowing \(O(1)\) computation of \(\text{lca}_{T}\); this precomputation can be done in \(O(N)\) time [16; 17]. We also store the distance to the root in each node; let us denote this value for node \(u\) as \(d[u]\). Then the distance between nodes \(u\) and \(v\) is \(d[u]+d[v]-2d[\text{lca}_{T}(u,v)]\), which can be computed in constant time. However, we also need to be able to compute distances between points of the form \(p_{1}=T(u_{1},v_{1},\alpha_{1})\) and \(p_{2}=T(u_{2},v_{2},\alpha_{2})\). Our technique for this computation is to synchronize these points, that is, to express them both in the form \(p_{i}=T(w_{1},w_{2},\beta_{i})\), where \(w_{1},w_{2}\in\{u_{1},v_{1},u_{2},v_{2}\}\). Once the points are synchronized on a single path between \(w_{1}\) and \(w_{2}\), their distance is simply \(|\beta_{1}-\beta_{2}|\). To synchronize the points, we first consider the path between \(u_{1}\) and \(v_{1}\) and node \(u_{2}\). The path from \(u_{1}\) to \(u_{2}\) diverges from the path from \(u_{1}\) to \(v_{1}\) at some node \(x_{1}\). We can compute the distance \(d_{T}(u_{1},x_{1})\) as \((d_{T}(u_{1},v_{1})+d_{T}(u_{1},u_{2})-d_{T}(v_{1},u_{2}))/2\); this is well known from the neighbor joining algorithm [18]. Our next goal is to express \(p_{1}\) in the form \(T(u_{2},y_{1},\gamma_{1})\) for some node \(y_{1}\in\{u_{1},v_{1}\}\). If \(\alpha_{1}\leq d_{T}(u_{1},x_{1})\), \(p_{1}\) is located on the shared portion of the two paths considered above and thus \(p_{1}=T(u_{2},u_{1},d_{T}(u_{1},u_{2})-\alpha_{1})\). Otherwise, \(p_{1}\) is located after the path from \(u_{1}\) to \(v_{1}\) passing through \(x_{1}\), and thus \(p_{1}=T(u_{2},v_{1},\gamma_{1})\), where \(\gamma_{1}=d_{T}(u_{2},v_{1})-d_{T}(u_{1},v_{1})+\alpha_{1}\).