Charging Station: Reconstructing String in Paired De Bruijn Graph

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:

AG-AG → GC-GC → CT-CT → TG-TG → GC-GC → CA-CT → AG-TG → GC-GC → CT-CA

An attempt to assemble these (2, 1)-mers reveals that not every column has the same nucleotide (see the two columns shown in red below). This example illustrates that not all Eulerian paths in the paired de Bruijn graph spell solutions of the String Reconstruction from Read-Pairs Problem.

String Spelled by a Gapped Genome Path Problem

---

String Spelled by a Gapped Genome Path Problem <br><br>Problem overview: <br> Reconstruct a sequence of (k, d)-mers corresponding to a path in a paired de Bruijn graph. <br><br> Input: A sequence of (k, d)-mers ($a_{1}|b_{1}$ ...