A faster and simpler algorithm for sorting signed permutations by reversals

Haim Kaplan, Ron Shamir, Robert E. Tarjan

Research output: Contribution to journalArticle

122 Scopus citations

Abstract

We give a quadratic time algorithm for finding the minimum number of reversals needed to sort a signed permutation. Our algorithm is faster than the previous algorithm of Hannenhalli and Pevzner and its faster implementation by Berman and Hannenhalli. The algorithm is conceptually simple and does not require special data structures. Our study also considerably simplifies the combinatorial structures used by the analysis.

Original languageEnglish (US)
Pages (from-to)880-892
Number of pages13
JournalSIAM Journal on Computing
Volume29
Issue number3
DOIs
StatePublished - Jan 1 2000

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Mathematics(all)

Keywords

  • Computational molecular biology
  • Reversal distance
  • Sorting permutations

Fingerprint Dive into the research topics of 'A faster and simpler algorithm for sorting signed permutations by reversals'. Together they form a unique fingerprint.

  • Cite this