Listing all sorting reversals in quadratic time

In 1995 Hannenhalli and Pevzner [1] presented an algorithm to transform one genome into another in a minimum number of biologically plausible moves. They modeled a genome as a signed permutation and the move that they considered was the reversal: the order of a substring of the permutation is reversed, and the sign of each element in the substring is flipped. Since then many refinements and speed improvements have been developed [2-8].In 2002 Siepel and Ajana et al. [9,10] showed how to list every parsimonious scenario of reversals, each scenario being a proposed candidate for the true evolutionary history. Fundamental to their algorithms are O(n3) techniques for finding all sorting reversals; the reversals that at each step produce a permutation that is closer to the target permutation than the last. Ajana et al. [9] used these results to support the replication-directed reversal hypothesis. Lefebvre et al. [11] and Sankoff et al. [12] used similar methodology to gain insight into the distribution of reversal lengths between genomes. Algorithms that attempt to more succinctly represent all shortest-length scenarios [13,14] have also been developed.In this paper we show how to list all sorting reversals in O(n2) time on average. This algorithm is optimal in the sense that there are Ω(n2) safe cycle-splitting reversals in the worst case. We later give a family of permutations that have Ω(n2) unsafe reversals.We implemented our algorithm in Java, and show experimentally that our algorithm is significantly faster than that of Siepel. This will afford a marked speedup of the aforementioned methods [9-14], since listing all sorting reversals is the kernel of repeated computation in each of them, especially when applied to permutations of sizes 3 × 103 to 3 × 105 (the size of bacterial or mammalian genomes).After giving background material in Section 2 we introduce ominous substrings in Section 3. Section 4 describes how to detect the set of all ominous substrings of a pe