# Synesth: Comprehensive Syntenic Reconciliation with Unsampled Lineages
## 4 Explicatory Histories and Optimization Problems
Note that \(\mathbb{H}(\mathcal{T},S)\) is infinite: given any explicatory history, it is always possible to extend it into a larger one by introducing superfluous duplications or transfers. We next define a way to reduce this space to a finite one. **Definition 5** (Event vector). : _Let \(\mathcal{H}=\langle H,e,x,s\rangle\) be a history. We define \(\mathrm{ev}(\mathcal{H})=(c_{\mathrm{Dup}},c_{\mathrm{Cut}},\)\(c_{\mathrm{TrDup}},c_{\mathrm{TrCut}},c_{\mathrm{Loss}})\in\mathbb{N}^{5}\) as the vector such that \(c_{e}\) is the number of events of type \(e\in\mathcal{E}\) in \(\mathcal{H}\)._  
As usual for reconciliation, our definition of an event vector excludes the number of speciations since they do not allow one to meaningfully distinguish between histories. Notice that the number of gains is also excluded, as needed to make the problem of Section 6 tractable. Consequently, we disregard taking advantage of the simultaneous gains of multiple genes to reduce the overall number of individual gain events. **Definition 6** (Order on vectors and histories). : _For two event vectors \((a_{i})_{1\leq i\leq n}\) and \((b_{i})_{1\leq i\leq n}\), \((a_{i})\preceq(b_{i})\) if for all \(i\in\{1,...,n\}\), \(a_{i}\leq b_{i}\). This partial order induces another one on the histories, namely \(\mathcal{H}\preceq\mathcal{H}^{\prime}\) if \(\mathrm{ev}(\mathcal{H})\preceq\mathrm{ev}(\mathcal{H}^{\prime})\)._  
**Definition 7** (Pareto optimality). : _For any set \(E\) with a partial order \(\preceq\), we define its Pareto subset as \(\min\preceq E=\{x\in E\mid\forall y\in E,(x\
eq y)\rightarrow\
eg(y\preceq x)\}\)._  
As an example, in the set of vectors \(A=\{(1,2),(2,2),(3,1)\}\subseteq\mathbb{N}^{2}\), we have \((1,2)\preceq(2,2)\) while \((1,2)\) and \((3,1)\) are not comparable; hence, \(\min\preceq A=\{(1,2),(3,1)\}\). Let us now consider the set \(\mathbb{H}^{\min}(\mathcal{T},S)=\min{}_{<}\mathbb{H}(\mathcal{T},S)\) of histories whose event vectors are Pareto-optimal. As opposed to \(\mathbb{H}(\mathcal{T},S)\), \(\mathbb{H}^{\min}\) is a finite set, as we will show in Theorem 3. We can thus meaningfully define the problem of computing this set. **Problem 1 (All Pareto-optimal histories). **  
_Input_: A synteny tree \(\mathcal{T}\) and a species tree \(S\). _Output_: The set \(\mathbb{H}^{\min}(\mathcal{T},S)\) of Pareto-optimal histories explicating \(\mathcal{T}\) and \(S\). Even though \(\mathbb{H}^{\min}\) is finite, it may contain a number of optimal histories that are exponential in \(|V(T)|\). Rather, consider the set \(\mathrm{ev}^{\min}(\mathcal{T},S)=\min{}_{\preceq}\{\mathrm{ev}(\mathcal{H}) \mid\mathcal{H}\in\mathbb{H}(\mathcal{T},S)\}\) of Pareto-optimal event vectors. As we will show later (Theorem 4), the number of optimal event vectors in \(\mathrm{ev}^{\min}\) is polynomial. We now consider the following problem of reduced complexity:  
**Problem 2 (All Pareto-optimal vectors). **  
_Input_: A synteny tree \(\mathcal{T}\) and a species tree \(S\). _Output_: The set \(\mathrm{ev}^{\min}(\mathcal{T},S)\). Now, given a vector of costs for each event type \(\delta=(\delta_{\mathrm{Dup}},\delta_{\mathrm{Cut}},\delta_{\mathrm{TDup}}, \delta_{\mathrm{TCut}},\delta_{\mathrm{Loss}})\in(\mathbb{R}^{+}\cup\{\infty\}) ^{5}\), we can associate an overall scalar cost \(\mathrm{c}(\mathcal{H})=\delta\cdot\mathrm{ev}(\mathcal{H})\) to each history. **Problem 3 (Minimum cost). **  
_Input_: A synteny tree \(\mathcal{T}\), a species tree \(S\), and a vector \(\delta\in(\mathbb{R}^{+}\cup\{\infty\})^{5}\). _Output_: The minimum cost \(c^{\min}(\mathcal{T},S)=\min\{\mathrm{c}(\mathcal{H})\mid\mathcal{H}\in\mathbb{ H}(\mathcal{T},S)\}\) of any history explicating \(\mathcal{T}\) and \(S\). Finally, we will call Problems 2' and 3' the versions of Problems 2 and 3 where we additionally ask for one history corresponding to each returned optimal event vector (for Problem 2') or one history for the returned minimum cost (for Problem 3').