# Nearly Be Bruijn sequences constructed from De Bruijn sequences

Let $w$ be a De Bruijn $01$-sequence of the type $B(2,n)$; i.e., a cyclic $01$-sequence that contains every $n$-digit $01$-sequence exactly once. Let $x$ be a $01$-sequence of length $n$. When and how can one construct from $W$ a cyclic $01$-sequence $y$ that contains every $n$-digit $01$-sequence except $x$?

Example 1. Let $w=01110100$, of type $B(2,3)$, and let $x=101$. In $w$, replace $101$ by $1001$, resulting in $y=011100100$. Since $y$ is cyclical, it contains every $3$-digit sequence except $x$. Note that $100$ occurs twice, which is not disallowed.

Example 2. For $w$ as above and $x=001$, there is no such $y$.

• @MaxAlekseyev The two trailing zeros are probably the cyclic image of the two leading zeros. – Fan Zheng Apr 24 '16 at 5:00
• I've fixed that in the question to avoid confusion. – Max Alekseyev Apr 25 '16 at 13:46

Each de Bruijn sequence corresponds to an Eulerian circuit in the de Bruijn graph $G$ (where arcs are labeled with $n$-mers and nodes are labeled with $(n-1)$-mers). The indegree and outdegree of each vertex is 2, so $G$ is Eulerian (i.e., de Bruijn sequence exists).

If $n$-mer $x$ is forbidden in a sequence, then we need to remove the arc labeled $x$ from $G$, resulting in a graph $G'$. This destroys the Eulerian property unless the arc was a self-loop (i.e., $x=0^n$ or $x=1^n$). In the latter case, the solution is trivial -- simply remove one 0 or 1 from the appearance of $x$. In the former case, we need to restore the Eulerian property by doubling some arcs in $G'$.

Let $a$ and $b$ be $(n-1)$-mers representing the prefix and suffix of $x$, respectively. Then $G'$ lacks the arc $(a,b)$, and outdegree(a) = indegree(b) = 1, while indegree(a) = outdegree(b) = 2. To restore the balance, we need to find a trail from $a$ to $b$ in $G'$ and double every arc along this trail.

First, such trail exists as soon as $a$ and $b$ each contains both zeroes and ones (otherwise there is no way out of $a$ or into $b$).

Second, in order to construct the shortest such trail, let $c$ be the largest overlap of $y$ and $z$, where $y$ and $z$ are obtained from $x$ by inverting the last and first digit, respectively (notice that $y$ starts with $a$, while $z$ ends with $b$). So, $y=y'c$ and $z=cz'$. Then the trail we look for is encoded by the string $y'cz'$. In the original de Bruijn sequence, this corresponds to replacement of instance of $x$ with $y'cz'$. The sequence length is increased by $n-|c|$.

In summary:

• if $x=0^n$ or $1^n$, remove one digit from the instance of $x$ in the sequence.

• if $x=0^{n-1}1$, $1^{n-1}0$, $10^{n-1}$, or $01^{n-1}$, there is no solution.

• Otherwise replace the instance of $x$ in the sequence with $y'cz'$.

In the example with $x=101$, we have $y=100$, $z=001$, thus $c=00$ and $y'cz'=1001$.

• Nice answer. Why use field specific $n-$mer suffix when the generic term $n-$tuple will do? – kodlu Apr 24 '16 at 3:11
• @kodlu: $n$-mer is a traditional way to refer to a substring of a fixed length $n$. Tuples are more about sequences than strings. – Max Alekseyev Apr 24 '16 at 3:25