Orion: scaling genomic sequence matching with fine-grained parallelization

Gene sequencing instruments are producing huge volumes of data, straining the capabilities of current database searching algorithms and hindering efforts of researchers analyzing large collections of data to obtain greater insights. In the space of parallel genomic sequence search, most of the popul...

Full description

Saved in:
Bibliographic Details
Main Authors: Mahadik, Kanak, Chaterji, Somali, Zhou, Bowen, Kulkarni, Milind, Bagchi, Saurabh
Format: Conference Proceeding
Language:English
Subjects:
Applied computing > Life and medical sciences > Computational biology
Applied computing > Life and medical sciences > Genetics
Applied computing > Life and medical sciences > Systems biology
Bioinformatics
Computer systems organization > Dependable and fault-tolerant systems and networks
DNA
General and reference > Cross-computing tools and techniques > Performance
Genomics
Networks > Network performance evaluation
Organisms
Parallel processing
Theory of computation > Design and analysis of algorithms > Approximation algorithms analysis > Scheduling algorithms
Theory of computation > Design and analysis of algorithms > Online algorithms > Online learning algorithms > Scheduling algorithms
Theory of computation > Theory and algorithms for application domains > Machine learning theory > Reinforcement learning > Sequential decision making
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Gene sequencing instruments are producing huge volumes of data, straining the capabilities of current database searching algorithms and hindering efforts of researchers analyzing large collections of data to obtain greater insights. In the space of parallel genomic sequence search, most of the popular software packages, 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 than database sharding alone, while maintaining 100% accuracy. We show that it is 12.3X faster than mpiBLAST for solving a relevant comparative genomics problem.
ISSN:2167-4329
2167-4337
DOI:10.1109/SC.2014.42