New bounds and tractable instances for the transposition distance

Anthony Labarre (1)

1 ULB - Université libre de Bruxelles

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.

Domaines: Bio-informatique [q-bio.QM]; Bio-Informatique, Biologie Systémique [q-bio.QM]; Algorithme et structure de données [cs.DS]

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