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)
Institution
The University of North Carolina at Greensboro (UNCG )
Web Site: http://library.uncg.edu/

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 http://www.uncg.edu/mat/kcover/ for automated use of the programs.

Additional Information

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