Tel-Aviv University - Computer Science Colloquium

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^{3/2}\sqrt{\log{n}})$

time for $n$ genes.

Joint work with Roded Sharan.