Skip to Main content Skip to Navigation
Journal articles

New bounds and tractable instances for the transposition distance

Abstract : The problem of sorting by transpositions asks for a sequence of adjacent interval exchanges that sorts a permutation and is of the shortest possible length. The distance of the permutation is defined as the length of such a sequence. Despite the apparently intuitive nature of this problem, introduced in 1995 by Bafna and Pevzner, the complexity of both finding an optimal sequence and computing the distance remains open today. In this paper, we establish connections between two different graph representations of permutations, which allows us to compute the distance of a few nontrivial classes of permutations in linear time and space, bypassing the use of any graph structure. By showing that every permutation can be obtained from one of these classes, we prove a new tight upper bound on the transposition distance. Finally, we give improved bounds on some other families of permutations and prove formulas for computing the exact distance of other classes of permutations, again in polynomial time.
Complete list of metadatas

Cited literature [16 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-00728947
Contributor : Anthony Labarre <>
Submitted on : Friday, September 7, 2012 - 9:45:00 AM
Last modification on : Thursday, June 4, 2020 - 10:24:03 AM
Long-term archiving on: : Saturday, December 8, 2012 - 3:40:07 AM

Files

labarre-new.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Anthony Labarre. New bounds and tractable instances for the transposition distance. IEEE/ACM Transactions on Computational Biology and Bioinformatics, Institute of Electrical and Electronics Engineers, 2006, 3 (4), pp.380-394. ⟨10.1109/TCBB.2006.56⟩. ⟨hal-00728947⟩

Share

Metrics

Record views

153

Files downloads

355