Bilkent University
Department of Computer Engineering

---

MS THESIS PRESENTATION

 

GateKeeper-GPU: accelerated Pre-alignment Filtering in Short Read Mapping

 

Zülal Bingöl
MS Student
(Supervisor: Asst. Prof. Dr. Can Alkan)
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 dierence 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. Therefore 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 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: 24 August 2020, Monday @ 11:00