Department of Computer Science
 
Chair V

 
University of Bonn -> Department of Computer Science -> Chair V
CS-Reports 2001 Copyright 2001 University of Bonn, Department of Computer Science, Abt. V
85228

July 3, 2001

1.375-Approximation Algorithm for Sorting by Reversals
Piotr Berman, Sridhar Hannenhalli and Marek Karpinski
[Download PostScript] [Download PDF]

Analysis of genomes evolving by inversions leads to a general combinatorial problem of Sorting by Reversals, MIN-SBR, the problem of sorting a permutation by a minimum number of reversals. This combinatorial problem has a long history, and a number of other motivations. It was studied in a great detail recently in computational molecular biology. Following a series of preliminary results, Hannenhalli and Pevzner developed the first exact polynomial time algorithm for the problem of sorting signed permutations by reversals, and a polynomial time algorithm for a special case of unsigned permutations. The best known approximation algorithm for MIN-SBR, due to Christie, gives a performance ratio of 1.5. In this paper, by exploiting the polynomial time algorithm for sorting signed permutations and by developing a new approximation algorithm for maximum cycle decomposition of breakpoint graphs, we improve the performance ratio for MIN-SBR to 1.375. Besides its biological and combinatorial importance, better approximation algorithms for MIN-SBR have become particularly challenging recently because this problem has been proven to NP-hard by Caprara, and MAX-SNP hard by Berman and Karpinski, excluding thus an existence of a polynomial time approximation scheme (PTAS) for that problem.

Last Change: 11/05/14 at 10:20:36
 Deutsch
University of Bonn -> Department of Computer Science -> Chair V