# Synesth: Comprehensive Syntenic Reconciliation with Unsampled Lineages
## 5 Generating All Pareto-Optimal Histories
Denote the children of \(v\) in \(T\) as \(v_{\ell}\) and \(v_{\ell}\), and the children of \(v\) in \(H\) as \(w_{\ell}\) and \(w_{\tau}\). If \(e(v)\in\{\text{Spe},\text{Dup},\text{Cut}\}\), then \(\gamma_{\ell}\) and \(\gamma_{\ell}\) cannot be strict ancestors of \(\sigma\), as otherwise \(\mathcal{H}\) would not be acyclic. Let \(Y=x(v_{\ell})\), \(Y^{\prime}=x(w_{\ell})\), \(Z=x(v_{\tau})\), \(Z^{\prime}=x(w_{\tau})\). If \(e(v)=\text{Spe}\), then \(\mathcal{H}\in P_{\text{Spe}}\) by Definition 1 (Item 1). Otherwise, let us first show that the synteny contents of both children are chosen appropriately. We have that \(X\cap Y\subseteq Y^{\prime}\) (resp. \(X\cap Z\subseteq Z^{\prime}\)); since, if any \(g\in X\cap Y\) (resp. \(g\in X\cap Z\)) was not in \(Y^{\prime}\) (resp. \(Z^{\prime}\)), we would have multiple gains of \(g\) in \(H\), i.e., one above \(v\) (since \(g\in X\)) and one between \(v\) and \(v_{l}\) (since \(g\in Y\), resp. \(v_{\tau}\) since \(g\in Z\)). * If \(e(v)\in\{\text{Dup},\text{\rm{TrDup}}\}\), by Definition 1, at least one of \(Y^{\prime}\) or \(Z^{\prime}\) is equal to \(X\). Without loss of generality (w.l.o.g. ), assume that \(Z^{\prime}=X\). We should have \(Y^{\prime}\subseteq X\cap Y\), as otherwise we would have at least one additional event in the path between \(v\) and \(v_{l}\) for losing \(Y^{\prime}-(X\cap Y)\), thus contradicting the Pareto-optimality of \(\mathcal{H}\). Hence, \(Y^{\prime}=X\cap Y\). * If \(e(v)\in\{\text{Cut},\text{\rm{TrCut}}\}\), it cannot be that \(Y^{\prime}\
ot\subseteq X\cap Y\) and \(Z^{\prime}\
ot\subseteq X\cap Z\) are both true as such a scenario would lead to a loss on each path between \(v\) and \(v_{\ell}\) and between \(v\) and \(v_{\tau}\), whereas by choosing \(Y^{\prime}\subseteq X\cap Y\) or \(Z^{\prime}\subseteq X\cap Z\), we save at least one loss. Since \(Y^{\prime}\) and \(Z^{\prime}\) are a partition of \(X\), then \(Z^{\prime}=X-Y\) if \(Y^{\prime}=X\cap Y\), or \(Y^{\prime}=X-Z\) otherwise. Finally, we show that the species of both children are also chosen appropriately. * If \(e(v)\in\{\text{Dup},\text{Cut}\}\), then by Definition 1, \(s(w_{\ell})=s(w_{\tau})=\sigma\). * If \(e(v)\in\{\text{\rm{TrDup}},\text{\rm{TrCut}}\}\), then by Definition 1, either \(s(w_{\ell})=\sigma\) and \(s(w_{\tau})\parallel\sigma\), or \(s(w_{\tau})=\sigma\) and \(s(w_{\ell})\parallel\sigma\). * If \(e(v)=\text{\rm{TrDup}}\), if \(s(w_{\ell})=\sigma\) (resp. \(s(w_{\tau})=\sigma\)), then \(x(w_{\ell})=X\) (resp. \(x(w_{\tau})=Y\)). We next consider how to compute the set of histories \(\text{path}([X,\sigma],[Y,\gamma])\) given any two syntenies \(X\) and \(Y\) and species \(\sigma\) and \(\gamma\). **Theorem 2** (Pareto-optimal paths). : _Let \(X\) and \(Y\) be two syntenies and \(\sigma\) and \(\gamma\) be two species. If \(\gamma\) is a strict ancestor of \(\sigma\), then \(\text{path}([X,\sigma],[Y,\gamma])=\emptyset\). Otherwise, \(\text{path}([X,\sigma],[Y,\gamma])=P_{0}\oplus P_{1}\oplus P_{2}\), where the following holds:_  
* \(P_{0}=\emptyset\) _if_ \(\sigma\parallel\gamma\)_. Otherwise,_ \(P_{0}\) _contains the history made up of a chain of_ \(\text{D}_{S^{*}}(\sigma,\gamma)\) _speculations and_ \(|\{(u,v)\in\text{P}_{S^{*}}(\sigma,\gamma)\mid v\
ot\in\text{V}(S)\}|\) _full losses; preceded by a partial loss event if_ \(X\
ot\subseteq Y\) _and followed by a gain event if_ \(Y\
ot\subseteq X\)_. If_ \(\gamma\in\text{L}(S^{*})-\text{L}(S)\)_, then_ \(P_{0}\) _also includes a history where the initial partial loss event is replaced by a terminal_ Dup _or_ Cut _event and an unsampled leaf._
* \(P_{1}=P_{\text{\rm{TrDup}}}\oplus P_{\text{\rm{TrCut}}}^{\text{\rm{Left}}} \oplus P_{\text{\rm{TrCut}}}^{\text{\rm{Right}}}\)_. If_ \(\sigma\parallel\gamma\)_, all three sets contain histories starting with a_ Tr _event_ \(v\) _from_ \(\sigma^{\prime}=\sigma\) _to_ \(\gamma\)_. Otherwise, all three sets contain histories starting with a speciation at \(\sigma\).