# Synesth: Comprehensive Syntenic Reconciliation with Unsampled Lineages
## 5 Generating All Pareto-Optimal Histories
Consider the history \(\mathcal{H}^{\prime}\) obtained from \(\mathcal{H}\) via the following: (1) Removing all the nodes on the path from \(v_{2}\) to \(v_{4}\) and their invisible subtrees, excluding \(v_{2}\) and \(v_{4}\) themselves but including, in particular, \(v_{3}\); (2) Connecting \(v_{2}\) directly to \(v_{4}\); (3) Remapping \(s(v_{2})\) to any unsampled species separated both from \(s(v_{1})\) and \(s(v_{4})\); (4) Replacing the subtree below \(v_{2}\) by a single unsampled leaf \(l\) with \(s(l)=s(v_{2})\) and \(x(l)=x(v_{2})\) if \(e(v_{2})=\mathrm{TrDup}\), or \(x(l)=x(v_{2})-x(v_{4})\) otherwise. Clearly, \(\mathcal{H}^{\prime}\preceq\mathcal{H}\), \(\mathcal{H}^{\prime}\
eq\mathcal{H}\) and \(\mathcal{H}^{\prime}\in\mathrm{path}([X,\sigma],[Y,\gamma])\), which contradicts the Pareto-optimality of \(\mathcal{H}\). As per Definition 4 (Item 5 and Item 6), any partial loss must be placed at the end of the history, and any gain must be placed at the start. Note that \(\mathcal{H}\) contains either zero (\(P_{0}\)), one (\(P_{1}\)), or two (\(P_{2}\)) transfers. * [\(\mathcal{H}\) _contains no transfers._] Note that \(\sigma\) cannot be separated from \(\gamma\) since only transfers can reach separate species; thus, \(\sigma\) is an ancestor of \(\gamma\). We start by showing that \(\mathcal{H}\) can only possibly contain a duplication or a cut if that event is on an unsampled leaf species. If \(v\) is a node such that \(e(v)\in\{\mathrm{Dup},\mathrm{Cut}\}\) and \(s(v)\
otin\mathrm{L}(S^{*})-\mathrm{L}(S)\), then the invisible subtree of \(v\) contains at least one full loss. In this case, we can remove the invisible subtree and turn \(v\) into a partial loss, if needed, otherwise we would replace \(v\) with its remaining child. Hence, if \(\mathcal{H}\) contains a duplication or a cut, it must be the last binary event on the main path. Thus, all other binary events must be speciations, and we need exactly \(\mathrm{D}_{S^{*}}(\sigma,\gamma)\) of them to reach \(\sigma\) from \(\gamma\). Those speciations must lead to one full loss for each species \(s\in\mathrm{V}(S)\). Hence, \(\mathcal{H}\in P_{0}\). * [\(\mathcal{H}\) _contains exactly one transfer._] Let \(v\) be the only transfer node. If \(\sigma\leq\gamma\), then there must be a speciation above \(v\) so that \(s(v)\) can be separated from \(\gamma\) since \(\mathcal{H}\) cannot contain other transfers. Notice that \(\mathcal{H}\) contains no partial losses, duplications, or cuts. In fact, any partial loss can be merged into the transfer. As for duplications and cuts, they can be removed if they do not save any loss, or merged into the transfer otherwise. Apart from the initial speciation if \(\sigma\leq\gamma\), \(\mathcal{H}\) contains no other speciations as those before (resp. after) the transfer can be removed by redirecting the transfer to start from a higher species (resp. to end at a lower species) that is still separated from \(\gamma\) (resp. \(\sigma\)). If \(e(v)=\mathrm{TrDup}\) or \(X\
ot\subseteq Y\), then the invisible subtree of \(v\) must contain at least one full loss, unless \(s(v)\in\mathrm{L}(S^{*})-\mathrm{L}(S)\). If \(s(v)\
ot\in\mathrm{L}(S^{*})-\mathrm{L}(S)\) and \(e(v)=\mathrm{TrCut}\), then either subtree of \(v\) must contain at least one full or partial loss if \(x(v)\
ot\subseteq Y\). Hence, \(\mathcal{H}\in P_{1}\). * [\(\mathcal{H}\) _contains exactly two transfers._] Let \(v\) and \(v^{\prime}\) be the only two transfer nodes. If \(\sigma=\mathrm{r}(S^{*})\), then \(\mathcal{H}\) must contain at least one full loss; hence, \(\mathcal{H}\) is not Pareto-optimal. If \(\sigma\in\mathrm{L}(S^{*})-\mathrm{L}(S)\), then, if \(\sigma\leq\gamma\), we can remove both transfers, and, if \(\sigma\parallel\gamma\), then we can remove \(v^{\prime}\), in both cases without introducing additional events. If \(\sigma\parallel\gamma\), then we have the following: If \(e(v)=\mathrm{TrDup}\), we can remove \(v^{\prime}\) without adding new losses; If \(X\subseteq Y\), then \(x(v)\subseteq x(v^{\prime})\subseteq x(w)\).