Two genomes may have many genes in common, but the genes may be arranged in a different sequence or be moved between chromosomes. Such differences in gene orders are the results of rearrangement events that are common in molecular evolution. For example, in unichromosomal genomes, the most common rearrangement events are reversals, in which a contiguous interval of genes is put into the reverse order. For multichromosomal genomes, the most common rearrangement events are reversals, translocations, fissions, and fusions, which are described later.

The *pairwise genome rearrangement problem* is to find an
optimal scenario transforming one genome to another via
these rearrangement events.
We provide a C program and a web tool combining rearrangement
algorithms for unichromosomal and multichromosomal genomes,
with either signed or unsigned gene data.
In each case, it computes the minimum possible number
of rearrangement steps, and determines a possible scenario
taking this number of steps.

GRIMM implements the Hannenhalli-Pevzner algorithms for computing unichromosomal and multichromosomal genomic distances, making extensive use of code that was adapted from GRAPPA for the unichromosomal problem. GRIMM also implements the Hannenhalli-Pevzner algorithm for computing the reversal distance between two unsigned unichromosomal genomes, and Tesler's algorithm for computing the distance between two unsigned multichromosomal genomes.

5 -3 4 2 -1 |

7 -2 8 3 $ 5 9 -6 -1 12 $ 11 4 10 $ |

11 4 10 $ -3 -8 2 -7 $ 5 9 -6 -1 12 $ |

5 13 2 -9 7-4 6 8 5 1-7 9 -2 -3-4 6 8

**Reversal:**An interval within a single chromosome may be reversed in the same fashion as a reversal acts in the unichromosomal case:7 -2 8 3 $ 5 9

**-6 -1 12**$ 11 4 10 $7 -2 8 3 $ 5 9

**-12 1 6**$ 11 4 10 $**Note:**When the programs are run in unichromosomal mode, the genomes3 1 2 and -2 -1 -3

**Translocation:**Two chromosomes "A B" and "C D" may be rearranged into "A D" and "C B". (The letters A, B, C, D stand for sequences of genes.) Because flipping chromosomes does not alter a genome (only its representation is altered), "A -C" and "-B D" is another possible translocation, and is the one actually done by our algorithm. (-B means to reverse the order of the genes in sequence B and negate each one.) For example, a translocation on chromosomes 1 and 3 is7 -2 8

**3**$ 5 9 -6 -1 12 $**11 4**10 $7 -2 8

**-4 -11**$ 5 9 -6 -1 12 $**-3**10 $**Fusion:**Two chromosomes may be fused together into a single chromosome. Due to chromosome flippings, there are four distinct fusions between each pair of chromosomes. Here is one of the fusions between chromosomes 1 and 3:**7 -2 8 3 $**5 9 -6 -1 12 $**11 4 10 $****7 -2 8 3 -10 -4 -11 $**5 9 -6 -1 12 $**Fission:**A chromosome may be broken into two chromosomes between any pair of genes:7 -2 8 3 $

**5 9 -6 -1 12 $**11 4 10 $7 -2 8 3 $

**5 9 $ -6 -1 12 $**11 4 10 $

Existing data for which signs are not known may be entered into the programs without specifying the signs. The programs will find an optimal assignment of signs, if the data is not too complex, or will approximate it otherwise. For example, to turn the unsigned genome

1 2 3 4 5

1 4 3 2 5

12 3 45 1-4 -3 -25

12 3 45 1-45 1 -4-3-23-2 5

1 2 -1 3 4

1 3 -9 -7 5

These sites offer programs to sort permutations by reversals. At their roots is the Hannenhalli-Pevzner algorithm for sorting signed permutations by reversals. Successive authors improved the algorithm.

- Sridhar
Hannenhalli's previous website provided C programs to
compute optimal reversal scenarios between signed and unsigned
permutations, but those programs are no longer available. The current site contains the papers he coauthored with Pavel Pevzner, on which these algorithms are based.
The distance computation is performed in time
*O(n*.^{4}) - Itsik Mantin implemented a very nice Java applet that
illustrates the graph theory behind the reversal algorithm.
It uses improvements in the algorithm developed by Haim Kaplan, Ron Shamir and Robert E. Tarjan, which bring the time to compute distance down to
*O(n*.^{2}) - GRAPPA is
written by a multitude of authors. It reduces the distance
computation time to
*O(n)*using improvements by David A. Bader, Bernard M.E. Moret, and Mi Yan. The main purpose of GRAPPA is to construct phylogenetic trees for multiple signed unichromosomal genomes; the distance computation on which we are focused is but a mere subroutine in that context.We thank the authors of GRAPPA for making it available to us. GRIMM is based largely on their code invdist.c for the unichromosomal case. We made extensive modifications and additions to that code.

In addition to these programs, Guillaume Bourque has developed an algorithm and implementation MGR for computing phylogenetic trees for multiple genomes, unichromosomal or multichromosomal. It uses GRIMM to do its distance computations.

- Bader, D.A., Moret, B.M.E., and Yan, M. (2001)
A linear-time algorithm for computing inversion distances between signed
permutations with an experimental study,
*J. Comput. Biol.***8**(5), 483-491. Paper at journal or author. - Caprara, A. (1999) Sorting permutations by reversals and Eulerian cycle
decompositions.
*SIAM J. Discrete Math.***12**(1), 91-110 (electronic). Paper at journal or author. - Grimm, J. and Grimm, W. (1812) Puss in Boots. In
*Grimm's Fairy Tales.* - Hannenhalli, S. and Pevzner, P.A. (1995) Transforming men into mice
(polynomial algorithm for genomic distance problem).
In
*36th Annual Symposium on Foundations of Computer Science (Milwaukee, WI, 1995),*IEEE Comput. Soc. Press, Los Alamitos, CA, pp. 581-592. Paper at journal or author. - Hannenhalli, S. and Pevzner, P. (1996) To cut ... or not to cut
(applications of comparative physical maps in molecular evolution).
In
*Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Atlanta, GA, 1996),*ACM, New York, pp. 304-313. Paper at journal or author. - Hannenhalli, S. and Pevzner, P.A. (1999)
Transforming cabbage into turnip:
polynomial algorithm for sorting signed permutations by reversals.
*J. ACM***46**(1), 1-27. Paper at journal or author. - Kaplan, H., Shamir, R., and Tarjan, R.E. (1999)
A faster and simpler algorithm for sorting signed permutations by reversals.
*SIAM J. Comput.***29**(3), 880--892 (electronic). Paper at journal or author. - Pevzner, P.A. (2000)
*Computational molecular biology, An algorithmic approach,*MIT Press, Cambridge, MA, Chap. 10.

This page was created by Glenn Tesler, University of California, San Diego.