# Predicting the Evolution of Syntenies--An Algorithmic Review
## 5 Accounting for Gene Trees
### The Reconciliation Approach  
Given a gene tree \(T\) and a species tree \(S\) representing the true bifurcation histories of the considered gene family and set of species, respectively, inferring the scenario of gene gain and loss explaining the difference between the two trees is the purpose of the gene-tree-species-tree-reconciliation approach [2; 17]. A _Reconciliation_ of \(T\) with respect to \(S\) is usually defined as an _event-labeled_ extension of \(T\), where an internal node label represents the event at the origin of the bifurcation, and grafted branches represent lost (or missing) genes. The considered events are most often speciation, duplications and possibly HGTs. In particular, a most parsimonious reconciliation minimizing the number \(D(T,S)\) of Duplications (the D-distance) or the number \(DL(T,S)\) of Duplications and Losses (the DL-distance) can be found in linear time using the LCA (Last Common Ancestor) mapping [85; 86; 87].  
Given a tree \(T\), an extension \(R\) of \(T\) (\(R\) can be equal to \(T\)), and a mapping \(s\) from \(\mathcal{L}(T)\) to \(V(S)\) (indicating the genome to which the gene associated with each leaf of \(T\) belongs), _an extension of \(s\)_ is a function \(\tilde{s}\) from \(V(R)\) to \(V(S)\) such that for each leaf \(x\) of \(T\), \(\tilde{s}(x)=s(x)\). Considering an evolutionary model for a gene family accounting for Duplications (D) and Losses (L) in addition to speciation, the \(DL\)-_reconciliation_ of \(T\) with respect to \(S\) is defined as follows.  
**Definition 1** (DL-reconciliation).: _Let \(\Gamma\) be a gene family where each \(x\in\Gamma\) belongs to the species \(s(x)\) of \(\Sigma\). Let \(T\) be a binary gene tree for \(\Gamma\) and \(S\) be a binary species tree for \(\Sigma\). A DL-reconciliation is a triplet \(\langle R,\tilde{s},\tilde{e}\rangle\) where \(R\) is an extension of \(T\) and \(\tilde{s}\) is an extension of \(s\) such that for each binary node \(x\) of \(R\) with two children \(x_{l}\) and \(x_{r}\), one of the following cases holds:_  
1. \(\tilde{s}(x_{l})\) _and_ \(\tilde{s}(x_{r})\) _are the two children of_ \(\tilde{s}(x)\) _in_ \(S\) _in which case_ \(\tilde{e}(x)=Spe\)_;_
2. \(\tilde{s}(x_{l})=\tilde{s}(x_{r})=\tilde{s}(x)=\sigma\) _in which case_ \(\tilde{e}(x)=Dup\) _representing a duplication in_ \(\sigma\)_;_  
_A grafted leaf on a newly created node \(x\) corresponds to a loss in \(\tilde{s}(x)\)._  
As \(R\) is as an extension of \(T\), each node in \(T\) has a corresponding node in \(R\). In other words, we can consider that \(V(T)\subseteq V(R)\). In particular, the species labeling on \(R\) induces a species labeling on \(T\).  
Given a cost function \(c\) on duplications and losses and a reconciliation \(\mathcal{R}=\langle R,\tilde{s},\tilde{e}\rangle\), the cost \(c(\mathcal{R})\) is the sum of costs of the induced events.  
Given a cost of \(0\) for speciation and a unitary cost for duplications and losses, the DL-reconciliation \(\langle R,\tilde{s},\tilde{e}\rangle\) of minimum cost \(DL(T,S)\) is unique and obtained from \(\tilde{s}\) being the LCA-mapping, i.e., verifying, for any internal node \(x\) of \(V(R)\cap V(T)\), \(\tilde{s}(x)=lca_{S}(s(\mathcal{L}(T[x])))\). We also refer to this reconciliation as the _lca-reconciliation_. See Figure 3 for an illustration.