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: