TY - GEN
T1 - Characterizing and optimizing the memory footprint of de novo short read DNA sequence assembly
AU - Cook, Jeffrey J.
AU - Zilles, Craig
PY - 2009/9/22
Y1 - 2009/9/22
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=70349184314&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=70349184314&partnerID=8YFLogxK
U2 - 10.1109/ISPASS.2009.4919646
DO - 10.1109/ISPASS.2009.4919646
M3 - Conference contribution
AN - SCOPUS:70349184314
SN - 9781424441846
T3 - ISPASS 2009 - International Symposium on Performance Analysis of Systems and Software
SP - 143
EP - 152
BT - ISPASS 2009 - International Symposium on Performance Analysis of Systems and Software
T2 - International Symposium on Performance Analysis of Systems and Software, ISPASS 2009
Y2 - 26 April 2009 through 28 April 2009
ER -