Orion: Scaling Genomic Sequence Matching with Fine-Grained Parallelization
Acceptance rate 21%
Abstract
Gene sequencing instruments are producing huge volumes of data, straining the capabilities of current database searching algorithms and hindering efforts of researchers analyzing larger collections of data to obtain greater insights. In the space of parallel genomic sequence search, most of the popular softwares, like mpiBLAST, use the database segmentation approach, wherein the entire database is sharded and searched on different nodes. However this approach does not scale well with the increasing length of individual query sequences as well as the rapid growth in size of sequence databases. In this paper, we propose a fine-grained parallelism technique, called Orion, that divides the input query into an adaptive number of fragments and shards the database. Our technique achieves higher parallelism (and hence speedup) and load balancing, while maintaining 100% accuracy. We show that it is 12.3X faster than mpiBLAST for solving a relevant comparative genomics problem.
BibTeX
@inproceedings{mahadik14sc,
author = {Kanak Mahadik and Somali Chaterji and Bowen Zhou and Milind Kulkarni and Saurabh Bagchi},
title = {Orion: Scaling Genomic Sequence Matching with Fine-Grained Parallelization},
booktitle = {Proceedings of the The International Conference for High Performance Computing, Networking, Storage and Analysis (SC)},
pages = {449--460},
publisher = {IEEE Press},
address = {New Orleans, Louisana},
year = {2014},
month = nov,
doi = {10.1109/SC.2014.42}
}