The Prague Stringology Conference 2003

Manolis Christodoulakis, Costas S. Iliopoulos, Kunsoo Park and Jeong Seop Sim

Approximate Seeds of Strings

In this paper we study approximate seeds of strings, that is, substrings of a given string x that cover (by concatenations or overlaps) a superstring of x, under a variety of distance rules (the Hamming distance, the edit distance, and the weighted edit distance). We solve the smallest distance approximate seed problem and the restricted smallest approximate seed problem in polynomial time and we prove that the general smallest approximate seed problem is NP-complete.

Download paper: Article in PostScript Article in PDF
 PostScript   PDF