Interchanging graphs associated with sorting by transpositions

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

Research output: Contribution to journalArticles

Abstract

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
Volume191
Publication statusPublished - 2008

Citation

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

Keywords

  • 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.