# A Linear-Time Algorithm for the Isometric Reconciliation of Unrooted Trees
## 2 Algorithm
### Potential Rooting of a Gene Tree
By combining these two equations, the equation \(d_{G}(q,a)=h+d_{S}(r,a)\) implied by the potential rooting \((q,h)\) and Equation (1), we obtain  
\[d_{G}(q^{\prime},a) = d_{G}(q,a)-d_{G}(q,q^{\prime})\] \[= h+d_{S}(r,a)-d_{G}(q,q^{\prime})\] \[= h^{\prime}+d_{G}(q,q^{\prime})-d_{S}(r,r^{\prime})+d_{S}(r,a)-d_ {G}(q,q^{\prime})\] \[= h^{\prime}-d_{S}(r,r^{\prime})+d_{S}(r,a)\] \[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}),\]0 \[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}),\]1  
Thus we have proved that \((q^{\prime},h^{\prime})\) is the potential rooting, as required. The following two claims help us to compute potential rootings. **Claim 3**. : _Let both \(S\) and \(G\) contain only a single node \(x\). The potential rooting of \(G\) with respect to \(S\) is \((x,0)\)._  
**Claim 4**. : _Let \(S\) be a rooted species tree with root \(r\), which is an internal node with two children \(r_{1}\) and \(r_{2}\), and let \(G\) be an unrooted gene tree. Let \(S_{1}\) and \(S_{2}\) be subtrees of \(S\) rooted at \(r_{1}\) and \(r_{2}\). Let us assume that \(G_{L(S_{1})}\) and \(G_{L(S_{2})}\) have potential rootings \((q_{1},h_{1})\), \((q_{2},h_{2})\) (both rootings exist). Then the pair \((q,h)\) is a potential rooting of \(G\) if and only if the following three conditions are satisfied._  
1. \(h=(d_{G}(q_{1},q_{2})-d_{S}(r_{1},r_{2})+h_{1}+h_{2})/2\)_._
2. \(q=G(q_{1},q_{2},\beta)\)_, where_ \(\beta=h+d_{S}(r_{1},r)-h_{1}\) _and_ \(0\leq\beta\leq d_{G}(q_{1},q_{2})\)_._
3. _Let_ \(\pi\) _be the path in_ \(G\) _between_ \(q_{1}\) _and_ \(q_{2}\)_. For each_ \(i\in\{1,2\}\) _either_ \(q_{i}=q\) _or_ \(\pi\) _is completely outside_ \(G_{L(S_{i})}\) _except for its endpoint_ \(q_{i}\)_._  
Proof. : Let \(G_{1}=G_{L(S_{1})}\) and \(G_{2}=G_{L(S_{2})}\). Tree \(G\) consists of \(G_{1}\) and \(G_{2}\) and possibly the path \(\pi\) connecting these two trees in \(G\). First, let us prove that if \((q,h)\) is a potential rooting, it satisfies the three conditions. Let us start with Condition 3 for some \(i\in\{1,2\}\). If \(q=q_{i}\), the condition is automatically satisfied. Otherwise, we can use Claim 2 to observe that \(q_{i}\) must be the point from \(G_{L(S_{i})}\) closest to \(q\), implying that the path from \(q\) to \(q_{i}\) is outside \(G_{L(S_{i})}\) except for \(q_{i}\). This discussion also implies that \(q\) is on the path from \(q_{1}\) to \(q_{2}\), as needed in Condition 2. Next, we use Equation (1) from Claim 2, which gives us the value of \(h\) expressed as  
\[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}),\]2  
for each of the subtrees \(S_{i}\). We obtain the desired value of \(\beta\) from Condition 2 directly from Equation (2) for \(S_{1}\), noting that \(\beta=d_{G}(q_{1},q)\). Finally, using Equation (2) for \(S_{2}\) and noting that \(d_{G}(q,q_{2})=d_{G}(q_{1},q_{2})-\beta\), we obtain Condition 1. To prove that the three conditions imply potential rooting, we first prove that Conditions 1 and 2 imply \(d_{G}(q,q_{i})=h+d_{S}(r,r_{i})-h_{i}\) for each \(i\in\{1,2\}\). This equation clearly holds for \(i=1\) fromCondition 2 as \(\beta=d_{G}(q_{1},q)\). Therefore, let us consider \(d_{G}(q,q_{2})\). From definition of \(q\) in Condition 2, we see that \(d_{G}(q,q_{2})=d_{G}(q_{1},q_{2})-\beta\).