Bilkent University
Department of Computer Engineering


Stream-Processing Framework for Graph-based Sequence Alignment


Alim Şükrücan Gökkaya
MS Student
Computer Engineering Department
Bilkent University

High-throughput sequencing (HTS) technologies are advancing to produce vast amounts of data in decreasing amount of time and price. This trend pushes the time requirements to the limits in terms of the time it takes from preparation of genetic samples until computation of read mapping to the reference sequences. We propose a streaming framework to accelerate the alignment to a population-genome reference, in real-time, as the reads are being emitted by the HTS equipment. A widely used approach is the seed-and-extend heuristics which is used by many existing aligners due to optimal alignment algorithm with dynamic programming has quadratic time complexity. We propose a distributed stream processing architecture to efficiently run the sequence alignment pipeline. Furthermore, we investigate a novel graph-based seed indexing method to improve mapping performance and quality.


DATE: 05 November, 2018, Monday, CS590 presentations begin at @ 15:40