Lili
Zhang
and
F. BlanchetSadri
Abstract
Computing approximate patterns in strings or sequences has important applications in DNA sequence analysis, data compression, musical text analysis, and so on. In this paper, we introduce approximate kcovers and study them under various commonly used distance measures. We propose the following problem: "Given a string x of length n, a set U of m strings of length k, and a distance measure, compute the minimum number t such that U is a set of approximate kcovers for x with distance t". To solve this problem we present three algorithms with time complexity O(km(nk)), O(mn^{2}) and O(mn^{2}) under hamming, levenshtein and edit distance, respectively.
Keywords: Strings, kcovers, approximate kcovers, distance measures, string algorithms, dynamic programming.
