Listing all sorting reversals in quadratic time

We describe an average-case O(n2) algorithm to list all reversals on a signed permutation π that, when applied to π, produce a permutation that is closer to the identity. This algorithm is optimal in the sense that, the time it takes to write the list is Ω(n2) in the worst case.

• Publication year

  2010

• Venue

  Algorithms for Molecular Biology

• Publication date

  2010-09-06

• Fields of study

  Biology, Mathematics, Computer Science, Medicine

• Identifiers
  DOI 10.1186/1748-7188-6-11PMID 21504604PMCID 3110122
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar, PubMed

• No claims are published for this paper.

• No concepts are published for this paper.

• An improved algorithm to enumerate all traces that sort a signed permutation by reversals

  2010cited by this paper
• Web API for biology with a workflow navigation system

  2009cited by this paper
• Sorting Signed Permutations by Inversions in O(nlogn) Time

  2009cited by this paper
• On the expectation and variance of the reversal distance.

  2009cited by this paper
• baobabLUNA: the solution space of sorting by reversals

  2009cited by this paper
• Hurdles Hardly Have to Be Heeded

  2008cited by this paper
• The Solution Space of Sorting by Reversals

  2007cited by this paper
• Advances on sorting by reversals

  2007cited by this paper
• The Distribution of Genomic Distance between Random Genomes

  2006cited by this paper
• A very elementary presentation of the Hannenhalli-Pevzner theory

  2005cited by this paper
• Sorting by Reversals in Subquadratic Time

  2004cited by this paper
• The Distribution of Inversion Lengths in Bacteria

  2004cited by this paper
• Detection and validation of single gene inversions

  2003cited by this paper
• Efficient Data Structures and a New Randomized Approach for Sorting Signed Permutations by Reversals

  2003cited by this paper
• An algorithm to find all sorting reversals

  2002influential reference
• Exploring the Set of All Minimal Sequences of Reversals - An Application to Test the Replication-Directed Reversal Hypothesis

  2002influential reference
• The strong ion gap does not have prognostic value in critically ill patients in a mixed medical/surgical adult ICU

  2002cited by this paper
• An algorithm to enumerate all sorting reversals

  2002cited by this paper
• Common intervals and sorting by reversals: a marriage of necessity

  2002influential reference
• A Linear-Time Algorithm for Computing Inversion Distance between Signed Permutations with an Experimental Study

  2001cited by this paper
• On the Tightness of the Alternating-Cycle Lower Bound for Sorting by Reversals

  1999cited by this paper
• A Faster and Simpler Algorithm for Sorting Signed Permutations by Reversals

  1999cited by this paper
• Faster and simpler algorithm for sorting signed permutations by reversals

  1997cited by this paper
• Transforming men into mice (polynomial algorithm for genomic distance problem)

  1995cited by this paper
• Transforming cabbage into turnip: polynomial algorithm for sorting signed permutations by reversals

  1995influential reference
• Mechanisms of dietary modification of aflatoxin B1 carcinogenesis.

  1982cited by this paper

• A New Efficient Algorithm for the All Sorting Reversals Problem with No Bad Components

  2016influential citation
• Exploring the Solution Space of Sorting by Reversals: A New Approach

  2013cites this paper
• Sampling solution traces for the problem of sorting permutations by signed reversals

  2012cites this paper
• Parallel Algorithm to Enumerate Sorting Reversals for Signed Permutation

  2011cites this paper
• Listing All Parsimonious Reversal Sequences: New Algorithms and Perspectives

  2010influential citation
• Sampling Solution Traces for the Problem of Sorting Permutations by Signed Reversals

  year unknowncites this paper