Assembling genomes: Transforming Read-Pairs to Long Virtual Reads

Constructing de Bruijn graph from long reads

Let Reads be the collection of all $2N$ k-mer reads taken from N read-pairs. Note that a read-pair formed by k-mer reads Read$_{1}$ and Read$_{2}$ corresponds to two edges in the de Bruijn graph DeBruijn$_{k}$ (Reads). Since these reads are separated by distance d in the genome, there must be a path of length k + d + 1 in DeBruijn$_{k}$ (Reads) connecting the node at the beginning of the edge corresponding to Read$_{1}$ with the node at the end of the edge corresponding to Read$_{2}$, as shown in the figure below. If there’s only one path of length k + d + 1 connecting these nodes, or if all such paths spell out the same string, then we can transform a read-pair formed by reads Read$_{1}$ and Read$_{2}$ into a virtual read of length 2 · k + d that starts as Read$_{1}$, spells out this path, and ends with Read$_{2}$.