Search⌘ K
Home
Courses
Bioinformatics Algorithms

String Reconstruction With Overlap Graph: The Genome Vanishes

Learn to construct and interpret overlap graphs from collections of k-mers, a crucial step in genome assembly. This lesson guides you through understanding how reads overlap by suffix and prefix matching, enabling reconstruction of genome sequences even when direct paths seem to vanish.

We'll cover the following...

The genome can still be traced out in the graph in the figureFIGURE3_7 by following the horizontal path from TAA to GTT. But in genome sequencing, we don’t know in advance how to correctly order reads. Therefore we’ll arrange the 3-mers lexicographically, which produces the overlap graph shown in the figure below. The genome path has disappeared!

STOP and Think: Can any other strings be reconstructed by following a path visiting all the nodes in the above figure?

Finding genome path

The genome path may have disappeared to the naked eye, but it must still be there, since we’ve simply rearranged the nodes of the graph. Indeed, the figure below (top) highlights the genome path spelling out TAATGCCATGGGATGTT. However, if we had given you this graph to begin with, you would’ve ...