DIMACS TR: 2001-41
1.375-Approximation Algorithm for Sorting by Reversals
Authors: Piotr Berman, Sridhar Hannenhalli and Marek Karpinski
ABSTRACT
Analysis of genomes evolving by inversions leads to a general
combinatorial problem of {\em 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 approximationalgorithm
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.
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2001/2001-41.ps.gz
DIMACS Home Page