March 7, 2007

Title: Sorting by Transpositions

Abstract:

An important problem in genome rearrangements is sorting permutations by

transpositions. Its complexity is still open, and two rather complicated

1.5-approximation algorithms for sorting linear permutations are known

(Bafna and Pevzner, Christie). In this talk, we prove that the problem
of

sorting circular permutations by transpositions is equivalent to the
problem

of sorting linear permutations by transpositions. Hence, all algorithms
for

sorting linear permutations by transpositions can be used to sort
circular

permutations. Then, we derive our main result: A new 1.5-approximation

algorithm, which is considerably simpler than the previous ones, and

achieves running time which is equal to the best known. The analysis of
the

algorithm is significantly less involved.

Joint work with Ron Shamir

If time permits we will discuss briefly two subsequent studies:

"A 1.375-approximation algorithm for sorting
by transpositions" (with Isaac Elias),

and "Matrix Tightness: A
Linear-Algebraic Framework for Sorting by Transpositions" (with Elad
Verbin).

Benny Pinkas