A linear-time algorithm for computing inversion distance between signed permutations with an experimental study

D. A. Bader, B. M.E. Moret, M. Yan

Research output: Contribution to journalArticlepeer-review

255 Scopus citations

Abstract

Hannenhalli and Pevzner gave the first polynomial-time algorithm for computing the inversion distance between two signed permutations, as part of the larger task of determining the shortest sequence of inversions needed to transform one permutation into the other. Their algorithm (restricted to distance calculation) proceeds in two stages: in the first stage, the overlap graph induced by the permutation is decomposed into connected components; then, in the second stage, certain graph structures (hurdles and others) are identified. Berman and Hannenhalli avoided the explicit computation of the overlap graph and gave an O(nα(n)) algorithm, based on a Union-Find structure, to find its connected components, where α is the inverse Ackerman function. Since for all practical purposes α(n) is a constant no larger than four, this algorithm has been the fastest practical algorithm to date. In this paper, we present a new linear-time algorithm for computing the connected components, which is more efficient than that of Berman and Hannenhalli in both theory and practice. Our algorithm uses only a stack and is very easy to implement. We give the results of computational experiments over a large range of permutation pairs produced through simulated evolution; our experiments show a speed-up by a factor of 2 to 5 in the computation of the connected components and by a factor of 1.3 to 2 in the overall distance computation.

Original languageEnglish (US)
Pages (from-to)483-491
Number of pages9
JournalJournal of Computational Biology
Volume8
Issue number5
DOIs
StatePublished - 2001
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Modeling and Simulation
  • Molecular Biology
  • Genetics
  • Computational Mathematics
  • Computational Theory and Mathematics

Keywords

  • Cycle graph
  • Inversion distance
  • Overlap forest
  • Overlap graph
  • Signed permutation
  • Sorting by reversals

Fingerprint

Dive into the research topics of 'A linear-time algorithm for computing inversion distance between signed permutations with an experimental study'. Together they form a unique fingerprint.

Cite this