# Predicting the Evolution of Syntenies--An Algorithmic Review
## 5 Accounting for Gene Trees
### Evolution of Tandemly Arrayed Gene Clusters  
An important class of syntenic regions is constituted by Tandemly Arrayed Gene clusters (TAGs). Slippage during recombination, a mechanism at the origin of tandem repeats which is favored by the presence of repetitive sequences, induces a chain reaction eventually leading to the creation of large TAGs, i.e., groups of paralogous genes that are adjacent on a chromosome. TAGs account for about one third of the duplicated genes in eukaryotes [117]. In human, they represent about 15% of all genes [118] forming a number of complex gene clusters. Those repeated regions are however extremely difficult to study or even to assemble correctly due to the fact that during evolution, the duplication status of segments is obscured by subsequent deletions, breaks and rearrangements. When the step of determining the linear gene composition of a TAG cluster is completed, inferring an evolutionary scenario for the tandemly repeated genes is further complicated by the fact that the phylogenetic signal is often obscured by gene conversion. Methods based on a preprocessing of a self-alignment dot-plot of a cluster or the dot-plot of a pairwise-alignment of two clusters have been developed for reconstructing a hypothetical ancestral sequence and a duplication scenario leading to an observed gene cluster [119; 120; 121]. Although these methods are useful to infer recent evolutionary events, they are less appropriate for longer timescales as alignment of the nonfunctional regions becomes impossible due to mutations continuously affecting each duplicated segment. Assuming correct gene orders and gene trees have been obtained, the problem of inferring the evolutionary scenario of a set of TAG clusters can be handled using the _tandem-duplication model of evolution_ first introduced by [PERSON] in 1977 [122]. This model assumes that from a single ancestral gene at a given position in the chromosome, the locus grows through a series of consecutive duplications placing the newly created copy next to the original one. Such tandem duplications may be _simple_ (duplication of a single-gene) or _multiple_ (simultaneous duplication of neighboring genes). Based on this idea, several theoretical studies have considered the problem of reconstructing the tandem-duplication history of a single TAG cluster through tandem duplications only (which is not always possible) [123]. The model has been extended to the study of a set of orthologous TAG clusters, with an evolutionary model accounting for losses and rearrangements, in addition to simple tandem duplications [124; 125]. Later, [PERSON] et al. [126] developed the DILTAG algorithm inferring all most parsimonious evolutionary histories for a single gene cluster, according to a general cost model involving simple and multiple tandem duplications, deletions and inversions. Figure 7: The gene tree \(T\) is event-labeled according to the lca-mapping with the species tree \(S=((A,B),C)\). A leaf \(x_{i}\) of \(T\) denotes a gene copy in genome \(X\), its index \(i\) corresponding to its position in the TAG cluster of genome \(X\), as illustrated on the tips of the species tree \(S\) on the right. DILTAG proceeds by exploring a \"history graph\" (search space), where vertices correspond to _ordered gene trees_, i.e., gene trees with ordered leaves (gene orders), and edges to evolutionary events. The size of the whole search-space being exponential, a greedy heuristic was developed that only conserves, in a queue, the most promising partial evolutionary histories obtained after exploring a given depth of the history graph. In [PERSON] et al. (2017), DILTAG was then used for inferring the evolution of a set of orthologous TAGs (see Figure 7 for an example). The developed MultiDILTAG algorithm proceeds in two steps. First, ignoring gene orders, an lca-reconciliation of the gene tree \(T\) with the species tree \(S\) is computed, leading to a set \(\Gamma(x)\) of ancestral genes at each internal node \(x\) of \(S\).