Genomics is an important area of study that holds the promise of unraveling mysteries of how our genes guide our lives and how personalized gene therapies may be used to treat various medical conditions. The increasing adoption of massively-parallel sequencing technologies, known as next generation sequencing (NGS) technologies, has resulted in a situation where computation has become the bottleneck in our ability to ingest all the genetic information and to synthesize actionable knowledge from this information.

Intellectual Merit

We addressed this problem by developing computational approaches, with a focus on the above domain of computational genomics.

Extracting parallelism. We developed a principled way to extract parallelism from applications. We leveraged the approximate nature of some of these applications (e.g., the DNA sequence match does not need to be exact) to aid in the parallelism. We identified coarse-grained, inter-query parallelism and fine-grained, intra-query parallelism inherent in many of the genomics workflows. We developed parallel building blocks for alignment of genomic sequences, assembly of genomes, and pattern mining for determining regulatory elements in the genome, epigenome, and metagenome.

Modeling. The quality of the scaling model determines how well our system can predict the behavior of a program at large scales. We extended existing modeling techniques that can capture a wide variety of scaling behaviors and automatically select which program behaviors to track. We also modeled the data dependence that many of the target algorithms exhibit and came up with techniques to quantify the confidence in the output of the model.

Detection and diagnosis. Because the scaling model captures the relationship between scale and behavior, we used it to predict a program’s behavior even when run at a new, heretofore-unseen scale. Thus, discrepancy between the predicted behavior and the observed behavior was an indicator that there is a manifested software bug. By isolating the source of those deviations to particular program behaviors, such as a particular loop’s executing too many times, we could localize the source of the bug. The key feature of our approach is that the modeling can be done, efficiently, at small scales, and the model applied for detection and diagnosis at large production scales.

Broader Impact

We disseminated the deliverables of the project through open source software, a domain specific language geared toward genomics researchers and practitioners who want to develop scalable and high-performing applications, and tutorials presented at the Biology Division of the Argonne National Laboratory. To further simplify the use of our deliverables, we created a web server that can take queries about which parts of the human epigenome exert a regulatory effect and visualize it. At the backend, this runs a distributed machine learning algorithm that runs a classification task.

Last Modified: 01/15/2017
Modified by: Milind Kulkarni