Interchanging graphs associated with sorting by transpositions

Pinglong YOU, Wai Chee SHIU, Wai Hong CHAN, An CHANG

Research output: Contribution to journalArticlespeer-review


Sorting a permutation by transpositions is one of important methods of sequence comparison in computational molecular biology for deriving evolutionary and functional relationships between genes. In the paper, we first associate the problem of sorting by transpositions by a new kind of interchanging graph, and then give such graph a nice characterization. Based on this characterization, we also give the connectivity of the interchanging graphs. Copyright © 2008 Utilitas Mathematica Pub. Inc.
Original languageEnglish
Pages (from-to)25-31
JournalCongressus Numerantium
Publication statusPublished - 2008


You, P., Shiu, W. C., Chan, W. H., & Chang, A. (2008). Interchanging graphs associated with sorting by transpositions. Congressus Numerantium, 191, 25-31.


  • Permutation
  • Transposition
  • Interchanging graph
  • Blow up
  • Connectivity

Fingerprint Dive into the research topics of 'Interchanging graphs associated with sorting by transpositions'. Together they form a unique fingerprint.