Regular PapersNo Access

ALGORITHMS FOR APPROXIMATE K-COVERING OF STRINGS

Department of Mathematical Sciences, University of North Carolina, P. O. Box 26170, Greensboro, North Carolina 27402–6170, United States

Search for more papers by this author

and

F. BLANCHET-SADRI

Department of Mathematical Sciences, University of North Carolina, P.O. Box 26170, Greensboro, North Carolina 27402–6170, United States

Search for more papers by this author

https://doi.org/10.1142/S0129054105003789Cited by:1 (Source: Crossref)

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(mn²) and O(mn²) under Hamming, Levenshtein and edit distance, respectively. A World Wide Web server interface has been established at for automated use of the programs.

Keywords:

References

P. Agius, F. Blanchet-Sadri, Ajay Chriscoe and Liem Mai, "Approximate patterns in strings," Preprint (2004) (http://www.uncg.edu/mat/pattern/) . Google Scholar
A. Apostolico and A. Ehrenfeucht, Theoret. Comput. Sci. 119, 247 (1993). Web of Science, Google Scholar
A. Apostolico, M. Farach and C. S. Iliopoulos, Inform. Process. Lett. 39, 17 (1991). Web of Science, Google Scholar
D. Breslauer, Inform. Process. Lett. 44, 345 (1992). Web of Science, Google Scholar
D. Breslauer, Inform. Process. Lett. 49, 235 (1994). Web of Science, Google Scholar
C. S. Iliopoulos and K. Park, J. Korea Inform. Sci. Soc. 21, 1400 (1994). Web of Science, Google Scholar
C. S. Iliopoulos and W. F. Smyth, On-line algorithms for k-covering, Proc. 9th Australasian Workshop on Combinatorial Algorithms (1998) pp. 97–106. Google Scholar
G. M. Landau, J. P. Schmidt and D. Sokol, J. Comp. Biol. 8, 1 (2001). Web of Science, Google Scholar
Y. Li and W. F. Smyth, Algorithmica 32, 95 (2002). Web of Science, Google Scholar
D. Moore and W. F. Smyth, Inform. Process. Lett. 50, 239 (1994). Web of Science, Google Scholar
D. Moore and W. F. Smyth, Inform. Process. Lett. 54, 101 (1995). Web of Science, Google Scholar
S. B. Needleman and C. D. Wunsch, J. Mol. Biol. 48, 443 (1970). Web of Science, Google Scholar
J. P. Schmidt, SIAM J. Comput. 27, 972 (1998). Web of Science, Google Scholar
J. Setubal and J. Meidanis , Introduction to Computational Molecular Biology ( PWS Publishing Company , Boston , 1997 ) . Google Scholar
J. S. Simet al., Theoret. Comput. Sci. 262, 557 (2001). Web of Science, Google Scholar