# CREx2

## Overview

**CREx2** is an dynamic programming algorithm that aims to compute a weight-minimum sequence of rearrangements for arbitrary mitochondrial gene orders and the following types of weighted rearrangement operations: inversions, transpositions, inverse transpositions, and tandem duplication random loss. **CREx2** considers only rearrangement operations that preserve common intervals, i.e., groups of genes that form an interval in both given gene orders. If the common intervals of a problem instance are organized in a linear structure, then **CREx2** has a linear runtime. Otherwise, there are two modes for **CREx2**: The first mode **CREx2-ILP** has been proposed in [Hartmann et al. 2018]. It computes an exact weight-minimum rearrangement scenario within an exponential runtime (in worst case). The second mode **CREx2-APP** has been proposed in [Hartmann 2019] it computes approximated solutions efficiently. Both versions of **CREx2** as well as CREx proposed in [Bernt et al. 2007] are implemented in the current version of **CREx2**.

Algorithm **CREx2** is implemented in C++ and it relies on the **Gurobi** Optimizer 8.1.

## CREx2 Downloads

The complete algorithm CREx2 including CREx, CREx2-ILP, and CREx2-APP can be downloaded here.

#### Installation:

- Obtain a Free Academic
**Gurobi**License (http://www.gurobi.com/academia/for-universities) - Download and install
**Gurobi**Optimizer (e.g., http://www.gurobi.com/downloads/download-center) - Download
**CREx2** - Extract crex2.tar.gz (
`tar -zxvf crex2.tar.gz`

) - If no Linux distribution is used, compile the
**CREx2**source code using the given Makefile. Otherwise, no further installation is needed.

A version of **CREX2 without any dependency on the Gurobi Optimizer** (thus only the approximation algorithms CREx and CREx2-APP are contained) can be downloaded here. For the installation of this algorithm only steps 3-5 are required.

**CREx2** is executed from the command line using:

```
./crex2 -f <input file> [options]
```

Use `-h`

for more information.

For testing whether or not **CREx2** is installed correctly enter:

`./crex2 -f example.fas`

or`./crex2 -f example.fas -d`

.

The first command produces two scenarios of rearrangements that transform the given gene orders gene_order_1 and gene_order_2 (see example.fas) into each other. Thereby, equally weighted rearrangements are used. The second command produces a table that gives only the lengths of these scenarios.

Feel free to send bug reports or any other kind of impressions or suggestions on **CREx2** to

## Publications

*M. Bernt, D. Merkle, K. Ramsch, G. Fritzsch, M. Perserke, D. Bernhard, M. Schlegel, P. Stadler, M. Middendorf*

**CREx: Inferring Genomic Rearrangements Based on Common Intervals**

Bioinformatics, 23(21): 2957-2958, 2007

*Tom Hartmann, Matthias Bernt, Martin Middendorf*

**An Exact Algorithm for Sorting by Weighted Preserving Genome Rearrangements**

IEEE/ACM Trans Comput Biol Bioinform. 2019 Jan-Feb;16(1):52-62.

*Tom Hartmann*

**Models and Algorithms for Sorting Permutations with Tandem Duplication and Random Loss**

PhD Thesis

University Leipzig 2018