Cycles · Application: Genome Assembly and de Bruijn Graphs

Lesson 5

Nikolai Chukhin · Alexander S. Kulikov

Let’s return to the problem of finding the shortest string that contains all the following strings as substrings: \[{\tt AGC},{\tt ATC},{\tt CAG},{\tt CAT},{\tt CCA},{\tt GCA},{\tt TCA},{\tt TCC}.\] Suppose we know that all the 3-mer occurrences (i.e., substrings of length three, with multiplicities) of the unknown string are given. How can we find the string itself? Clearly, adjacent 3-mers overlap by two characters. Therefore, we can draw a graph of all the overlaps and simply find a Hamiltonian path in it!

In this graph, there is, for example, a Hamiltonian path: \({\tt TCA}\to{\tt CAG}\to{\tt AGC}\to{\tt GCA}\to{\tt CAT}\to{\tt ATC}\to{\tt TCC}\to{\tt CCA}\). From this path, it is easy to reconstruct the superstring: \(\texttt{TCAGCATCCA}\).

We have found an approach to solve the problem, but how satisfactory is it? Actually, it is not satisfactory at all: we do not have efficient algorithms for finding a Hamiltonian path! If the number of input strings reaches hundreds of thousands, as in genome assembly in practice, our approach will be utterly helpless.