## 3 The papers
### Problem area # 5 : evolution  
Genome rearrangements.The most common type of genomic rearrangement event is by far the inversion, also called _reversal_. A _reversal_\(\rho_{ij}\), with \(1\leq i<j\leq n\), is a permutation defined as  
\[\rho_{ij}=(1\;\ldots\;i-1\;\;\;\boxed{j-1\;\ldots\;i+1\;i}\;\;\;j+1\;\ldots\; n).\]  
If we represent a genome of \(n\) genes as a permutation \(\pi=(\pi_{1},\ldots,\pi_{n})\) of the numbers \(\{1,\ldots,n\}\), by applying (multiplying) \(\rho_{ij}\) to \(\pi\), one obtains \((\pi_{1}\;\ldots\;\pi_{i-1},\;\pi_{j}\;\pi_{j-1}\;\ldots\;\pi_{i},\;\pi_{j+1} \;\ldots\;\pi_{n})\), i.e., the order of the elements \(\pi_{i},\ldots,\pi_{j}\) has been reversed. Given two genomes \(\pi\) and \(\sigma\) over the same \(n\) genes, their _reversal distance_ is the smallest number \(d\) such that there exits reversals \(\rho^{1},\rho^{2},\ldots,\rho^{d}\) with  
\[\sigma=\rho^{1}\cdot\rho^{2}\cdots\rho^{d}\cdot\pi\]  
Without loss of generality, we can always assume that \(\sigma=(1\ 2\ \cdots\ n)\), so that the problem becomes that of finding the smallest number of reversals that sort a given permutation \(\pi\). This problem is also known as _sorting by reversals_ (SBR). [75]: [PERSON] and [PERSON] and [PERSON] (1999) [RED,ILP]  
describe a column-generation approach for SBR. The approach is based on the solution of a graph problem strictly related to SBR. Each permutation \(\pi\) defines a _breakpoint graph_\(G(\pi)\), in which the edges are colored red and blue, and the number of red and blue edges incident on any node is the same. The edges of \(G(\pi)\) can be decomposed into a set of cycles alternating red and blue edges (called _alternating cycles_). It can be shown that, to find the optimal solution of SBR, one has to decompose the edges of \(G(\pi)\) into the maximum number of alternating cycles. The paper formulates the cycle decomposition problem as an integer programming model with a variable for each alternating cycle. The variables are priced-in via the solution of minimum weighted perfect matching problems. The algorithm is capable of sorting permutations of up to \(n=100\) elements in a matter of seconds. [76]: [PERSON] and [PERSON] and [PERSON] (2001) [RED,ILP]  
show that, by relaxing the set of variables to the set of pseudo-alternating cycles (i.e., alternating cycles that can re-use some of the edges), the pricing problem becomes matching on _bipartite_ graphs. This is much faster to solve than matching on general graphs. The resulting algorithm is capable of sorting permutations of up to \(n=300\) elements in a matter of seconds. Given permutations \(\pi^{1},\pi^{2},\ldots,\pi^{q}\), their _reversal median_ is a permutation \(\sigma\) such that the sum of the reversal distance from \(\sigma\) to each of the \(\pi^{i}\) is minimum. [77]: [PERSON] (2003) [RED]  
shows how to reduce the reversal median problem to finding a perfect matching in a graph that forms the maximum number of cycles jointly with \(q\) given perfect matchings. The paper proposes effective algorithms for its exact and heuristic solution, validated by the solution of a few hundred instances associated with real-life genomes. Phylogeny reconstruction.Given a set of genomes, one basic problem is that of constructing a phylogenetic tree over the genomes which describes their evolution. The internal nodes of the tree represent ancestral genomes, while the input genomes label the tree leaves. The tree edges are weighted, where the length of each edge is the evolutionary distance (e.g., reversal distance) between the genomes corresponding to the endpoints of the edge. The objective is that of finding the tree of smallest total length. As a by-product, for each pair of input genomes, the total length of the path between them in the tree should approximate their evolutionary distance. * [78] [PERSON] and [PERSON] (2005) [OTH] describe a linear program whose solution yields a lower bound to the phylogeny reconstruction problem.