Sorting by Multi-cut Rearrangements

Let S be a string built on some alphabet \(\varSigma \). A multi-cut rearrangement of S is a string \(S'\) obtained from S by an operation called k-cut rearrangement, that consists in (1) cutting S at a given number k of places in S, making S the concatenated string \(X_1\cdot X_2\cdot X_3\ldots X_k\cdot X_{k+1}\), where \(X_1\) and \(X_{k+1}\) are possibly empty, and (2) rearranging the \(X_i\)s so as to obtain \(S'=X_{\pi (1)}\cdot X_{\pi (2)}\cdot X_{\pi (3)}\ldots X_{\pi (k+1)}\), \(\pi \) being a permutation on \(1,2\ldots k+1\) satisfying \(\pi (1)=1\) and \(\pi (k+1)=k+1\). Given two strings S and T built on the same multiset of characters from \(\varSigma \), the Sorting by Multi-cut Rearrangements (SMCR) problem asks whether a given number \(\ell \) of \(k\)-cut rearrangements suffices to transform S into T. The SMCR problem generalizes and thus encompasses several classical genomic rearrangements problems, such as Sorting by Transpositions and Sorting by Block Interchanges. It may also model chromoanagenesis, a recently discovered phenomenon consisting in massive simultaneous rearrangements. In this paper, we study the SMCR problem from an algorithmic complexity viewpoint, and provide, depending on the respective values of k and \(\ell \), polynomial-time algorithms as well as NP-hardness, FPT-algorithms, W[1]-hardness and approximation results, either in the general case or when S and T are permutations.