Counting a variant of de Bruijn sequence where not every substring needs to appear

40 Views Asked by At

Are there any existing textbooks/articles/papers discussing a variant of de Bruijn sequence where not all substrings (I am specifically looking for when a fixed total number of substrings occur only once) need to occur? I want to count those. I believe the following is an equivalent and specific way to phrase the problem.

I want to count the number of unique possible length-$m$ substrings of some de Bruijn sequence on alphabet $\{ A, C, T, G\}$ with order $n$. (It should be an equivalent formulation because if not all substrings occur once, then it must be a substring of some de Bruijn sequence, the only problem that stops me from counting now is that two different de Bruijn sequences might have same substrings of length $m$, which I don't know how to deal with.)