Bilkent University
Department of Computer Engineering
CS 590 SEMINAR
GateKeeper-GPU : Hardware Construction for Accelerated Pre-Alignment Filtering in Short Read Mapping
Zülal Bingöl
MS Student
Computer Engineering Department
Bilkent University
Recent advances in high throughput sequencing (HTS) facilitate fast production of short DNA fragments (reads) in numerous amounts. Although the production is becoming inexpensive everyday, processing the present data for sequence alignment as a whole procedure is still computationally expensive. In mapping stage of alignment, short reads are mapped to the candidate locations on the reference genome sequence in accordance with their difference from the reference segment with the least possible error. In this sense, comparison of reads and reference segments requires approximate string matching techniques which traditionally inherit dynamic programming algorithms (i.e., Smith-Waterman). Performing dynamic programming for each of the read and reference segment pair makes mapping, a computationally-costly stage for alignment process. So, accelerating this stage is expected to improve alignment performance in terms execution time. Here, we propose a fast pre-alignment filter to be performed before the mapping stage to get rid of the reads which exceed a predefined error threshold against reference segments. By filtering out the unnecessary reads, the computational load on the dynamic programming in mapping stage is reduced. We choose GateKeeper (Alser, et al., 2017) as the filtration algorithm since it maintains high accuracy of more than 96% and we implement on a GPU platform with CUDA framework to obtain benefit from performing compute-intensive work with highly parallel and independent millions of threads for boosting performance.
DATE: 22 October, 2018, Monday, CS590 presentations begin at @ 15:40
PLACE: EA-409