**Tel-Aviv****
University**

**Sunday, April 30, 2006, 11:15-12:15**

**Room 309**

**Schreiber****
Building**

--------------------------------------------------------------------------------

**Tzvika**** Hartman**

**Bar-Ilan**** University**

Title: Approximation Algorithms for 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

Next, we consider the problem of sorting by transpositions
and

transreversals.
We provide a 1.5-approximation algorithm for the problem,

improving on a five-years-old 1.75
ratio for this problem. Our algorithm is

also faster than current approaches
and requires $O(n^

time for $n$ genes.

Joint work with Roded Sharan.