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 language | English |
|---|---|
| Pages (from-to) | 25-31 |
| Journal | Congressus Numerantium |
| Volume | 191 |
| Publication status | Published - 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