Charging Station: Reconstructing String in Paired De Bruijn Graph
Explore the process of reconstructing DNA sequences from paired de Bruijn graphs by examining Eulerian paths and overlapping k-mers. Understand how string spelled by gapped patterns algorithms assemble strings from (k, d)-mers, and learn to identify when perfect overlap enables successful genome reconstruction.
We'll cover the following...
Consider the following Eulerian path formed by nine edges in the paired de Bruijn graph from the figure below.
AG-AG → GC-GC → CA-CT → AG-TG →GC-GC → CT-CT → TG-TG → GC-GC → CT-CA
We can arrange the (2, 1)-mers in this path into the nine rows shown below, revealing the string AGCAGCTGCTGCA spelled by this path:
Now, consider another Eulerian path in the paired de Bruijn graph from the above figure: ...
String Spelled by a Gapped Genome Path Problem
String Spelled by a Gapped Genome Path Problem
Problem overview:
Reconstruct a sequence of (k, d)-mers corresponding to a path in a paired de Bruijn graph.
Input: A sequence of (k, d)-mers ( ...