Efficient parallel and out of core algorithms for constructing large bi-directed de Bruijn graphs

Vamsi K. Kundeti, Sanguthevar Rajasekaran, and Hieu Dinh are with the Department of Computer Science and Engineering, University of Connecticut,371 Fairfield Way, U-2155, Storrs, CT, 06269, USA. -- Matthew Vaughn is with the Texas Advanced Computing Center, University of Texas at Austin, TX, 78758, USA. -- Vishal Thapar is with Cold Spring Harbor Laboratory, One Bungtown Road, Cold Spring Habor, NY, 11724, USA. ; Background: Assembling genomic sequences from a set of overlapping reads is one of the most fundamental problems in computational biology. Algorithms addressing the assembly problem fall into two broad categories - based on the data structures which they employ. The first class uses an overlap/string graph and the second type uses a de Bruijn graph. However with the recent advances in short read sequencing technology, de Bruijn graph based algorithms seem to play a vital role in practice. Efficient algorithms for building these massive de Bruijn graphs are very essential in large sequencing projects based on short reads. In an earlier work, an O(n/p) time parallel algorithm has been given for this problem. Here n is the size of the input and p is the number of processors. This algorithm enumerates all possible bi-directed edges which can overlap with a node and ends up generating Θ(nΣ) messages (Σ being the size of the alphabet). Results: In this paper we present a Θ(n/p) time parallel algorithm with a communication complexity that is equal to that of parallel sorting and is not sensitive to Σ. The generality of our algorithm makes it very easy to extend it even to the out-of-core model and in this case it has an optimal I/O complexity of Θ(nlog(n/B)Blog(M/B)) (M being the main memory size and B being the size of the disk block). We demonstrate the scalability of our parallel algorithm on a SGI/Altix computer. A comparison of our algorithm with the previous approaches reveals that our algorithm is faster - both asymptotically and practically. We demonstrate the scalability of our sequential out-of-core ...