Let S be a string built on some alphabet Σ. 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 · X_2 · X_3 ... X_k · X_(k+1), where X_1 and X_(k+1) are possibly empty, and (2) rearranging the X_is so as to obtain S' = X_(π(1)) · X_(π(2)) · X_(π(3)) ... X_(π(k+1)), π being a permutation on 1,2...k + 1 satisfying π(1) = 1 and π(k + 1) = k + 1. Given two strings S and T built on the same multiset of characters from Σ, the SORTING BY MULTI-CUT REARRANGEMENTS (SMCR) problem asks whether a given number ℓ 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 ℓ, 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.
展开▼
