A work stealing based approach for enabling scalable optimal sequence homology detection
By: Researcher
Disclaimer: The provided code links for this paper are external links. Science Nest has no responsibility for the accuracy, legality or content of these links. Also, by downloading this code(s), you agree to comply with the terms of use as set out by the author(s) of the code(s).
Please contact us in case of a broken link from here
| Authors | Jeff Daily, Ananth Kalyanaraman, Sriram Krishnamoorthy, Abhinav Vishnu |
| Journal/Conference Name | Journal of Parallel and Distributed Computing |
| Paper Category | Artificial Intelligence |
| Paper Abstract | Sequence homology detection is central to a number of bioinformatics applications including genome sequencing and protein family characterization. Given millions of sequences, the goal is to identify all pairs of sequences that are highly similar (or “homologous”) on the basis of alignment criteria. While there are optimal alignment algorithms to compute pairwise homology, their deployment for large-scale is currently not feasible; instead, heuristic methods are used at the expense of quality. Here, we present the design and evaluation of a parallel implementation for conducting optimal homology detection on distributed memory supercomputers. Our approach uses a combination of techniques from asynchronous load balancing (viz. work stealing, dynamic task counters), data replication, and exact-matching filters to achieve homology detection at scale. Results for 2.56 M sequences on up to 8K cores show parallel efficiencies of , a time-to-solution of 33 s, and a rate of alignments per second. |
| Date of publication | 2014 |
| Code Programming Language | C++ |
| Comment |
Copyright Researcher 2022