CREx2 Overview


CREx2 is an exact algorithm that calculates 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. Further, CREx2 considers only rearrangement operations that preserve common intervals, i.e., groups of genes that form an interval in both given gene orders. CREx2 has a (worst case) exponential runtime, but a linear runtime for problem instances where the common intervals are organized in a linear structure.

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

Download CREx2 from here.


Publication:

Tom Hartmann, Matthias Bernt, Martin Middendorf
An Exact Algorithm for Sorting by Weighted Preserving Genome Rearrangements
submitted for publication