Approximate k-Covering Home

Algorithms for Approximate k-Covering

 Lili Zhang and F. Blanchet-Sadri


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 k-covers 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 k-covers for x with distance t". To solve this problem we present three algorithms with time complexity O(km(n-k)), O(mn2) and O(mn2) under hamming, levenshtein and edit distance, respectively.

      Keywords: Strings, k-covers, approximate k-covers, distance measures, string algorithms, dynamic programming.

Acknowledgement: This material is based upon work supported by the National Science Foundation under  grant No. CCR-0207673.

Disclaimer: Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the National Science Foundation.