# Synesth: Comprehensive Syntenic Reconciliation with Unsampled Lineages
## 6 Polynomial-Time Computation of Pareto-Optimal Event Vectors  
We now address Problem 2. Given a synteny tree \(\mathcal{T}=\langle T,x,s\rangle\) on a species tree \(S\), similar to the way \(h(v,X,\sigma)\) was previously used to recursively compute \(\mathbb{H}^{\min}(\mathcal{T},S)\), we define \(\Lambda(v,X,\sigma)\) for computing \(\operatorname{ev}^{\min}(\mathcal{T},S)\) as \(\Lambda(v,X,\sigma)=\{\operatorname{ev}(\mathcal{H})\mid\mathcal{H}\in h(v,X,\sigma)\}\). To compute \(\Lambda(v,X,\sigma)\), we replace the algebra of Theorem 1 with an algebra where:  
* The base cases are \(\{(0,0,0,0,0)\}\) and \(\emptyset\);
* \(A\oplus B\) is the union of vectors from \(A\) and \(B\), retaining only the Pareto-optimal ones;
* \(A\otimes B\) sums the pairs of vectors from \(A\times B\), retaining only the Pareto-optimal ones. Additional simplifications can reduce the complexity of computing \(\Lambda(v,X,\sigma)\). We start by showing that, when adapted for Problem 2, it is sufficient to try a constant number of syntenies \(X,Y,Z\subseteq\mathcal{F}\) at each step of the recurrence of Theorem 1. First, let us show that it is sufficient to place the gain event for each gene family at the lowest common ancestor of the leaves they appear in. Definition 10 (Gain positions): Let \(\mathcal{T}=\langle T,x,s\rangle\) be a synteny tree on \(\mathcal{F}\), \(\Gamma\in\mathcal{F}\), \(v\in\operatorname{V}(T)\), and \(X\subseteq\mathcal{F}\). We thus define  
\[\operatorname{lca}(\Gamma) =\operatorname{lca}_{\mathcal{T}}\{l\in\operatorname{L}(T)\mid \Gamma\in x(l)\},\] \[f(v,X) =\{\Gamma\in X\mid\operatorname{lca}(\Gamma)\
ot>v\}.\]  
Lemma 1 (Gains at the LCA): If \(\mathcal{T}=\langle T,x,s\rangle\) is a synteny tree on \(\mathcal{F}\), \(v\in\operatorname{V}(T)\), and \(X\subseteq\mathcal{F}\), then \(\min_{\preceq}\left(\Lambda(v,X,\sigma)\cup\Lambda(v,f(v,X),\sigma)\right)= \Lambda(v,f(v,X),\sigma)\). Proof. : Let \(\mathcal{H}\in h(v,X,\sigma)\). Let \(\Gamma\in X-f(v,X)\), if there is any. By definition, \(\operatorname{lca}(\Gamma)>v\). Assume w.l.o.g. that \(\operatorname{lca}(\Gamma)\geq v_{\ell}\). Consider the history \(\mathcal{H}^{\prime}\) in which \(\Gamma\) is removed from \(x(v)\) and all \(x(w)\) for \(w\in T[v_{\mathrm{r}}]\), thereby removing any invalid loss event created in the process, and in which the gain event for \(\Gamma\) is moved to be the parent of \(v_{\mathrm{r}}\) (potentially merging it with other gains). Then, \(\operatorname{ev}(\mathcal{H}^{\prime})\preceq\operatorname{ev}(\mathcal{H})\), since we only potentially removed losses from \(\mathcal{H}\) and the number of gains is not part of the event vector. Let \(\mathcal{H}^{*}\) be the history obtained after repeating this process for each \(\Gamma\in X-f(v,X)\). Clearly, \(\mathcal{H}^{*}\in h(v,f(v,X),\sigma)\); hence, \(e(\mathcal{H}^{*})\in\Lambda(v,f(v,X),\sigma)\) and \(\operatorname{ev}(\mathcal{H}^{*})\preceq\operatorname{ev}(\mathcal{H})\). In a similar way to Lemma 5 in [10], we now show that only two synteny contents have to be tried at each step of the recurrence as any synteny larger than the minimal required gene families (as formally defined below) leads to the same set of optimal event vectors. Definition 11 (Minimal synteny contents): For any \(v\in\operatorname{V}(T)\), we define  
\[\operatorname{gain}(v) =\{\Gamma\in\mathcal{F}\mid v=\operatorname{lca}(\Gamma)\},\] \[x^{\min}(v) = \begin{cases}x(v)&\text{if $v$ is a leaf,}\\ x^{\min}(v_{\ell})\cup x^{\min}(v_{\mathrm{r}})-(\operatorname{gain}(v_{ \ell})\cup\operatorname{gain}(v_{\mathrm{r}}))&\text{otherwise.}\end{cases} \]  
Lemma 2 (Two choices of synteny contents): Let \(\mathcal{T}=\langle T,x,s\rangle\) be a synteny tree on a species tree \(S\) and \(v\) be a node of \(T\). For any \(X,X^{\prime}\supsetneq x^{\min}(v)\) such that \(X=f(v,X)\) and \(X^{\prime}=f(v,X^{\prime})\), \(\Lambda(v,X,\sigma)=\Lambda(v,X^{\prime},\sigma)\). Proof. : We proceed by induction on the depth of \(v\) in \(T\).