# A Linear-Time Algorithm for the Isometric Reconciliation of Unrooted Trees
## 2 Algorithm
### Final Output and Possible Solution Sets  
This section has two goals. First, we want to characterize the set of possible solutions of the isometric reconciliation for two unrooted trees, which is of theoretical interest. We also need the results proved here to efficiently transform the output of our algorithm to its final form. We will characterize sets of potential roots, but these results also apply to the final valid roots, as according to the previous section, either all potential roots are valid or none are. We start with a generalized version of Claim 2, which can be proved in the same way as the original claim. Let \(S\) be a rooted species tree with root \(r\) and \(G\) an unrooted gene tree. Let \(A\) be a subset of leaves, and consider trees \(S_{A}\) and \(G_{A}\) induced by leaves from \(A\) and all paths connecting them. Let \(r^{\prime}\) be the root of \(S_{A}\), that is, the lowest common ancestor in \(S\) of all leaves in \(A\). Let \((q,h)\) be a potential rooting of \(G\) with respect to \(S\). Then \(G_{A}\) has a potential rooting \((q^{\prime},h^{\prime})\) with respect to \(S_{A}\), where \(q^{\prime}\) is the point of \(G_{A}\) closest to \(q\) (distance measured by \(d_{G}\)). Value \(h^{\prime}\) is defined by the following equation:  
\[h^{\prime}=h-d_{G}(q,q^{\prime})+d_{S}(r,r^{\prime}). \tag{9}\]  
In particular, if \(r\) belongs to \(S_{A}\) then \(r^{\prime}=r\) and if in addition \(q\) belongs to \(G_{A}\), then also \(q^{\prime}=q\) and \(h^{\prime}=h\). Before stating our core observation characterizing the set of potential solutions of the problem in Claim 9, we will add one more technical claim. Consider points \(r_{1}\) and \(r_{2}\) in unrooted \(S\) and \(q_{1}\) and \(q_{2}\) in unrooted \(G\) and values \(h_{1}\) and \(h_{2}\) such that \((q_{1},h_{1})\) is a potential rooting of \(G\) with respect to \(S\) rooted in \(r_{1}\) and \((q_{2},h_{2})\) is a potential rooting with respect to \(S\) rooted in \(r_{2}\). Let \(a\) be any leaf, let \(x\) be the point on the path between \(r_{1}\) and \(r_{2}\) closest to leaf \(a\) under \(d_{S}\), and let \(u\) be the point on the path between \(q_{1}\) and \(q_{2}\) closest to a under \(d_{G}\). Then  
\[d_{G}(u,q_{1})-d_{S}(x,r_{1})=(d_{G}(q_{1},q_{2})-d_{S}(r_{1},r_{2})+h_{1}-h_{2 })/2.\]  
In particular, if \(h_{1}=h_{2}\) and \(d_{G}(q_{1},q_{2})=d_{S}(r_{1},r_{2})\), then \(d_{G}(u,q_{1})=d_{S}(x,r_{1})\). Note that we will later show that conditions \(h_{1}=h_{2}\) and \(d_{G}(q_{1},q_{2})=d_{S}(r_{1},r_{2})\) are always satisfied, and thus \(d_{G}(u,q_{1})=d_{S}(x,r_{1})\). Proof. : From the definition of a potential rooting, we get \(d_{G}(a,q_{1})-d_{S}(a,r_{1})-h_{1}=d_{G}(a,q_{2})-d_{S}(a,r_{2})-h_{2}=0\). By splitting individual distances at points \(x\) and \(u\), we get \(d_{G}(a,q_{1})=d_{G}(a,u)+d_{G}(u,q_{1})\), \(d_{G}(a,q_{2})=d_{G}(a,u)+d_{G}(u,q_{2})=d_{G}(a,u)+(d_{G}(q_{1},q_{2})-d_{G}( u,q_{1}))\) and similarly for tree \(S\). By combining these equations, we get the desired claim. Let \(G\) and \(S\) be unrooted trees. Let \(\mathcal{R}\) be the set of potential roots of \(S\). Let \(r_{1}\) and \(r_{2}\) be two points from \(\mathcal{R}\), and let \(r_{3}\) be some point on the path connecting \(r_{1}\) and \(r_{2}\) in \(S\). For \(i\in\{1,2,3\}\), let \(S^{(i)}\) be \(S\) rooted in \(r_{i}\), and let \((q_{i},h_{i})\) be the potential rooting of \(G\) with respect to \(S^{(i)}\) (if it exists). Then the following four statements hold:\(d_{S}(r_{1},r_{2})=d_{C}(q_{1},q_{2})\);
2. \(h_{1}=h_{2}\);
3. \(r_{3}\in\mathcal{R}\) and thus the potential rooting \((q_{3},h_{3})\) exists;
4. \(q_{3}\) is on the path between \(q_{1}\) and \(q_{2}\). Proof. : If both \(r_{1}\) and \(r_{2}\) belong to the same edge of \(S\), all four statements are implied by the discussion in Section 2.5, where it is proved that the set of potential rootings for a single edge is either empty or it is an interval of points on this edge.