Bilkent University
Department of Computer Engineering
MS THESIS PRESENTATION
Thousands of Alignments For Resequencing Applications Using Graphics Processing Unit
Mustafa Korkmaz
MSc Student
Computer Engineering Department
Bilkent University
The high throughput sequencing (HTS) methods have already started to fundamentally revolutionize the area of genome research through low-cost and highthroughput genome sequencing. However, the sheer size of data imposes various computational challenges. For example, in the Illumina HiSeq2000, each run produces over 7-8 billion short reads and over 600 Gb of base pairs of sequence data within less than 10 days. For most applications, analysis of HTS data starts with read mapping, i.e. finding the locations of these short sequence reads in a reference genome assembly. The similarities between two sequences can be determined by computing their optimal local alignments using a dynamic programming method called the Needleman-Wunsch algorithm. The Needleman-Wunsch algorithm is widely used in hash-based DNA read mapping algorithms because of its high sensitivity. However, the quadratic time complexity of this algorithm makes it highly timeconsuming and the main bottleneck in analysis. In addition to this drawback, the short length of reads ( ~100 bp) and the large size of ammalian genomes (3.1 Gbp for human) worsens the situation by requiring several hundreds to tens of thousands of Needleman-Wunsch calculations per read. The fastest approach proposed so far avoids Needleman-Wunsch and maps the data described above in 70 CPU days with low sensitivity. More sensitive mapping approaches are even slower. We propose that efficient parallel implementations of string comparison will dramatically improve the running time of this process. With this motivation, we propose to develop enhanced algorithms to exploit the parallel architecture of GPUs.
Keywords: Semi-global alignment, Needleman-Wunsch algorithm, parallel computation, CUDA, GPGPU.
DATE: 05 November, 2012, Monday @ 14:30
PLACE: EA409