printable pdf
比利时vs摩洛哥足彩 ,
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

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