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.

Download SPiTDRL from here.


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