Algorithms for Approximate K-Covering of Strings

UNCG Author/Contributor (non-UNCG co-authors, if there are any, appear on document)
Francine Blanchet-Sadri, Professor (Creator)
Lili Lily Zhang, Applications Programmer I (Creator)
The University of North Carolina at Greensboro (UNCG )
Web Site:

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 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. A World Wide Web server interface has been established at for automated use of the programs.

Additional Information

International Journal of Foundations of Computer Science, Vol. 16, No. 6, 2005, pp 1231-1251.
Language: English
Date: 2005
Strings, k-Covers, Approximate k-covers, Distance measures, String algorithms, Dynamic programming.