research-article
Authors: Ernst Joachim Houtgast, VladMihai Sima, Koen Bertels, and Zaid AlArs
ACM SIGARCH Computer Architecture News, Volume 44, Issue 4
Pages 38 - 43
Published: 11 January 2017 Publication History
- 7citation
- 227
- Downloads
Metrics
Total Citations7Total Downloads227Last 12 Months7
Last 6 weeks1
New Citation Alert added!
This alert has been successfully added and will be sent to:
You will be notified whenever a record that you have chosen has been cited.
To manage your alert preferences, click on the button below.
Manage my Alerts
New Citation Alert!
Please log in to your account
Get Access
- Get Access
- References
- Media
- Tables
- Share
Abstract
Next Generation Sequencing techniques have resulted in an exponential growth in the generation of genetics data, the amount of which will soon rival, if not overtake, other Big Data fields, such as astronomy and streaming video services. To become useful, this data requires processing by a complex pipeline of algorithms, taking multiple days even on large clusters. The mapping stage of such genomics pipelines, which maps the short reads onto a reference genome, takes up a significant portion of execution time. BWA-MEM is the de-facto industry-standard for the mapping stage.
Here, a GPU-accelerated implementation of BWA-MEM is proposed. The Seed Extension phase, one of the three main BWA-MEM algorithm phases that requires between 30%-50% of overall processing time, is offloaded onto the GPU. A thorough design space analysis is presented for an optimized mapping of this phase onto the GPU. The re- sulting systolic-array based implementation obtains a two- fold overall application-level speedup, which is the maximum theoretically achievable speedup. Moreover, this speedup is sustained for systems with up to twenty-two logical cores. Based on the findings, a number of suggestions are made to improve GPU architecture, resulting in potentially greatly increased performance for bioinformatics-class algorithms.
References
[1]
N. Ahmed, V. Sima, E.J. Houtgast, K.L.M. Bertels, and Z. Al-Ars. Heterogeneous Hardware/Software Acceleration of the BWA-MEM DNA Alignment Algorithm. In Proc. of the IEEE/ACM Intl. Conf. on Computer-Aided Design, ICCAD, 2015.
Digital Library
[2]
James Hadfield and Nick Loman. Next Generation Genomics: World Map of High-throughput Sequencers. http://omicsmaps.com, 2016. Accessed: 2016-01-13.
[3]
Gareth Highnam, Jason J. Wang, Dean Kusler, Justin Zook, Vinaya Vijayan, Nir Leibovich, and David Mittelman. An Analytical Framework for Optimizing Variant Discovery from Personal Genomes. Nature comm., 6, 2015.
[4]
E.J. Houtgast, V. Sima, K.L.M. Bertels, and Z. Al-Ars. An FPGA-Based Systolic Array to Accelerate the BWA-MEM Genomic Mapping Algorithm. In Int'l. Conf. on Embedded Computer Systems: Architectures, Modeling, and Simulation, 2015.
[5]
E.J. Houtgast, V. Sima, K.L.M. Bertels, and Z. Al-Ars. GPU-Accelerated BWA-MEM Genomic Mapping Algorithm Using Adaptive Load Balancing. In Architecture of Computing Systems-ARCS, pages 130--142. Springer, 2016.
Digital Library
[6]
E.J. Houtgast, V. Sima, G. Marchiori, K.L.M. Bertels, and Z. Al-Ars. Power-Efficient Accelerated Genomic Short Read Mapping on Heterogeneous Computing Platforms. In Proc. 24th IEEE International Symposium on Field-Programmable Custom Computing Machines, Washington DC, USA, May 2016.
[7]
Heng Li. Aligning Sequence Reads, Clone Sequences and Assembly Contigs with BWA-MEM. arXiv preprint arXiv:1303.3997, 2013.
[8]
Lukasz Ligowski and Witold Rudnicki. An efficient implementation of Smith Waterman algorithm on GPU using CUDA, for massively parallel scanning of sequence databases. In Parallel & Distributed Processing, 2009. IPDPS 2009. IEEE International Symposium on, pages 1--8. IEEE, 2009.
Digital Library
[9]
Chi-Man Liu, Thomas Wong, Edward Wu, Ruibang Luo, Siu-Ming Yiu, Yingrui Li, Bingqiang Wang, Chang Yu, Xiaowen Chu, Kaiyong Zhao, and R. Li. SOAP3: Ultra-Fast GPU-Based Parallel Alignment Tool for Short Reads. Bioinformatics, 28(6):878--879, 2012.
Digital Library
[10]
Yongchao Liu, Bertil Schmidt, and Douglas L. Maskell. CUSHAW: a CUDA compatible short read aligner to large genomes based on the Burrows-Wheeler transform. Bioinformatics, 28(14):1830--1837, 2012.
Digital Library
[11]
Yongchao Liu, Adrianto Wirawan, and Bertil Schmidt. CUDASW++ 3.0: Accelerating Smith-Waterman Protein Database Search by Coupling CPU and GPU SIMD Instructions. BMC bioinformatics, 14(1):117, 2013.
[12]
T.F. Smith and MS Waterman. Identification of Common Molecular Subsequences. Journal of molecular biology, 147(1):195--197, 1981.
[13]
Z.D. Stephens, S.Y. Lee, F. fa*ghri, R.H. Campbell, C. Zhai, M.J. Efron, R. Iyer, M.C. Schatz, S. Sinha, and G.E. Robinson. Big Data: Astronomical or Genomical? PLoS Biology, 13(7), 2015.
Cited By
View all
- Schmidt BHildebrandt A(2024)Dedicated Bioinformatics Analysis HardwareReference Module in Life Sciences10.1016/B978-0-323-95502-7.00022-1Online publication date: 2024
- Park SKim HAhmad TAhmed NAl-Ars ZHofstee HKim YLee J(2022)SALoBa: Maximizing Data Locality and Workload Balance for Fast Sequence Alignment on GPUs2022 IEEE International Parallel and Distributed Processing Symposium (IPDPS)10.1109/IPDPS53621.2022.00076(728-738)Online publication date: May-2022
- Masouros DKoliogeorgi KZervakis GKosvyra AChytas AXydis SChouvarda ISoudris D(2019)Co-design Implications of Cost-effective On-demand Acceleration for Cloud Healthcare Analytics: The AEGLE approach2019 Design, Automation & Test in Europe Conference & Exhibition (DATE)10.23919/DATE.2019.8714934(622-625)Online publication date: Mar-2019
- Show More Cited By
Recommendations
- Implementation of Short Read Alignment Algorithm in OpenCL on Xeon Phi Coprocessor
HPCC-CSS-ICESS '15: Proceedings of the 2015 IEEE 17th International Conference on High Performance Computing and Communications, 2015 IEEE 7th International Symposium on Cyberspace Safety and Security, and 2015 IEEE 12th International Conf on Embedded Software and Systems
Aligning sequencing reads to a reference genome is often essential in many comparative genomics pipelines. With the maturation of next-generation DNA sequencing (NGS) technologies, an enormous amount of sequence data has been generated, this calls for ...
Read More
- Microindel detection in short-read sequence data
Motivation: Several recent studies have demonstrated the effectiveness of resequencing and single nucleotide variant (SNV) detection by deep short-read sequencing platforms. While several reliable algorithms are available for automated SNV detection, ...
Read More
- Fast and accurate short read alignment with Burrows–Wheeler transform
Motivation: The enormous amount of short reads generated by the new DNA sequencing technologies call for the development of fast and accurate read alignment programs. A first generation of hash table-based methods has been developed, including MAQ, ...
Read More
Comments
Information & Contributors
Information
Published In
ACM SIGARCH Computer Architecture News Volume 44, Issue 4
HEART '16
September 2016
96 pages
ISSN:0163-5964
DOI:10.1145/3039902
- Editor:
- Babak Falsafi
Interim
Issue’s Table of Contents
Copyright © 2017 Authors.
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 11 January 2017
Published inSIGARCHVolume 44, Issue 4
Check for updates
Qualifiers
- Research-article
Contributors
Other Metrics
View Article Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations
7
Total Citations
227
Total Downloads
- Downloads (Last 12 months)7
- Downloads (Last 6 weeks)1
Other Metrics
View Author Metrics
Citations
Cited By
View all
- Schmidt BHildebrandt A(2024)Dedicated Bioinformatics Analysis HardwareReference Module in Life Sciences10.1016/B978-0-323-95502-7.00022-1Online publication date: 2024
- Park SKim HAhmad TAhmed NAl-Ars ZHofstee HKim YLee J(2022)SALoBa: Maximizing Data Locality and Workload Balance for Fast Sequence Alignment on GPUs2022 IEEE International Parallel and Distributed Processing Symposium (IPDPS)10.1109/IPDPS53621.2022.00076(728-738)Online publication date: May-2022
- Masouros DKoliogeorgi KZervakis GKosvyra AChytas AXydis SChouvarda ISoudris D(2019)Co-design Implications of Cost-effective On-demand Acceleration for Cloud Healthcare Analytics: The AEGLE approach2019 Design, Automation & Test in Europe Conference & Exhibition (DATE)10.23919/DATE.2019.8714934(622-625)Online publication date: Mar-2019
- Schmidt BHildebrandt A(2019)Dedicated Bioinformatics Analysis HardwareEncyclopedia of Bioinformatics and Computational Biology10.1016/B978-0-12-809633-8.20186-6(1142-1150)Online publication date: 2019
- Vijayaraghavan TRajesh ASankaralingam K(2018)MPU-BWM: Accelerating Sequence AlignmentIEEE Computer Architecture Letters10.1109/LCA.2018.284906417:2(179-182)Online publication date: 1-Jul-2018
- Wang ZZhang MZhang JYan RWan XLiu ZZhang FCui X(2018)Mmalloc: A Dynamic Memory Management on Many-core Coprocessor for the Acceleration of Storage-intensive Bioinformatics Application2018 IEEE International Conference on Bioinformatics and Biomedicine (BIBM)10.1109/BIBM.2018.8621415(771-774)Online publication date: Dec-2018
- Houtgast ESima VBertels KAl-Ars Z(2018)Comparative Analysis of System-Level Acceleration Techniques in Bioinformatics: A Case Study of Accelerating the Smith-Waterman Algorithm for BWA-MEM2018 IEEE 18th International Conference on Bioinformatics and Bioengineering (BIBE)10.1109/BIBE.2018.00053(243-246)Online publication date: Oct-2018
View Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in
Full Access
Get this Publication
View options
View or Download as a PDF file.
PDFeReader
View online with eReader.
eReaderMedia
Figures
Other
Tables
