# Synesth: Comprehensive Syntenic Reconciliation with Unsampled Lineages
## 5 Generating All Pareto-Optimal Histories  
We start by addressing Problem 1, which asks to enumerate the \(\mathbb{H}^{\min}\) set. This can be conducted inductively by building histories from the leaves of the synteny tree up to its root. This result is the basis for the dynamic programming formulations introduced for the other problems in the upcoming sections. The next two definitions are used to build histories by composing partial histories (see Figure 2). In the following, a node \(v\) of a history such that \(x(v)=X\) and \(s(v)=\sigma\) is denoted as \(v[X,\sigma]\), or \(v[e,X,\sigma]\) if the event \(e\in\mathcal{E}\) associated to \(v\) is known. The node name may be omitted where it is not relevant by simply writing \([X,\sigma]\) or \([e,X,\sigma]\). If \(A\), \(B\), and \(C\) are three nodes, then \((A,B)C\) refers to the triplet tree with Root \(C\) and Leaves \(A\) and \(B\). **Definition 8** (Partial histories). : _Let \(\mathcal{T}=(T,x,s)\) be a synteny tree on a species tree \(S\). Let \(v\in\mathrm{V}(T)\), \(X\subseteq\mathcal{F}\), and \(\sigma\in\mathrm{V}(S^{*})\). We define \(h(v,X,\sigma)\) as the set of the Pareto-optimal histories explicating the subtree of \(\mathcal{T}\) rooted at \(v[X,\sigma]\). We also define \(\mathrm{path}([X,\sigma],[Y,\gamma])\) as the set of Pareto-optimal acyclic histories whose root is \([X,\sigma]\) and whose only visible leaf is \([Y,\gamma]\). Formally,_  
\[h(v,X,\sigma) =\{\langle H,e,x,s\rangle\in\mathbb{H}^{\min}(\mathcal{T}[v],S) \mid(\mathrm{r}(H)=v)\land(x(v)=X)\land(s(v)=\sigma)\}\] \[\mathrm{path}([X,\sigma],[Y,\gamma]) =\min{}_{\preceq}\{\mathcal{H}=\langle H,e,x,s\rangle\mid(x( \mathrm{r}(H))=X)\land(s(\mathrm{r}(H))=\sigma)\] \[\land(\mathrm{L}_{V}(\mathcal{H})=\{l\})\land(x(l)=Y)\land(s(l)=\gamma)\] \[\land\mathcal{H}\text{ is acyclic}\}.\]  
**Definition 9** (History composition). : _If \(\mathcal{H}=\langle H,e,x,s\rangle\) and \(\mathcal{H}^{\prime}=\langle H^{\prime},e^{\prime},x^{\prime},s^{\prime}\rangle\) are two histories such that there exists a leaf \(l\in\mathrm{L}(H)\) with \(x(l)=x(\mathrm{r}(H^{\prime}))\) and \(s(l)=s(\mathrm{r}(H^{\prime}))\), then we define their composition \(\mathcal{H}\otimes\mathcal{H}^{\prime}\) as the history obtained by replacing \(l\) with \(\mathrm{r}(H^{\prime})\) and merging \(e\) with \(e^{\prime}\), \(x\) with \(x^{\prime}\), and \(s\) with \(s^{\prime}\). This operation is only defined if the resulting history is valid (particularly if no gene family would be gained in two separate \(\mathrm{Gain}\) events)._  
_When applied to two_ sets _of histories_ \(A\) _and_ \(B\)_, then_ \(A\otimes B\) _is defined by taking the Cartesian product of the two sets and composing each resulting history pair whilst excluding invalid compositions._  
_For any node \(v\) of a syntenty tree \(\mathcal{T}\) and any event \(e\in\mathcal{E}\), syntenies \(X,Y,Y^{\prime},Z,Z^{\prime}\subseteq\mathcal{F}\), and species \(\sigma,\gamma_{\ell_{\ell}},\gamma^{\prime}_{\ell_{\ell}},\gamma_{\tau_{\ell} },\gamma^{\prime}_{\tau}\in\mathrm{V}(S^{*})\), we define the set of histories starting with \(v[e,X,\sigma]\) as followed by two paths from \([Y^{\prime},\gamma^{\prime}_{\ell}]\) to \(v_{\ell}[Y,\gamma_{\ell}]\) and from \([Z^{\prime},\gamma^{\prime}_{\tau}]\) to \(v_{\tau}[Z,\gamma_{\tau}]\), thereby leading to two sub-histories as follows:_  
\[\mathcal{M}(v[e,X,\sigma],[Y^{\prime},\gamma^{\prime}_{\ell}],v_{ \ell}[Y,\gamma_{\ell}],[Z^{\prime},\gamma^{\prime}_{\tau}],v_{\tau}[Z,\gamma_ {\tau}])\] \[=([Y^{\prime},\gamma^{\prime}_{\ell}],[Z^{\prime},\gamma^{\prime }_{\tau}])\;v[e,X,\sigma] \otimes(\mathrm{path}([Y^{\prime},\gamma^{\prime}_{\ell}],v_{ \ell}[Y,\gamma_{\ell}])\otimes h(v_{\ell},Y,\gamma_{\ell}))\] \[\otimes(\mathrm{path}([Z^{\prime},\gamma^{\prime}_{\tau}],v_{ \tau}[Z,\gamma_{\tau}])\otimes h(v_{\tau},Z,\gamma_{\tau})).\]  
For example, in Figure 2, we have \(\mathcal{H}=\mathcal{M}(v[\mathrm{Spe},X,\sigma],[X,\sigma_{\ell}],v_{\ell}[Y,\gamma_{\ell}],[X,\sigma_{\tau}],v_{\tau}[Z,\gamma_{\tau}])\).