2007 | OriginalPaper | Chapter
Reversal Distance for Strings with Duplicates: Linear Time Approximation Using Hitting Set
Authors : Petr Kolman, Tomasz Waleń
Published in: Approximation and Online Algorithms
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
In the last decade there has been an ongoing interest in string comparison problems; to a large extend the interest was stimulated by genome rearrangement problems in computational biology but related problems appear in many other areas of computer science. Particular attention has been given to the problem of
sorting by reversals
(SBR)
: given two strings,
A
and
B
, find the minimum number of reversals that transform the string
A
into the string
B
(a
reversalρ
(
i
,
j
),
i
<
j
, transforms a string
A
=
a
1
...
a
n
into a string
A
′=
a
1
...
a
i
− 1
a
j
a
j
− 1
...
a
i
a
j
+ 1
...
a
n
).
Primarily the problem has been studied for strings in which every symbol appears exactly once (that is, for permutations) and only recently attention has been given to the general case where duplicates of the symbols are allowed. In this paper we consider the problem
k
-
SBR
, a version of
SBR
in which each symbol is allowed to appear up to
k
times in each string, for some
k
≥1. The main result of the paper is a Θ(
k
)-approximation algorithm for
k
-
SBR
running in time
O
(
n
); compared to the previously known algorithm for
k
-
SBR
, this is an improvement by a factor of Θ(
k
) in the approximation ratio, and by a factor of Θ(
k
) in the running time. Crucial ingredients of our algorithm are the suffix tree data structure and a linear time algorithm for a special case of a disjoint set union problem.