Flanked Block-Interchange Distance on Strings

Rearrangement sorting problems impact profoundly in measuring genome similarities and tracing historic scenarios of species. However, recent studies on genome rearrangement mechanisms disclosed a statistically significant evidence, repeats are situated at the ends of rearrangement relevant segments and stay unchanged before and after rearrangements.To reflect the principle behind this evidence, we propose flanked block-interchange, an operation on strings that exchanges two substrings flanked by identical left and right symbols in a string. The flanked block-interchange distance problem is formulated as finding a shortest sequence of flanked block-interchanges to transform a string into the other. We propose a sufficient and necessary condition for deciding whether two strings can be transformed into each other by flanked block-interchanges. This condition is linear time verifiable. Under this condition for two strings, we present a <inline-formula><tex-math notation="LaTeX">$\text{4}\,k$</tex-math><alternatives><mml:math><mml:mrow><mml:mtext>4</mml:mtext><mml:mspace width="0.166667em"/><mml:mi>k</mml:mi></mml:mrow></mml:math><inline-graphic xlink:href="zhu-ieq1-3351440.gif"/></alternatives></inline-formula>-approximation algorithm for the flanked block-interchange distance problem where each symbol occurs at most <inline-formula><tex-math notation="LaTeX">$k$</tex-math><alternatives><mml:math><mml:mi>k</mml:mi></mml:math><inline-graphic xlink:href="zhu-ieq2-3351440.gif"/></alternatives></inline-formula> times in a string and a polynomial algorithm for this problem where each symbol occurs at most twice in a string. We show that the problem of flanked block-interchange distance is NP-hard at last.