Out-of-core de novo assembly framework for large scale genome

Abstract

De novo assembly is a vital process in modern genomics that recovers the genomes from short DNA fragments. For the recovery, it first constructs the assembly graph that represents the overlap between different fragments and then concatenates the overlapped fragments by traversing the assembly graph. However, the input genomic datasets for de novo assembly often include a large genome or thousands of small genomes, making the corresponding assembly graph at a massive scale. To this end, this dissertation proposes OC-assembler, a de novo assembly framework that stores the assembly graph in storage and processes the graph in an out-of-core fashion. OC-assembler introduces a new graph data structure that reduces the memory footprint by considering the double-stranded structure of an input genome, thereby significantly reducing the storage I/O. Further, OC-assembler efficiently handles the iterative graph update of the de novo assembly by storing a small update log instead of overwriting the entire graph in storage when the amount of updates is small. Our evaluation on diverse genome datasets shows that OC-assembler reduces the storage I/O by 2.9×, thereby shortening the execution time by 2.1× compared to existing out-of-core graph processing methods.