Characterizing and optimizing the memory footprint of de novo short read DNA sequence assembly

In this work, we analyze the memory-intensive bioinformatics problem of "de novo" DNA sequence assembly, which is the process of assembling short DNA sequences obtained by experiment into larger contiguous sequences. In particular, we analyze the performance scaling challenges inherent to de Bruijn graph-based assembly, which is particularly well suited for the data produced by "next generation" sequencing machines. Unlike many bioinformatics codes which are computationintensive or control-intensive, we find the memory footprint to be the primary performance issue for de novo sequence assembly. Specifically, we make four main contributions: 1) we demonstrate analytically that performing error correction before sequence assembly enables larger genomes to be assembled in a given amount of memory, 2) we identify that the use of this technique provides the key performance advantage to the leading assembly code, Velvet, 3) we demonstrate how this pre-assembly error correction technique can be subdivided into multiple passes to enable de Bruijn graph-Based assembly to scale to even larger genomes, and 4) we demonstrate how Velvet's in-core performance can be improved using memorycentric optimizations.