Eﬃcient Out-of-Core Contig Generation - Entenza, Julio Omar Prieto; Haeusler, Edward Hermann; Lifschitz, Sérgio (Anais do Simpósio Brasileiro de Bioinformática (BSB); 2020: Anais do XIII Simpósio Brasileiro de Bioinformática, 2020)
Genome sequencing involves splitting a genome into a set reads that are assembled into contigs that are eventually ordered and organized as scaﬀolds. 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 eﬃcient 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.