Reversal distance for strings with duplicates: linear time approximation using hitting set
Summary: 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 \(\rho(i,j), i<j\), transforms a string \(A=a_1\dots a_n\) into a string \(A'=a_1\dots a_{i-1} a_{j} a_{j-1} \dots a_{i} a_{j+1} \dots a_n\)). Closely related is the Minimum Common String Partition Problem (MCSP): given two strings, \(A\) and \(B\), find a minimum size partition of \(A\) into substrings \(P_1,\dots,P_l\) (i.e., \(A=P_1\dots P_l\)) and a partition of \(B\) into substrings \(Q_1,\dots,Q_l\) such that \((Q_1,\dots,Q_l)\) is a permutation of \((P_1,\dots,P_l)\). Primarily the SBR 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\geq 1\). The main result of the paper is a \(\Theta(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 \(\Theta(k)\) in the approximation ratio, and by a factor of \(\Theta(k)\) in the running time. We approach the \(k\)-SBR by finding an approximation for the \(k\)-MCSP first and then turning it into a solution for \(k\)-SBR. 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.
- Reversal Distance for Strings with Duplicates: Linear Time Approximation Using Hitting Set
- Mathematical Foundations of Computer Science 2005
- Approximating reversal distance for strings with bounded number of duplicates
- Reversal distances for strings with few blocks or small alphabets
- A new distance metric on strings computable in linear time
- Efficient Algorithms for the Closest String and Distinguishing String Selection Problems
- Linear time algorithms for finding and representing all the tandem repeats in a string
- Almost linear time computation of maximal repetitions in run length encoded strings
- Space-Efficient Approximate String Matching Allowing Inversions in Fast Average Time
- scientific article; zbMATH DE number 826062
- Quick greedy computation for minimum common string partitions
- Parameterized tractability of the maximum-duo preservation string mapping problem
- Minimum common string partition revisited
- Reversal Distance for Strings with Duplicates: Linear Time Approximation Using Hitting Set
- Mathematical Foundations of Computer Science 2005
- Approximating reversal distance for strings with bounded number of duplicates
This page was built for publication: Reversal distance for strings with duplicates: linear time approximation using hitting set
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1010605)
