Efficient bounds for oriented chromosome inversion distance

John Kececioglu, David Sankoff

Research output: Chapter in Book/Report/Conference proceedingConference contribution

71 Scopus citations


We study the problem of comparing two circular chromosomes that have evolved by chromosome inversion, assuming that the order of corresponding genes is known, as well as their orientation. Determining the minimum number of inversions is equivalent to finding the minimum of reversals to sort a signed circular permutation, where a reversal takes an arbitrary substring of elements and reverses their order, as well as flipping their sign. We show that tight bounds on the minimum number of reversals can be found by simple and efficient algorithms.

Original languageEnglish (US)
Title of host publicationCombinatorial Pattern Matching - 5th Annual Symposium, CPM 1994, Proceedings
EditorsMaxime Crochemore, Dan Gusfield
Number of pages19
ISBN (Print)9783540580942
StatePublished - 1994
Event5th Annual Symposium on Combinatorial Pattern Matching, CPM 1994 - Asilomar, United States
Duration: Jun 5 1994Jun 8 1994

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume807 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other5th Annual Symposium on Combinatorial Pattern Matching, CPM 1994
Country/TerritoryUnited States


  • Chromosome inversion
  • Genome rearrangements
  • Reversal distance
  • Sorting by signed reversals

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Efficient bounds for oriented chromosome inversion distance'. Together they form a unique fingerprint.

Cite this