# A Linear-Time Algorithm for the Isometric Reconciliation of Unrooted Trees
## 2 Algorithm
### Potential Rooting of a Gene Tree  
In the first phase of our algorithm, we process all rooted subtrees of the species tree \(S\) and compute potential rootings of the corresponding parts of \(G\), as defined in the next definition. Definition 1: Let \(S\) be a rooted species tree with root \(r\) and \(G\) an unrooted gene tree with the same set of leaves. A potential rooting of \(G\) with respect to \(S\) is a pair \((q,h)\) where \(q\) is a point in \(G\) and \(h\) is a real value such that for any leaf \(a\in L(S)=L(G)\) we have  
\[d_{G}(q,a)=h+d_{S}(r,a).\]  
The intuition behind this definition is that in the reconciliation of \(S\) with \(G\), point \(q\) is the new root of \(G\), and it maps to distance \(h\) above node \(r\). In an isometric reconciliation, we always have \(h\geq 0\), but here we allow negative values of \(h\) to keep the algorithm simple; negative values of \(h\) are ruled out in a later phase of the algorithm. In the rest of this section, we prove a series of claims characterizing potential rootings. Although Definition 1 and the following claims are formulated for rooted tree \(S\), we will eventually apply them to rooted subtrees \(T\) of an unrooted tree \(S\), and to keep the set of leaves the same, we will restrict \(G\) to \(G_{L(T)}\). Claim 1: Let \(S\) be a rooted species tree with root \(r\) and \(G\) an unrooted gene tree. Then there is at most one potential rooting of \(G\) with respect to \(S\). More precisely, if \((q_{1},h_{1})\) and \((q_{2},h_{2})\) are potential rootings, then \(h_{1}=h_{2}\) and \(d_{G}(q_{1},q_{2})=0\). Proof: Let \((q_{1},h_{1})\), \((q_{2},h_{2})\) be two potential rootings. If \(d_{G}(q_{1},q_{2})=0\), then both \(h_{1}\) and \(h_{2}\) must be equal to \(d_{G}(q_{1},a)-d_{S}(r,a)\), where \(r\) is the root of \(S\), and \(a\) is an arbitrary leaf from \(L(S)\). Therefore, let us assume that \(d_{G}(q_{1},q_{2})>0\). Consider the forest obtained by removing the path connecting \(q_{1}\) and \(q_{2}\) from \(G\). For \(i\in\{1,2\}\), let us denote by \(a_{i}\) an arbitrary leaf of \(G\) contained in the component of this forest containing \(q_{i}\). Due to the choice of leaf \(a_{1}\), the path from \(a_{1}\) to \(q_{2}\) in \(G\) goes through \(q_{1}\), and thus we obtain the following equations:  
\[h_{2}+d_{S}(r,a_{1})=d_{G}(q_{2},a_{1})=d_{G}(q_{1},a_{1})+d_{G}(q_{1},q_{2})= h_{1}+d_{S}(r,a_{1})+d_{G}(q_{1},q_{2}),\]  
\[h_{2}-h_{1}=d_{G}(q_{1},q_{2}).\]  
Symmetrically, for \(a_{2}\) we have  
\[h_{1}+d_{S}(x,a_{2})=d_{G}(q_{1},a_{2})=d_{G}(q_{2},a_{2})+d_{G}(q_{1},q_{2})= h_{2}+d_{S}(x,a_{2})+d_{G}(q_{1},q_{2}),\]  
\[h_{2}-h_{1}=-d_{G}(q_{1},q_{2}),\]  
which is a contradiction, implying that indeed \(d_{G}(q_{1},q_{2})=0\). **Claim 2**. : _Let \(S\) be a rooted species tree with root \(r\) and \(G\) an unrooted gene tree. Let \(S^{\prime}\) be a subtree of \(S\) with root \(r^{\prime}\). Let \((q,h)\) be a potential rooting of \(G\) with respect to \(S\). Then \(G_{L(S^{\prime})}\) has a potential rooting \((q^{\prime},h^{\prime})\) with respect to \(S^{\prime}\), where \(q^{\prime}\) is the point of \(G_{L(S^{\prime})}\) closest to \(q\) (distance measured by \(d_{G}\)). In particular, if \(q\) is inside \(G_{L(S^{\prime})}\), then \(q^{\prime}=q\). Value \(h^{\prime}\) is defined by the following equation:_  
\[h^{\prime}=h-d_{G}(q,q^{\prime})+d_{S}(r,r^{\prime}). \tag{1}\]  
Proof. : Let \(q^{\prime}\) be the point of \(G_{L(S^{\prime})}\) closest to \(q\), and let \(h^{\prime}\) be the value defined by Equation (1). Then for any leaf \(a\) of \(S^{\prime}\) the path from \(a\) to \(q\) must lead through \(q^{\prime}\), and thus we have \(d_{G}(q,a)=d_{G}(q^{\prime},a)+d_{G}(q,q^{\prime})\). Similarly, \(d_{S}(r,a)=d_{S}(r^{\prime},a)+d_{S}(r,r^{\prime})\).