Lesson 6

It turns out that there is a much more efficient approach. It shows, in particular, how important it is to correctly reformulate the problem. In the previous approach, each input string corresponded to a vertex. Now let’s try to represent each occurrence of a string as an edge: string \(s\) will be an edge from \(s\) without the last character to \(s\) without the first character (from the prefix to the suffix). For example, the string \(\texttt{CAT}\) will be the edge \({\tt CA}\to{\tt AT}\). Repeated occurrences give parallel edges. The resulting graph is called the de Bruijn graph.

In the resulting graph, it is enough to find an Eulerian path, which can be done very quickly. The existence of an Eulerian path in this graph follows from the fact that we are given the full multiset of \(k\)-mer occurrences of the unknown string. In the general case, we do not know algorithms that work faster than finding the heaviest Hamiltonian path in the overlap graph.

import networkx as nx
from networkx import DiGraph, eulerian_path

reads = ['AGC', 'ATC', 'CAG', 'CAT', 'CCA', 'GCA', 'TCA', 'TCC']
graph = DiGraph(strict=False)
for read in reads:
    graph.add_edge(read[:-1], read[1:])

path = list(eulerian_path(graph))
print(path[0][0] + ''.join(e[1][-1] for e in path))

TCCATCAGCA