Here the approximation algorithm SB4TYPE is presented which aims to compute a shortest rearrangement scenario that transforms one given gene order into another given gene order by using only rearrangements of type inversion, transposition, inverse transposition, and tandem duplication random loss. The algorithm runs in quasilinear time with respect to the total number of genes in the given gene orders and uses at most two ancillary rearrangements.

Algorithm SB4TYPE is implemented in C++ and does not have any dependency.


Tom Hartmann
Models and Algorithms for Sorting Permutations with Tandem Duplication and Random Loss
PhD Thesis
University Leipzig 2018

SP4TYPE Downloads

SP4TYPE can be downloaded here.


  1. Download SP4TYPE
  2. Extract SP4TYPE.tar.gz (tar -zxvf SP4TYPE.tar.gz)
  3. If no Linux distribution is used, compile the SP4TYPE source code using the given Makefile. Otherwise, no further installation is needed.

SP4TYPE is executed from the command line using:

./sp4type -f <input file> [options]

Use -h for more information.

The options of SP4TYPE are:

  • --file -f , contains (multiple gene orders),
  • --distance -d consider only distance problem,
  • --help -h prints this message, where -f is a required argument.

For testing whether or not SP4TYPE is installed correctly enter:

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

[enable JavaScript]