Flanked Transposition Distance for Two Strings

Transposition is a well-known genome rearrangement event that switches two consecutive sub-strings on a string. Since a transposition makes changes to a string, the genome here is just a string. The problem of transforming one string into the other by a sequence of transposition operations has attracted a lot of attention. However, it has been reported that genome rearrangement events are often associated with repeated sub-strings. In particular, a transposition operation is most likely associated with three identical repeated sub-strings. A transposition operation on two consecutive sub-strings $x$ and $y$ switches the two sub-strings and transforms the whole string $zxyw$ into the other string $zyxw$, where $z$ and $w$ represents the two sub-strings on the left and right of $xy$, respectively. When repeated sub-strings are considered, the two consecutive sub-strings $x$ and $y$ are flanked with three identical repeated sub-strings $R$ and the flanked transposition transforms the whole string $zRxRyRw$ into $zRyRxRw$. For a flanked transposition operation, the neighbors of $x$ and $y$ remain the same before and after the transposition. In this paper, we investigate the problem of transforming one string into the other by a number of flanked transpositions. First, we present a necessary and sufficient condition to determine if a string can be transformed into the other by a sequence of flanked transpositions. We then design a decision algorithm with running time $\mathcal {O}(n)$ to test if such a condition holds. We also show that transforming one string into the other by using minimum number of flanked transpositions is NP-hard. A string $\pi$ of $n$ letters is simple if the $n-1$ consecutive pairs of letters are distinct. We present an $\mathcal {O}(n^{2})$ approximation algorithm with ratio 2 for the optimization version of the special case, where both input strings are simple.