Computer Science Colloquium, 2006-2007

Tzvika Hartman
March 7, 2007
Title: Sorting by Transpositions

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