# Predicting the Evolution of Syntenies--An Algorithmic Review
## 5 Accounting for Gene Trees
### Evolution through Segmental Duplications and Losses
#### 5.3.2 Super-Reconciliation  
Given a set of gene families \(\mathcal{G}=\{\Gamma_{1},\Gamma_{2},\cdots,\Gamma_{t}\}\) organized into a set of syntenies \(\mathcal{X}\), a synteny tree \(T\) for \(\mathcal{X}\) and a species tree \(S\) for the set \(\Sigma\) of species containing the syntenies, the problem is to infer a scenario of segmental duplications and losses explaining \(T\) with respect to \(S\). Therefore, at this stage, the super-reconciliation problem can be seen as a generalization of the classical reconciliation problem allowing for segmental events.  
In [94; 95], this problem is handled by a two-step algorithm: First label the internal nodes of \(T\) as duplications or speciation following the LCA-mapping (Figure 5(3), left), and then infer an optimal scenario of losses in agreement with this event-labeled tree \(\hat{T}\) (Figure 5(3), right). This two-steps method has been shown exact, i.e., leading to a super-reconciliation of minimum cost (DL-distance).  
The main problem is the second step which consists of extending the tree \(\hat{T}\) with losses and infer the actual event at each node (i.e., the corresponding synteny and segment being duplicated or lost). As losses and segments affected by the events are fully determined by gene orders assigned to internal nodes, the problem actually reduces to the small phylogeny problem, i.e., the problem of assigning syntenies to internal nodes of \(\hat{T}\).  
For \(x\in V(\hat{T})\), define \(d(x,X)\) as the minimum number of segmental duplications and losses induced by a synteny assignment of \(\hat{T}_{x}\) with \(X\) being the assignment at \(x\). The Small Phylogeny for Syntenies problem is to find an optimal assignment, i.e., an assignment leading to \(d(\hat{T})=\min_{X}d(r(\hat{T}),X)\) for \(X\) belonging to the set of syntenies that are order-consistent with \(\mathcal{X}\).  
Let \(x\) be an internal node of \(\hat{T}\) and \(x_{t}\), \(x_{r}\) be its two children. Let \(X\), \(X_{t}\), \(X_{r}\) be valid assignments for respectively \(x\), \(x_{1}\) and \(x_{r}\). Then \(X_{t}\) and \(X_{r}\) are subsequences of \(X\). If \(x\) is a speciation, then all missing genes in \(X_{t}\) and \(X_{r}\) result from losses. Otherwise, if \(x\) is a duplication, then for at most one of \(X_{i}\) and \(X_{r}\), the missing prefix or suffix can be due to the partial duplication of a segment of \(X\), and all other missing genes should be losses. Therefore, we define two distances: \(D^{T}(X,Y)\) for the minimum number of segmental losses required to transform \(X\) to \(Y\) and \(D^{P}(X,Y)\) for the minimum number of segmental losses required to transform a substring of \(X\) to \(Y\).  
Based on the above observations, recurrence relations are defined for a dynamic programming algorithm computing \(d(x,X)\), for each \(x\in V(\hat{T})\) and each possible synteny \(X\). The exponential-time complexity of the algorithm is due to the exponential size of the set of syntenies that should be considered at each internal node of \(\hat{T}\).