4
$\begingroup$

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$.

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

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$.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.