Constructing Universal Strings
Explore the construction of k-universal circular strings by applying Eulerian cycles on de Bruijn graphs. Understand how these concepts model the assembly of circular genomes like bacterial chromosomes, and solve the k-Universal Circular String Problem using algorithmic approaches.
We'll cover the following...
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 exactly once (in the figure given below).
k-Universal Circular String Problem
Problem overview:
Find a k-universal circular string.
Input: An integer k.
Output: A k-universal circular string.
Sample dataset: ...