Covering Sequences for ℓ-Tuples

de Bruijn sequences of order ℓ, i.e., sequences that contain each ℓ-tuple as a window exactly once, have found many diverse applications in information theory and most recently in DNA storage. This family of binary sequences has asymptotic rate of 1/2. To overcome this low rate, we study ℓ-tuples covering sequences, which impose that each ℓ-tuple appears at least once as a window in the sequence. The cardinality of this family of sequences is analyzed while assuming that ℓ is a function of the sequence length n. Lower and upper bounds on the asymptotic rate of this family are given. Moreover, we study an upper bound for ℓ such that the redundancy of the set of ℓ-tuples covering sequences is at most a single symbol. We present an efficient encoding and decoding schemes for ℓ-tuples covering sequences that meet this bound.