Bioinformatics AlgorithmsAn Active Learning Approach
You are reading the free online edition. Autograded code challenges and a certificate are in the interactive text, free to start.Solve these problems with autograders, free

Lesson 3.8

From Euler's Theorem to an Algorithm for Finding Eulerian Cycles

6 min read4 code challenges✓ Read

Watch the lectureReturning to Konigsberg

Constructing Eulerian cycles

The proof of Euler’s Theorem offers an example of what mathematicians call a constructive proof, which not only proves the desired result, but also provides us with a method for constructing the object we need. In short, we track Leo’s movements until he inevitably produces an Eulerian cycle in a balanced and strongly connected graph Graph, as summarized in the following pseudocode.


EulerianCycle(Graph)
    form a cycle Cycle by randomly walking in Graph (don't visit the same edge twice!)
    while there are unexplored edges in Graph
        select a node newStart in Cycle with still unexplored edges
        form Cycle’ by traversing Cycle (starting at newStart) and then randomly walking
        Cycle ← Cycle’
    return Cycle

You should now be prepared to solve the Eulerian Cycle Problem for any graph. It may not be obvious, but a good implementation of EulerianCycle will work in linear time. To achieve this runtime speedup, you would need to use an efficient data structure in order to maintain the current cycle that Leo is building as well as the list of unused edges incident to each node and the list of nodes on the current cycle that have unused edges.

Try it Step through EulerianCycle, then try the bridges of Königsberg

Now write it yourself: Implement EulerianCycle in the interactive text.

Code Challenge Solve the Eulerian Cycle Problem. (Solve at Cogniterra or Rosalind.)Solve it with the autograderFree to start in the interactive text

  •      Input: The adjacency list of an Eulerian directed graph.
  •      Output: An Eulerian cycle in this graph.

From Eulerian cycles to Eulerian paths

We can now check if a directed graph has an Eulerian cycle, but what about an Eulerian path? Consider the de Bruijn graph on the left in the figure below, which we already know has an Eulerian path, but which does not have an Eulerian cycle because nodes TA and TT are not balanced. However, we can transform this Eulerian path into an Eulerian cycle by adding a single edge connecting TT and TA, as shown in the figure below.

STOP and Think How many unbalanced nodes does a graph with an Eulerian path have?

Eulerian path to cycle

Figure: Transforming an Eulerian path (left) into an Eulerian cycle (right) by adding an edge.

More generally, consider a graph that does not have an Eulerian cycle but does have an Eulerian path. If an Eulerian path in this graph connects a node v to a different node w, then the graph is nearly balanced, meaning that all its nodes except v and w are balanced. In this case, adding an extra edge from w to v transforms the Eulerian path into an Eulerian cycle. Thus, a nearly balanced graph has an Eulerian path if and only if adding an edge between its unbalanced nodes makes the graph balanced and strongly connected.

STOP and Think Find an analogue of the nearly balanced condition that will determine when an undirected graph has an Eulerian path.

The analogue of Euler’s theorem for undirected graphs immediately implies that there is no Eulerian path in Königsberg. However, the story is different in modern-day Kaliningrad; for more details, see "DETOUR: The Bridges of Kaliningrad" in the print companion or at Cogniterra.

Code Challenge Solve the Eulerian Path Problem. (Solve at Cogniterra or Rosalind.)Solve it with the autograderFree to start in the interactive text

  • Input: The adjacency list of a directed graph that has an Eulerian path.
  • Output: An Eulerian path in this graph.

You now have a method to assemble a genome, since the String Reconstruction Problem reduces to finding an Eulerian path in the de Bruijn graph generated from reads.

We can therefore summarize this solution using the following pseudocode, which relies on three problems that we have already solved:

  1. The de Bruijn Graph Construction Problem;
  2. The Eulerian Path Problem;
  3. The String Spelled by a Genome Path Problem.
    StringReconstruction(Patterns)
        dB ← DeBruijn(Patterns)
        path ← EulerianPath(dB)
        Text ← PathToGenome(path)
        return Text

Code Challenge Solve the String Reconstruction Problem. (Solve at Cogniterra or Rosalind.)Solve it with the autograderFree to start in the interactive text

  • Input: An integer k followed by a list of k-mers Patterns.
  • Output: A string Text with k-mer composition equal to Patterns. (If multiple answers exist, you may return any one.)

Constructing universal strings

Now that you know how to use the de Bruijn graph to solve the String Reconstruction Problem, you can also construct a k-universal string for any value of k.

We should note that de Bruijn was interested in constructing k-universal circular strings. For example, 00011101 is a 3-universal circular string, as it contains each of the eight binary 3-mers (000, 001, 011, 111, 110, 101, 010, and 100) exactly once (see the figure below).

k-Universal Circular String Problem: Find a k-universal circular string.

  • Input: An integer k.
  • Output: A k-universal circular string.

K universal circular string

Figure: The circular 3-universal string 00011101 contains each of the binary 3-mers exactly once.

Like its analogue for linear strings, the k-Universal Circular String Problem is just a specific case of a more general problem, which requires us to reconstruct a circular string given its k-mer composition. This problem models the assembly of a circular genome containing a single chromosome, like the genomes of most bacteria. We know that we can reconstruct a circular string from its k-mer composition by finding an Eulerian cycle in the de Bruijn graph constructed from these k-mers. Therefore, we can construct a k-universal circular binary string by finding an Eulerian cycle in the de Bruijn graph constructed from the collection of all binary k-mers (see figure below).

Exercise Break How many 3-universal circular strings are there?

Debruijn graph circular

Figure: (Top) A graph consisting of eight isolated directed edges, one for each binary 3-mer. The nodes of each edge correspond to the 3-mer’s prefix and suffix. (Bottom) Gluing identically labeled nodes in the graph on top results in a de Bruijn graph containing four nodes. An Eulerian cycle through the edges 000 → 001 → 011 → 111 → 110 → 101 → 010 → 100 yields the 3-universal circular string 00011101.

Even though finding a 20-universal circular string amounts to finding an Eulerian cycle in a graph with over a million edges, we now have a fast algorithm for solving this problem. Let BinaryStringsk be the set of all 2k binary k-mers. The only thing we need to do is solve the k-Universal Circular String Problem is to find an Eulerian cycle in DeBruijn(BinaryStringsk). Note that the nodes of this graph represent all possible binary (k - 1)-mers. A directed edge connects (k - 1)-mer Pattern to (k - 1)-mer Pattern' in this graph if there exists a k-mer whose prefix is Pattern and whose suffix is Pattern'.

STOP and Think The figure below illustrates that DeBruijn(BinaryStrings4) is balanced and strongly connected and is thus Eulerian. Can you prove that for any k, DeBruijn(BinaryStringsk) is Eulerian?

4 universal string

Figure: An Eulerian cycle spelling the cyclic 4-universal string 0000110010111101 in DeBruijn(BinaryStrings4).

Code Challenge Solve the k-Universal Circular String Problem. (Solve at Cogniterra or Rosalind.)Solve it with the autograderFree to start in the interactive text

  • Input: An integer k.
  • Output: A k-universal circular string.