The smoothed complexity of edit distance
The smoothed complexity of edit distance
复制标题
编辑距离的平滑复杂度
DOI：
10.1145/2344422.2344434
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
Robert Krauthgamer
中科院分区：
文献类型：
--
作者：
Alexandr Andoni;Robert Krauthgamer
我们通过提出两个输入字符串之间的半随机距离模型来启动对序列对齐的平滑复杂性的研究，如下所示：首先，广告选择两个长度D的二进制字符串D和最长的公共序列A和其中最长的公共序列a然后，每个字符都以P的概率为单独使用，只是A以完全相同的方式在两个字符串内部扰动。
我们设计了两种有效的算法，这些算法将平滑实例的编辑距离达到恒定因子近似。假设编辑距离不是太小，并且运行时的保证明显优于最差的案例输入的界限。
我们的技术贡献是双重的。 [2002]。公制）因此，我们能够建立为ULAM公制开发的算法，其更好的算法通常不会延续到一般的编辑距离。
We initiate the study of the smoothed complexity of sequence alignment, by proposing a semi-random model of edit distance between two input strings, generated as follows: First, an adversary chooses two binary strings of length d and a longest common subsequence A of them. Then, every character is perturbed independently with probability p, except that A is perturbed in exactly the same way inside the two strings.
We design two efficient algorithms that compute the edit distance on smoothed instances up to a constant factor approximation. The first algorithm runs in near-linear time, namely d{1+ε} for any fixed ε > 0. The second one runs in time sublinear in d, assuming the edit distance is not too small. These approximation and runtime guarantees are significantly better than the bounds that were known for worst-case inputs.
Our technical contribution is twofold. First, we rely on finding matches between substrings in the two strings, where two substrings are considered a match if their edit distance is relatively small, a prevailing technique in commonly used heuristics, such as PatternHunter of Ma et al. [2002]. Second, we effectively reduce the smoothed edit distance to a simpler variant of (worst-case) edit distance, namely, edit distance on permutations (a.k.a. Ulam's metric). We are thus able to build on algorithms developed for the Ulam metric, whose much better algorithmic guarantees usually do not carry over to general edit distance.