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:

  1. Obtain a Free Academic Gurobi License (http://www.gurobi.com/academia/for-universities)
  2. Download and install Gurobi Optimizer (e.g., http://www.gurobi.com/downloads/download-center)
  3. Download CREx2
  4. Extract crex2.tar.gz (tar -zxvf crex2.tar.gz)
  5. 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:

  1. ./crex2 -f example.fas or
  2. ./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

[enable JavaScript]
.

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