%0 Journal Article
%T Listing all sorting reversals in quadratic time
%A Krister M Swenson
%A Ghada Badr
%A David Sankoff
%J Algorithms for Molecular Biology
%D 2011
%I BioMed Central
%R 10.1186/1748-7188-6-11
%X 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
%U http://www.almob.org/content/6/1/11