HotCSE Seminar
Computational Science & Engineering
Wednesday October 07, 11am-12pm, 1116-W Klaus

A Parallel Connectivity Algorithm for de-Bruijn Graphs in Metagenomic Applications

Chirag Jain
Advisor: Prof. Srinivas Aluru


Dramatic advances in DNA sequencing technology have made it possible to study microbial environments by direct sequencing of environmental DNA samples. Yet, due to the huge volume and high data complexity, current de novo assemblers cannot handle large metagenomic data sets or fail to perform assembly with acceptable quality. This work presents the first parallel solution for decomposing the metagenomic assembly problem without compromising the post-assembly quality. We transform this problem into that of finding weakly connected components in the de Bruijn graph. We propose a novel distributed memory algorithm to identify the connected sub-graphs, and present strategies to minimize the communication volume. We demonstrate the scalability of our algorithm on a soil metagenome data set with 1.8 billion reads. Our approach achieves a runtime of 22 minutes using 1280 Intel Xeon cores for a 421 GB uncompressed FASTQ dataset. Moreover, our solution is generalizable to finding connected components in arbitrary undirected graphs.


Chirag joined Dr Aluru's lab in Fall'14 as a CSE PhD student. He earned his bachelor’s degree in CS at Indian Institute of Technology at New Delhi, India. His current research is focused on designing the high performance computational methods for meta-genomics, an emerging area in the bioinformatics domain.