Murdoch University Research Repository

Welcome to the Murdoch University Research Repository

The Murdoch University Research Repository is an open access digital collection of research
created by Murdoch University staff, researchers and postgraduate students.

Learn more

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:
*Subscription may be required


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.

Item Type: Journal Article
Publisher: World Scientific Publishing Co.
Copyright: 1996 World Scientific Publishing Company
Item Control Page Item Control Page