Read mapping methods optimized for multiple gpgpus

DNA dizi hizalama problemi, kısaca, bir ya da birden fazla örnekten alınan DNA dizilerinin aynı veya benzer türe ait referans genomunu içeren veri tabanı ile karakter seviyesinde karşılaştırılması olarak tanımlanabilir. Yüksek kapasiteli dizileme (YKD) teknolojileri ilk olarak 2006 yılında kullanılmaya başlanmıştır. Bugün, YKD teknolojileri insan genomunun sadece 3 gün içerisinde yaklaşık 1.000$ maliyetle okunmasına imkan sağlamaktadır. Hızlı bir şekilde gelişmeye devam etmekte olan bu teknoloji ile birlikte çok büyük miktarda okuma ile karşılaşmak mümkün olmaktadır. YKD verilerinin analizi bir milyardan fazla kısa parçanın (100 karakter veya baz çifti) oldukça uzun olan (yaklaşık 3 milyar baz çifti) referans genomu ile karşılaştırılmasını gerektirdiğinden, yüksek mikltarda hesaplamaya dayalı bir problem olarak sunulabilir. DNA molekülü çift sarmal bir yapıda olduğundan, gereken kıyaslama sayısı iki katına çıkmaktadır. Bu nedenle yürütme zamanı ve bu büyüklükteki kısa parçaların referans ile karşılaştırılması zor ve önemli bir problemdir. O(n2) zamanda milyarlarca kısa parçanın uzun parçalara lokal hizalanma için geliştirilmiş algoritmaları kullanmak yerine, süreci hızlandıran keşifsel yaklaşımlar uygulanmaktadır. İlk olarak Burrows Wheeler Transform (BWT) ile sıkıştırılmış referansı ardından Ferragina-Manzini yöntemi ile endeksleyerek ya da daha basit komut tablosu kullanarak kısmi dizi eşleşmeleri hızlıca bulunabilir. Ardından, bulunan aday lokasyanlar Levenshtein uzaklığını hesaplayan ve karesel zaman gerektiren dinamik programlama algoritması ile doğrulanır. Bu yaklaşımlar lokal hizalama algoritmalarının doğrudan uygulanmasından oldukça daha hızlı olmasına rağmen, insan genomunun tekrarlı yapısından dolayı, her bir okuma için ağır hesaplama yüküne yol açan yüzlerce doğrulama gerektirmektedir. Ancak, bu milyarlarca hizalamanın her biri birbirinden bağımsız olduğundan okuma yerleştirme problemi paralelleştirilebilir bir yapıya sahiptir. Bu tez çalışmasında, sadece merkezi işlem birimi kullanan algoritma kapasitesinin üzerinde güce sahip, dizi hizalama prosedürünü hızlandırmak için optimize edilmiş, birden fazla sayıda grafik işlem birimleri kullanabilen yeni bir algoritma sunuyoruz. Okuma yerleştirme iş gücünü çoklu grafik işlem birimlerinin paralel mimarisi parçalarına dağıtarak, milyonlarca hizalamayı aynı anda gerçekleştiriyoruz. Yöntemimiz hem çok çekirdekli merkezi işlem birimlerini hem de bir ya da birden fazla çoklu grafik işlem birimleri kullanabilmektedir. Bu çalışmada amacımız büyük ölçekli hesaplama altyapılarına veya bulut platformlarına duyulan ihtiyacı azaltma hedefi doğrultusunda gelişmiş GPGPU cihazları ile tek bir sunucunun yapabileceği şekle dönüştürmektir