On an Algorithm for Sorting by Strip Swaps Using Cycle Graphs

The mathematics of genome rearrangements is significantly more complex compared to mutations. However, the study of genome rearrangements is of great interest to computational biologists, comparative genomicists, and phylogenists. Genome rearrangements are modeled using a variety of primitives, including block (strip) moves, block interchanges, reversals, and transpositions. The present study is an extension of previous work on a primitive known as the strip swap, a variant of the block interchange. A 2-approximation algorithm for sorting by strip swaps using cycle graphs previously reported in the literature fails under certain circumstances, and the current study provides a solution for those instances and improves upon the previous algorithm.