An Efficient GPU-Accelerated Implementation of Genomic Short Read Mapping with BWA-MEM

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 elds, 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 signicant 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 ooaded 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 ndings, a number of suggestions are made to
improve GPU architecture, resulting in potentially greatly increased performance for bioinformatics-class algorithms.