Catalog Home Page

Covering a circular string with substrings of fixed length

Duval, A.M. and Smyth, W.F. (1996) Covering a circular string with substrings of fixed length. International Journal of Foundations of Computer Science, 7 (1). pp. 87-93.

Link to Published Version: http://dx.doi.org/10.1142/S0129054196000075
*Subscription may be required

Abstract

A nonempty circular string C(x) of length n is said to be covered by a set Uk of strings each of fixed length k≤n iff every position in C(x) lies within an occurrence of some string u∈Uk. In this paper we consider the problem of determining the minimum cardinality of a set Uk which guarantees that every circular string C(x) of length n≥k can be covered. In particular, we show how, for any positive integer m, to choose the elements of Uk so that, for sufficiently large k, uk≈σk–m, where uk=|Uk| and σ is the size of the alphabet on which the strings are defined. The problem has application to DNA sequencing by hybridization using oligonucleotide probes.

Publication Type: Journal Article
Publisher: World Scientific Publishing Co.
Copyright: 1996 World Scientific Publishing Company
URI: http://researchrepository.murdoch.edu.au/id/eprint/27534
Item Control Page Item Control Page