# Synesth: Comprehensive Syntenic Reconciliation with Unsampled Lineages
## 4 Explicatory Histories and Optimization Problems  
The goal of reconciliation is to infer histories that _explicate_ the topology of a synteny tree given a tree of the corresponding species. Such histories are extensions of the synteny tree that map all leaves to the appropriate species and syntenies without introducing new _visible_ leaves. Figure 1: (1) A _synteny tree_\(\mathcal{T}\) (on the **left**) with an augmented _species tree_\(S^{*}\) (on the **right**). The numbers represent single gene families and the letters represent species. As indicated by the dashed gray lines connecting the two trees, the Syntenies \(\{1,2\}\), \(\{2,3\}\), and \(\{1,3\}\) belong to Species **A**, \(\{2,3\}\), and \(\{1,2\}\) to **B**\(\{3\}\) and \(\{1,2\}\) to **C**. The dotted lines in the augmented species tree represent unsampled edges. (2) An output _history_\(\mathcal{H}\) of Synseth when given \(\mathcal{T}\) and \(S^{*}\) as the input with costs \((\delta_{\mathrm{Dup}}=2,\delta_{\mathrm{Cut}}=2.5,\delta_{\mathrm{Dup}}=3, \delta_{\mathrm{Cut}}=3.5,\delta_{\mathrm{Loss}}=1)\). The history tree is represented with black lines on top of the species tree filled in gray. The hatched background represents a part of the history taking place in an unsampled lineage. The events are represented as follows: “Spe” by ovals, “Dup” and “Cut” by rectangles, “TrDup” and “TrCut” by diamonds, “Loss” by right half-circles, and “Gain” by left half-circles. The synteny contents are written inside of each event, while the associated species is represented implicitly by the position of each event on top of the species tree. Duplicated or transferred genes are underlined, while fissions are represented by a separation in the synteny. **Definition 3** (Visible leaves). : _A leaf \(l\) of a history \(\mathcal{H}=\langle H,e,x,s\rangle\) is said to be visible if \(x(l)\
eq\emptyset\) and \(s(l)\in\mathrm{V}(S)\), and invisible otherwise. The set of visible leaves of \(\mathcal{H}\) is denoted as \(\mathrm{L}_{V}(\mathcal{H})\)._  
For example, in Figure 1, the history in (2) explicates the trees in (1). In that history, the only invisible leaf is the unnamed leaf in the hatched region (representing an unsampled species). The leaves below full losses would also be invisible, but that example history does not contain any full loss. The following is a formal definition of an explicatory history:  
**Definition 4** (Explicatory histories). : _For a species tree \(S\), a history \(\mathcal{H}=\langle H,e,x,s\rangle\) on \(S^{*}\) is said to explicate a synteny tree \(\mathcal{T}=\langle T,x^{\prime},s^{\prime}\rangle\) and \(S\) if the following holds true:_  
1. \(H\) _is an extension of_ \(T\)_._
2. \(x^{\prime}=x|_{\mathrm{L}(T)}\) _and_ \(s^{\prime}=s|_{\mathrm{L}(T)}\)_._
3. \(\mathrm{L}_{V}(\mathcal{H})=\mathrm{L}(T)\)_._
4. _No_ \((u,v)\in\mathrm{E}(T)\) _is such that_ \(s(v)<s(u)\)_._
5. _No gain event is the parent of a node_ \(v\in\mathrm{V}(H)-\mathrm{V}(T)\)_._
6. _No partial loss event is a child of a node_ \(v\in\mathrm{V}(H)-\mathrm{V}(T)\)_._  
_The set of all such histories is denoted by \(\mathbb{H}(\mathcal{T},S)\)._  
Condition (3) disallows introducing new visible leaves. Condition (4) excludes assignments of species that create cycles between adjacent nodes of the synteny tree. This condition is a necessary, but not sufficient, condition for acyclicity. Imposing a full acyclicity condition would lead to computationally intractable problems [4]. As for Conditions (5) and (6), they are introduced to avoid having multiple histories with the same events, but with gains and losses distributed differently between the adjacent nodes of the synteny tree. More precisely, Condition (5) requires sifting gains down and merging them until they are the parent of a synteny tree node; conversely, Condition (6) requires sifting losses up and merging them until they are the child of a synteny tree node.