# Predicting the Evolution of Syntenies--An Algorithmic Review
## 3 The Sorting by Rearrangement Problem
#### The Small Phylogeny Problem  
Inferring the evolutionary history of a set of syntenies represented as gene orders has mainly been handled as a Small Phylogeny Problem[47]. Given a single synteny per genome (i.e., no paralogous syntenies in the same genome are allowed), and given a known phylogenetic tree for the set of considered species, the problem is to infer the ancestral syntenies at the internal nodes of the tree in a way optimizing certain mathematical criteria according to the chosen evolutionary model. Those criteria are usually related to minimizingthe number or cost of evolutionary events leading to the extant syntenies, although maximum likelihood criteria have also been considered. Given a node-labeled tree \(S\), where labels are syntenies, and given two adjacent nodes \(u\) and \(v\) in \(S\) where \(u\) is the parent of \(v\), \(u\) is labeled by \(X_{u}\) and \(v\) is labeled by \(X_{v}\), the length of the branch \((u,v)\) of \(S\) is the minimum cost of an evolutionary scenario transforming \(X_{u}\) to \(X_{v}\). Then the general problem can be formulated as Algorithms 1. Small Phylogeny Problem:  
**Input:** A phylogenetic tree \(S\) for a set \(\Sigma\) of species, a set \(\Gamma\) of gene families, a set \(X\) of syntenies on \(\Gamma\) labeling the leaves of \(S\) and a model of evolution;  
**Output:** A synteny labeling of the internal nodes of \(S\) minimizing the total branch length over the phylogeny. This problem has been most often considered in the context of inferring ancestral genomes, i.e., where syntenies are actually entire chromosomes or genomes. For most formulations in terms of different kinds of genomes (circular, multichromosomal, single or multiple gene copies, signed or unsigned genes) and different cost or distance metrics, even the simplest restriction in terms of the median of three genomes (an unrooted three leaf phylogeny) has been shown NP-hard [48]. Based on the breakpoint graph of two permutations [49], and considering three genomes at a time, the MGR [50] algorithm infers the median by iteratively performing \"good\" reversals, i.e., reversals diminishing the distance between the three considered genomes. The MGRA [51] algorithm uses a generalization of the breakpoint graph, called multi-colors graph, to more than two permutations, and performs 2-breaks (corresponding to the standard reversals, translocations, fissions, and fusions) \"consistent\" with the given species tree. On the other hand, the steinerization method is probably the most popular heuristic for the small phylogeny problem. First assigning an initial synteny labeling to each internal node of the phylogeny, the solution is then refined iteratively by decomposing the phylogeny into a set of overlapping median configurations, updating the median at each step only if it diminishes the sum of the lengths of the branches incident to the median, and iterating until eventually converging to a minimum. The quality of the solutions largely depends on the initialization of the ancestral gene orders. Various initialization strategies have been considered, with the purpose of avoiding local minima. In particular, based on a divide-and-conquer heuristic for finding a median of three permutations minimizing the inversion distance, GASTS [52] uses an accurate initialization step, allowing for an efficient algorithm running several orders of magnitude faster than existing approaches. Another approach, the Pathegroup approach [53], is based on storing partially completed breakpoint graphs on each node of the phylogeny and greedily completing them, following a priority list, in a bottom-up traversal of the species tree. The partial graphs eventually accumulate enough edges in their pathgroups so that cycles can be formed and so that fragments of the ancestral genome can be reconstructed.