Printable PDF
Department of Mathematics,
University of California San Diego

****************************

Math 269 - Combinatorics

Glenn Tesler

UCSD

Multi de Bruijn Sequences

Abstract:

We generalize the notion of a de Bruijn sequence to a ``multi de Bruijn sequence'': a cyclic or linear sequence that contains every $k$-mer over an alphabet of size $q$ exactly $m$ times. For example, over the binary alphabet $\{0,1\}$, the cyclic sequence $(00010111)$ and the linear sequence $000101110$ each contain two instances of each $2$-mer $00,01,10,11$. We derive formulas for the number of such sequences. The formulas and derivation generalize classical de Bruijn sequences (the case $m=1$). We also determine the number of multisets of aperiodic cyclic sequences containing every $k$-mer exactly $m$ times; for example, the pair of cyclic sequences $(00011)(011)$ contains two instances of each $2$-mer listed above. This uses an extension of the Burrows-Wheeler Transform due to Mantaci et al., and generalizes a result by Higgins for the case $m=1$.

Organizer: Jeff Remmel

April 11, 2017

4:00 PM

AP&M 7321

****************************