Parallel Construction of Bidirected String Graphs for Genome Assembly

Graph theoretic models for genome assembly are continually being proposed and refined. At the same time, large scale assembly projects rely on the overlap-layout-consensus assembly paradigm, in which the best pairwise alignments serve as seeds for a greedy extension of contigs. These methods, which largely rely on local information, are used despite research that demonstrates the superiority of other graph models, largely because the memory requirement of such models is prohibitive on single processor architectures. In this paper, we present a parallel algorithm for constructing bidirected string graphs from whole genome shotgun sequencing data, for use in the assembly problem. Our algorithm uses O(n/p) local computation - where n is the total size of shotgun sequences and p is the number of processors - and a constant number of all-to-all communications. We demonstrate scalability of the algorithm on the Blue Gene/L, and show that graphs for large, complex genome sequencing projects with deep sequence coverage can be effectively handled using parallel computers.