Publication

Abstract : Permutation models a genome. Transposition models the corresponding genomic mutation and nature is presumed to be parsimonious. Thus, transforming a given permutation π into another permutation δ with the minimum number of transpositions corresponds to the transposition based evolutionary distance between the genomes that they denote. This problem reduces to sorting γ in minimum moves, that is related to π and δ. That is, computation of td(γ). However, computing td(γ) is a known intractable combinatorial optimization problem. It has applications in comparative genomics and computer interconnection networks. Bafna and Pevzner designed a 1.5 approximation algorithm using a graph structure called the cycle graph. In a cycle graph, a 0-move does not change the number of odd cycles whereas a 2-move increases the number of odd cycles by two. They showed that two valid 2-moves are possible for every execution of a 0-move. Christie called an odd cycle in a cycle graph as super oriented if it admits a valid 2-move and at least one of the resultant cycle admits a second valid 2-move. He posed an open problem of characterizing super oriented cycles and observed that such a characterization could potentially improve the approximation ratio. We characterize super oriented cycles; thereby completing the characterization of all permutations that admit two consecutive 2-moves when at most two cycles are acted upon. In certain cases, we show that in computing td(π), our characterization leads to an improvement in the approximation ratio.