Building de Bruijn Graphs From Overlapping Words

From Word Overlap to Directed Edges

Suppose a collection of words is organized by how much consecutive information they share. A useful way to record that structure is to make each shorter word a vertex, then represent each longer word by a directed edge from its initial part to its final part. The edge records not only which two shorter words are related, but also the exact longer word that produces the relation.

Fix a finite nonempty alphabet \(\Sigma\), and write \(q=|\Sigma|\) for its number of symbols. A word of length \(r\) is an ordered sequence of \(r\) symbols from \(\Sigma\); the unique word of length zero is denoted by \(\varepsilon\). Let \(k\) be a positive integer. For a word \(w=w_1w_2\cdots w_k\) of length \(k\), its prefix of length \(k-1\) is \(w_1\cdots w_{k-1}\), and its suffix of length \(k-1\) is \(w_2\cdots w_k\). When \(k=1\), both are \(\varepsilon\).

Thus “order \(k\)” refers to the length of the edge words, not the length of the vertex words. Each edge moves from a word to the word obtained by dropping its first symbol and appending one new symbol. For \(k\ge2\), the two endpoint words overlap in \(k-2\) symbols. For \(k=1\), there is just one vertex, the empty word, and every symbol gives a loop at that vertex.

How to Construct the Digraph

The construction can be carried out systematically. First list every word of length \(k-1\). Then list every word of length \(k\), and for each one record its prefix and suffix of length \(k-1\) as its tail and head. The edge label should be kept: it identifies which length-\(k\) word the edge represents.

Overlap Determines Incidence

Proof. Write \(u=u_1\cdots u_{k-1}\) and \(v=v_1\cdots v_{k-1}\). If a length-\(k\) word gives an edge from \(u\) to \(v\), then that word has prefix \(u\) and suffix \(v\). The symbols common to these two parts must therefore agree: \(u_2\cdots u_{k-1}=v_1\cdots v_{k-2}\). This proves the required overlap condition. Conversely, suppose this equality holds. Form the word \(w=u_1\cdots u_{k-1}v_{k-1}\). Its prefix of length \(k-1\) is \(u\), and its suffix of length \(k-1\) is \(v\), using the assumed overlap. Thus it gives an edge from \(u\) to \(v\). Any word with prefix \(u\) and suffix \(v\) must have its first \(k-1\) symbols fixed by \(u\) and its last symbol fixed by \(v_{k-1}\), so it must equal \(w\). Hence the edge word is unique. For \(k=2\), the overlap consists of zero symbols, so the condition is vacuous and the unique edge from the one-symbol word \(u\) to the one-symbol word \(v\) is \(uv\). \(\square\)

The lemma gives a quick way to check an edge list: compare the overlapping symbols of its endpoints, then recover the label by appending the final symbol of the head to the tail. For order one, the lemma’s endpoint formulation is not needed: both endpoints are \(\varepsilon\), and the edge label is the chosen one-symbol word.

Counts and Degrees

Proof. A word of length \(r\) is formed by making \(r\) independent choices from the \(q\) symbols, so there are \(q^r\) such words. Applying this count with \(r=k-1\) gives \(q^{k-1}\) vertices; applying it with \(r=k\) gives \(q^k\) labelled edges. Now fix a vertex \(u=u_1\cdots u_{k-1}\). Each outgoing edge is formed by appending one symbol \(\sigma\in\Sigma\), giving the word \(u_1\cdots u_{k-1}\sigma\). Its tail is \(u\), and different choices of \(\sigma\) give different edge labels, so there are exactly \(q\) outgoing edges. Each incoming edge is formed by choosing a symbol \(\sigma\in\Sigma\) and taking the word \(\sigma u_1\cdots u_{k-1}\); these are \(q\) distinct labels, each with head \(u\). If \(k=1\), the vertex is \(\varepsilon\); the \(q\) one-symbol words all give loops there, and each is counted once in each directed degree. This proves the counts and degree statements in every case. \(\square\)

The degree calculation is local: each vertex has one outgoing edge for each possible next symbol and one incoming edge for each possible preceding symbol. It does not require the graph to be simple or to have no loops. In fact, the labelled-edge convention is important when different words have the same endpoints.

Why the Construction Is Useful

The vertices summarize the part of a word that must be retained to determine the next overlap. A directed edge then records a possible one-symbol extension. This converts a question about how words fit together into a question about directed incidence. The labels preserve the original words, while the endpoints expose their shared structure.

The equal in-degree and out-degree at every vertex are useful structural checks. If a proposed edge list gives a vertex more incoming than outgoing edges, or omits one of the possible appended symbols, then it does not describe the stated de Bruijn digraph. The theorem establishes the expected degree for every vertex, including vertices with loops.

Common Pitfalls

Using length-\(k\) words as vertices. For the binary example with \(k=3\), a mistaken vertex list would have eight length-three words. The construction instead uses length-\((3-1)=2\) words, giving \(2^{3-1}=4\) vertices; the eight length-three words are the edges. The corrected count is four vertices and \(2^3=8\) edges.

Ignoring loops or labels. In the same binary example, \(000\) gives the loop \(00\to00\), and \(111\) gives \(11\to11\). Omitting loops would lose these two words. At order one, all edge words have the same endpoints, so forgetting labels would merge distinct edges and lose the word-to-edge correspondence.

Reversing prefix and suffix. The edge for \(101\) goes from \(10\) to \(01\), not from \(01\) to \(10\): the tail is the prefix and the head is the suffix. Checking both endpoints against the original word prevents this direction error.