Abstract
A nonempty circular string C(x) of length n is said to be
covered by a set U_k of strings each of fixed length k <= n
iff every position in C(x) lies within an occurrence of
some string u in U_k.
In this paper we consider the problem of determining
the minimum cardinality of a set U_k 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 U_k
so that, for sufficiently large k, u_k \approx sigma^(k-m),
where u_k = |U_k|
and sigma is the size of the alphabet on which the strings are defined.
The problem has application to
DNA sequencing by hybridization using oligonucleotide probes.