Cabbage Can’t Always Be Transformed into Turnip: Decision Algorithms for Sorting by Symmetric Reversals

Sorting a permutation by reversals is a famous problem in genome rearrangements, and has been well studied over the past thirty years. But the involvement of repeated segments is sometimes inevitable during genome evolution, especially in reversal events. Since 1997, quite some biological evidence were found that in many genomes the reversed regions are usually flanked by a pair of inverted repeats. For example, a reversal will transform \(+a +x -y -z -a\) into \(+a +z +y -x -a\) , where \(+a\) and \(-a\) form a pair of inverted repeats. This type of reversals are called symmetric reversals, which, unfortunately, were largely ignored in algorithm design. While sorting genomes with a mixture of reversals and symmetric reversals sees more practical in many scenarios, it is certainly a much harder problem (which is out the scope of this paper). In this paper, we investigate the decision problem of sorting by symmetric reversals (SSR(A,B)), which requires a series of symmetric reversals to transform one chromosome A into the another chromosome B. Given a pair of chromosomes A and B with n repeats, we present an \(O(n^2)\) time algorithm to solve the decision problem SSR(A,B). This result is achieved by converting the problem to the circle graph, which has been augmented significantly from the traditional circle graph and a list of combinatorial properties must be proved to successfully answer the decision question.