TY - CHAP
T1 - 1.375-Approximation Algorithm for Sorting by Reversals
T2 - Algorithms — ESA 2002Algorithms — ESA 2002
Y1 - 2002
A1 - Berman,Piotr
A1 - Hannenhalli, Sridhar
A1 - Karpinski,Marek
ED - Möhring,Rolf
ED - Raman,Rajeev
AB - 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. 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 design a new 1.375-algorithm for the MIN-SBR problem.
JA - Algorithms — ESA 2002Algorithms — ESA 2002
T3 - Lecture Notes in Computer Science
PB - Springer Berlin / Heidelberg
VL - 2461
SN - 978-3-540-44180-9
UR - http://dx.doi.org/10.1007/3-540-45749-6_21
ER -