Journal article
Covering a circular string with substrings of fixed length
International Journal of Foundations of Computer Science, Vol.7(1), pp.87-93
1996
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.
Details
- Title
- Covering a circular string with substrings of fixed length
- Authors/Creators
- A.M. Duval (Author/Creator)W.F. Smyth (Author/Creator)
- Publication Details
- International Journal of Foundations of Computer Science, Vol.7(1), pp.87-93
- Publisher
- World Scientific Publishing Co.
- Identifiers
- 991005543127707891
- Copyright
- 1996 World Scientific Publishing Company
- Murdoch Affiliation
- Murdoch University
- Language
- English
- Resource Type
- Journal article
Metrics
24 Record Views