Parallel analysis of large graph-structured data in genomics and proteomics

This talk presents two new software tools that our research group is developing: lark, a de novo genome assembler, and FASCIA, a tool to approximately count and enumerate network motifs. Our de novo genome assembly approach involves construction, traversal, and simplification of de Bruijn graphs on large multicore clusters. We present new parallelization strategies and optimizations for various steps of the assembly process, focusing on techniques for scalable de Bruijn graph construction from short-read data. We demonstrate the parallel efficiency and scalability of our assembler with performance results and analysis of several recent metagenomic data sets. The problem of subgraph counting refers to determining the frequency of occurrence of a given subgraph or template within a large network. Subgraph counting is used to detect and characterize local structure (network motifs) in several biological networks, including protein interaction networks and metabolic networks. Exhaustive enumeration and exact counting is extremely compute-intensive, with running time growing exponentially with the number of vertices in the template. In FASCIA, we combine parallelism with the color coding technique to determine approximate counts of non-induced occurrences of the subgraph in the original network. The color coding technique gives a fast approximate algorithm for this problem, using a dynamic programming-based counting approach. Our new contributions are a multilevel shared-memory parallelization of the counting scheme and several optimizations to reduce the memory footprint. We show that approximate counts can be obtained for templates with up to 12 vertices, on networks with up to millions of vertices and edges.