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.
Algorithms for Approximate K-Covering of Strings
PDF (Portable Document Format)
489 KB
Created on 2/18/2011
Views: 2461
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.