Efficient Out-of-Core Contig Generation

• Julio Omar Prieto Entenza PUC-Rio http://orcid.org/0000-0002-8164-9965
• Edward Hermann Haeusler PUC-Rio http://orcid.org/0000-0002-4999-7476
• Sérgio Lifschitz PUC-Rio http://orcid.org/0000-0003-3073-3734

Abstract

Genome sequencing involves splitting a genome into a set reads that are assembled into contigs that are eventually ordered and organized as scaffolds. There are many programs that consider the use of the de Bruijn Graph (dBG) but they must deal with a high computational cost, mainly due to internal RAM consumption. We propose to use an external memory approach to deal with the de Bruijn graph construction focusing on contig generation. Our proposed algorithms are based on well-known I/O efficient methods that identify unitigs and remove errors such as tips and bubbles. Our analytical evaluation shows that it becomes feasible to generate de Bruijn graphs to obtain the needed contigs, independently of the available memory.