Configurable hardware based genome aligner

Next Generation Sequencing (NGS) machines produce enormous amount of data via massively parallelizing DNA sequencing. In bioinformatics, processing and storage of millions of short read data produced is one of the main problems. Hardware platforms, especially Field Programmable Gate Arrays (FPGA), are useful tools to overcome this computational burden. Within bioinformatics, alignment of short DNA read sequencing data to a reference genome sequence has become a standard step in the analysis pipeline for short DNA read sequence data. This is the costliest part of data analysis in terms of computation. Fundamentally, the problem is matching similar parts of two strings which are generally solved by Smith-Waterman (SW) algorithm which is a dynamic programming algorithm. SW algorithm is suitable to run efficiently on FPGA platforms. Besides, an FPGA platform can be used with a PC in a hybrid manner to form a complete system for analyzing and storing the NGS data. In this dissertation, we propose such a hybrid sequence alignment system to obtain the best alignment for short reads. The algorithm, design, and results of this dissertation describe the implementation, as well as improvements in mapping sensitivity and accuracy. The proposed system aligns NGS short reads to reference genome utilizing Phred Quality scores to obtain better mapping accuracy. This scheme results in mapping the reads to the locations that they fit best. This way, the proposed system approximates the optimum solution that can be obtained by dynamic programming. PC side of the system compresses read sequences along with the alignment results. We compare our system with other software and FPGA based systems in terms of sensitivity and accuracy. Based on the experiments, our proposed system provides increased sensitivity and accuracy.