# Synesth: Comprehensive Syntenic Reconciliation with Unsampled Lineages
## 3 Evolutionary Histories for Syntenies  
We model the evolution of syntenies through the following syntenic events: codivergence with the host species (\"Spe\"), duplication of a synteny subset (\"Dup\"), fission of a synteny (\"Cut\"), transfer of a duplicated or cut subset (resp. \"TrDup\" or \"TrCut\"), and the gain or loss of a subset (\"Gain\", \"Loss\"). Losses can be partial in the sense that only a subset of genes in a synteny are lost. Evolutionary histories are the sequences of such events, as formally defined below (see example in Figure 1). **Definition 1** (Evolutionary history for syntenies). : _A history \(\mathcal{H}\) on a species tree \(\mathcal{S}\) is a tuple \(\langle H,e,x,s\rangle\), where \(H\) is a partially binary tree. Each node \(v\in\mathrm{V}(H)\) is labeled with a species \(s(v)\in\mathrm{V}(S)\) and a synteny (i.e., a subset of gene families) \(x(v)\). Each internal node is additionally labeled with an event \(e(v)\in\mathcal{E}=\{\mathrm{Spe},\mathrm{Dup},\mathrm{Cut},\mathrm{TrDup}, \mathrm{TrCut},\mathrm{Gain},\mathrm{Loss}\}\) acting on \(x(v)\) and \(s(v)\). These labels satisfy the following conditions:_  
1. _If_ \(e(v)=\mathrm{Spe}\)_, with_ \(\mathrm{ch}(v)=\{v^{\prime},v^{\prime\prime}\}\) _and_ \(\sigma=s(v)\)_, then_ \(x(v)=x(v^{\prime})=x(v^{\prime\prime})\)_,_ \(s(v^{\prime})=\sigma_{\ell}\)_, and_ \(s(v^{\prime\prime})=\sigma_{\tau}\)_._
2. _If_ \(e(v)\in\{\mathrm{Dup},\mathrm{Cut},\mathrm{TrDup},\mathrm{TrCut}\}\)_, with_ \(\mathrm{ch}(v)=\{v_{\mathrm{r}},v_{\mathrm{k}}\}\)_:_ 1. _If_ \(e(v)\in\{\mathrm{Dup},\mathrm{TrDup}\}\)_, then_ \(x(v_{\mathrm{r}})\subseteq x(v)=x(v_{\mathrm{k}})\)_;_ 2. _If_ \(e(v)\in\{\mathrm{Cut},\mathrm{TrCut}\}\)_, then_ \(x(v_{\mathrm{r}})\cup x(v_{\mathrm{k}})=x(v)\)_,_ \(x(v_{\mathrm{r}})\cap x(v_{\mathrm{k}})=\emptyset\)_, and_ \(x(v_{\mathrm{r}})\
eq\emptyset\) _(but_ \(x(v_{\mathrm{k}})=\emptyset\) _is allowed);_ 3. _If_ \(e(v)\in\{\mathrm{Dup},\mathrm{Cut}\}\)_, then_ \(s(v)=s(v_{\mathrm{r}})=s(v_{\mathrm{k}})\)_;_ 4. _If_ \(e(v)\in\{\mathrm{TrDup},\mathrm{TrCut}\}\)_, then_ \(s(v)\parallel s(v_{\mathrm{r}})\)_, and_ \(s(v)=s(v_{\mathrm{k}})\)_._
3. _If_ \(e(v)\in\{\mathrm{Gain},\mathrm{Loss}\}\) _with_ \(\mathrm{ch}(v)=\{v_{\mathrm{c}}\}\)_, then_ \(s(v_{\mathrm{c}})=s(v)\) _and the following:_ 1. _If_ \(e(v)=\mathrm{Gain}\)_, then_ \(x(v_{\mathrm{c}})\supseteq x(v)\)_._ 2. _If_ \(e(v)=\mathrm{Loss}\)_, then_ \(x(v_{\mathrm{c}})\subsetneq x(v)\) _(a loss is_ full _if_ \(x(v_{\mathrm{c}})=\emptyset\)_, and_ partial _otherwise)._
4. _For each gene family_ \(\Gamma\)_, exactly one_ Gain _event in_ \(H\) _involves_ \(\Gamma\)_._
5. _The only nodes_ \(v\) _of the history such that_ \(x(v)=\emptyset\) _are its root and its leaves._ _Finally, we denote by_ \(\mathrm{Tr}\) _any event in_ \(\{\mathrm{TrDup},\mathrm{TrCut}\}\)_._  
Notice that, when the sets of \(x(v)\) are restricted to at most one gene family each, this model reduces to the classical reconciliation model of [14], with TrDup corresponding to \(\mathbb{T}\) (transfer) and TrCut to \(\mathbb{TL}\) (transfer-loss). Additionally, from any syntenic history on a set of gene families \(\mathcal{F}\), one can extract a reconciled gene tree for each gene family \(\Gamma\in\mathcal{F}\) whose root is the gain event for \(\Gamma\) and leaves are the loss events where \(\Gamma\) is lost. This root is unique because of Condition (4), which excludes _convergent gains_. Moreover, as in [14], we will allow for transfers to and from unsampled or extinct species by augmenting the species tree. For example, in Figure 1, Synteny \(\{1,2\}\) in Species \(A\) is the result of a transfer from an unsampled species. In the following, unless specified otherwise, all histories are on augmented species trees, as formally defined below. **Definition 2** (Augmented species tree).