# Predicting the Evolution of Syntenies--An Algorithmic Review
## 5 Accounting for Gene Trees
### Adjacency Evolution  
Rather than considering each gene family independently, a first approach towards integrating dependency information between genes is to account for gene adjacencies. This is the goal of the DeCo algorithm [88] integrating gene tree and gene order information for the purpose of inferring the evolution of syntenies, where syntenies are restricted to adjacencies, i.e., segments of two genes. Figure 3: A gene tree \(T\) for the gene family \(\Gamma=\{a_{1},b_{1},b_{2},c_{1},d_{1}\}\), where a gene \(x_{i}\) belongs to the genome \(X\); a species tree \(S\) for the genomes \(\Sigma=\{A,B,C,D\}\); a DL-reconciliation \(\langle R,\tilde{s},\tilde{e}\rangle\) of cost \(DL(T,S)\), where \(S\) is represented by the letter and \(\tilde{e}\) by the label (rectangle or plain circle) assigned to each internal node of \(R\). On the right, a representation of \(R\) embedded in the species tree \(S\). More precisely, given a set of gene families, each represented by a reconciled gene tree, i.e., a gene tree node labeled by the event (D or S) at the origin of the bifurcation represented by each internal node, and given a set of adjacencies between genes, the algorithm seeks for an evolutionary scenario of the adjacencies in agreement with the reconciled gene trees, and minimizing adjacency gain and breakage. Considering an appropriate clustering of adjacencies, the problem is shown to reduce to a set of problems with exactly two gene trees where all adjacencies are between those two trees. Therefore, the input of the DeCo algorithm is a pair of event-labeled gene trees (reconciled gene trees) and a set of adjacencies between the two trees, and the result is a forest of adjacency trees (called _adjacency forest_) of minimum cost (determined by adjacency gain and breakage), where an adjacency tree describes the descent pattern of adjacencies: for adjacency AB to descent from an adjacency CD, gene A should descent from gene C and gene B from gene D. An adjacency tree is event-labeled, where an event-labeling an internal node may be a speciation, an adjacency duplication or a gene duplication. Adjacency breakage and gene loss are represented by grafted edges, and adjacency gains are the roots of new trees (see Figure 4, inspired from Figure 2 in [88], for an illustration). A polynomial-time dynamic programming algorithm is developed, based on a set of recurrences detailing all the cases of adjacency breakage or gain, depending on whether only one or the two genes of an adjacency are duplicated or lost, together or separately. Applied on an arbitrary set of adjacencies between an arbitrary set of gene trees, the DeCo approach infers a set of ancestral adjacencies for the ancestral species of a species tree. However, as each adjacency is considered independently from the others, inferred ancestral adjacencies are not guaranteed to be compatible with a linear structure. Although this may be seen as a drawback of the method, it can also be used as benchmark for correcting gene trees [89]. As reviewed in [18], following the initial model, several extensions of DeCo have been considered, such as accounting for horizontal gene transfers (see Section 5.6) [90], or handling fragmented extant genome assemblies (Art-DeCo) [91]. These extensions are  
Figure 4: **(1)** Input of DeCO: a set of adjacencies between two gene families, the red and blue ones, in two genomes A and B; reconciled gene trees for the red and blue families, where rectangles are gene duplications, plain circles are speciation and dotted lines are grafted edges for gene losses; **(2)** An evolutionary history embedded in the species tree \(S=(A,B)\) explaining the evolution of the adjacencies through gene duplication, speciation and gene loss; **(3)** The output of DeCO in the form of a forest of two trees, representing the evolutionary history of **(2)**. The simultaneous duplication of the two adjacent genes corresponding to \(E_{S}\) and \(E_{B}\) is an adjacency duplication. The dotted line represents a gene loss.