Configurable hardware based genome aligner

Abstract

Yeni nesil dizileme platformları(NGS), DNA dizilimini ile düzeyde parallelleştirerek muazzzam miktarda genetik veri ortaya çıkarır. Bu büyüklükte verinin işlenmesi ve depolanması biyoinformatik alanındaki önemli problemlerdendir. Donanım tabanlı çözümler; özellikle de yeniden yapılandırılabilir esnek özellikleri ile Alanda Programlanabilir Kapı Dizileri (FPGA) bu işlemsel yoğunluğun üstesinden gelme konusunda faydalı yapılardır. Biyoinformatik veri analizi zincirinde, NGS çıktıları olan kısa okumaların referans genoma hizalanmaları standart bir basamağı oluşturur ve işlem yükü olarak en ağır basamaktır. Temel olarak problem, aynı alfabeden iki dizinin benzer kısımlarini eşleştirme problemidir. Problemin çözümünde tercih edilen yöntem de esasında bir dinamik proglamlama yaklaşımı olan Smith-Waterman (SW) algoritmasidır. SW algoritması FPGAler üzerinde efektif olarak gerçeklenebilir ve paralellenebilir bir algoritmadır. Bununla beraber FPGA tabanli platformlar, PC'ler ile hibrit olarak çalıstırılarak, NGS datasının analizine ve depolanmasına yönelik bir sistem meydana getirilebilir. Bu çalışmada, kısa genomik dizileri olaslı en doğru pozisyona hizalayabilen hibrit bir sistem önerilmiş ve gerçeklenmiştir. Tezde gerçeklenen sistemin tasarımı, algoritması ve sonuçları, gerçeklenmesini ve bunun yanında hassasiyet ve hizalama doğruluğunda, nihai olarak da hizalama kalitesinde elde edilen gelişmeyi tanımlar. Önerilen sistem hizalama kalitesini arttırmak amacı ile hizalama algoritmasında, Phred kalite skorlarını da kullanmaktadır. Bu yaklaşımla beraber referans dizisinin tamamına hizalama yapılarak, diziler en doğru pozisyona hizalanmaktadır. Hizalanan dizi verisi, sistemin PC tarafında hizalama sonuc¸ları ile etkiles¸imli olarak sıkıs¸tırılarak saklanır. Sistemin performansı yaygın kullanılan yazılım tabanlı hizalayıcılar ve FPGA tabanlı metodlar ile karşılaştırılmış ve denemelerin sonucunda daha yüksek hizalama kalitesi ortaya koyduğu gösterilmiştir.

Next Generation Sequencing (NGS) machines produce enormous amount of data viamassively parallelizing DNA sequencing. In bioinformatics, processing and storage ofmillions of short read data produced is one of the main problems. Hardware platforms,especially Field Programmable Gate Arrays (FPGA), are useful tools to overcome thiscomputational burden. Within bioinformatics, alignment of short DNA read sequencing datato 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 platformcan be used with a PC in a hybrid manner to form a complete system for analyzing andstoring the NGS data. In this dissertation, we propose such a hybrid sequence alignmentsystem 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.