Introduction

Massively parallel DNA sequencing technologies are revolutionizing genomics research. Billions of short reads generated at low costs can be assembled for reconstructing the whole genomes. Unfortunately, the large memory footprint of the existing de novo assembly algorithms makes it challenging to get the assembly done for higher eukaryotes like mammals. In this work, we investigate the memory issue of constructing de Bruijn graph, a core task in leading assembly algorithms, which often consumes several hundreds of gigabytes memory for large genomes. We propose a disk-based partition method, called Minimum Substring Partitioning (MSP), to complete the task using less than 10 gigabytes memory, without runtime slowdown. MSP breaks the short reads into multiple small disjoint partitions so that each partition can be loaded into memory, processed individually and later merged with others to form a de Bruijn graph. By leveraging the overlaps among the k-mers (substring of length k), MSP achieves astonishing compression ratio: The total size of partitions is reduced from Θ(kn) to Θ(n), where n is the size of the short read database, and k is the length of a k-mer. Experimental results show that our method can build de Bruijn graphs using a commodity computer for any large-volume sequence dataset.

Algorithm Overview

Minimum Substring Partitioning comes from the intuition that two adjacent k-mers are very likely to share the same minimum p-substring if p << k, since there is a length-(k-1) overlap between them. Figure below shows a Minimum Substring Partitioning example. In this example, the first 4 k-mers have the same minimum 4-substring, ACAC, as highlighted in red box; and the last 3 k-mers share the same minimum 4-substring, ACCC, as highlighted in blue box. In this case, instead of generating all these 7 k-mers separately, we can just compress them using the original short read. Namely, we compress the first 4 k-mers to CTGACACTTGACCCGTGGT, and output it to the partition corresponding to the minimum 4-substring ACAC. Similarly, the last 3 k-mers are compressed to CACTTGACCCGTGGTCAT and outputted to the partition corresponding to the minimum 4-substring ACCC. Generally speaking, given a short read s = s1s2 ... sn, if the adjacent j k-mers from s[i; i + k − 1] to s[i + j − 1; i + j + k − 2] share the same minimum p-substring t, then we can just output substring sisi+1 ... si+j+k−2 to the partition corresponding to the minimum p-substring t without breaking it to j individual k-mers. If j is large, this compression strategy will dramatically reduce the I/O cost.

For more details about the algorithm and the performance issues, please refer to the documents