Massively parallel mapping of next generation sequence reads using GPU

Yüksek çıktılı dizileme (YÇD) yöntemleri, düşük maliyeti ve yüksek çıktı vermesiyle, daha şimdiden genom araştırmaları alanında temelden bir devrim gerçekleştirdi. Ancak, elde edilen verinin büyük olması, çeşitli hesaplama tabanlı sorunları da beraberinde getirdi. Örneğin, Illumina HiSeq2000 modelinde, her bir çalışma sonrası, 7-8 milyardan fazla küçük DNA bölütü ve 600 Gb dan fazla baz çifti 10 gün içinde elde edilebilmektedşr. Birçok uygulama için, YÇD verilerinin çözümlenmesi küçük DNA bölütlerinin eşlenmesiyle başlar. Örneğin, küçük DNA parçalarının kaynak DNA'daki yerlerinin tespit edilmesi gibi.İki dizinin arasındaki benzerlik, en uygun genel hizalamalarının Needleman-Wunsch algoritması yarımıyla hesaplanmasıyla bulunur. Needleman-Wunsch algoritması yüksek duyarlılığı sebebiyle, karma tablo tabanlı küçük DNA bölütlerinin eşlenmesi algoritmalarında kullanılır. Ancak bu algoritmanın ikilenik karmaşıklıktaki yapısı, fazla zaman harcamasına ve analizlerde darboğaz oluşturmasına sebep olur. Bu engelin yanında DNA bölütlerinin küçüklüğü (yaklaşık 100 baz çifti) ve memeli genomlarının büyüklüğü (3.1 Giga baz çifti), her bir küçük DNA bölütü için yüzlerce ila onbinlerce arası hesaplama yapılmasını gerektirerek, durmu daha da kötü hale getirmektedir. Needleman-Wunsch algoritmasını kullanmadan çalışan ve yukarıdaki veriyi kullanan en hızlı uygulama 70 MİB gününde, az duyarlılıkta çalışmaktadır. Daha duyarlı olan yaklaşımlar ise daha da yavaş çalışmaktadır. Bu tezde, etkili bir paralel dizi karşılaştırma yapısı geliştirirek, bu uygulamanın başarımını ciddi seviyelerde arttırıldığını önerdik. Bu güdülenmeyle yola çıkarak, grafik işlem birimlerinin paralel mimarisinin kullanan gelişmiş bir yaklaşım ortaya koyduk.