The Prague Stringology Conference 2003
Manolis Christodoulakis, Costas S. Iliopoulos, Kunsoo Park and Jeong Seop Sim
Approximate Seeds of Strings
| Abstract: |
| 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: |  |
 |
| PostScript |