Read mapping methods optimized for multiple gpgpus

Abstract

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

DNA sequence alignment problem can be broadly dened as the character-levelcomparison of DNA sequences obtained from one or more samples against adatabase of reference (i.e., consensus) genome sequence of the same or a similarspecies. High throughput sequencing (HTS) technologies were introduced in2006, and the latest iterations of HTS technologies are able to read the genomeof a human individual in just three days for a cost of $1,000. With HTS technologieswe may encounter massive amount of reads available in dierent size andthey also present a computational problem since the analysis of the HTS datarequires the comparison of >1 billion short (100 characters, or base pairs) /reads`against a very long (3 billion base pairs) reference genome. Since DNA moleculesare composed of two opposing strands (i.e. two complementary strings), the numberof required comparisons are doubled. It is therefore present a dicult andimportant challenge of mapping in terms of execution time and scalability withthis volume of dierent-size short reads.Instead of calculating billions of local alignment of short vs long sequencesusing a quadratic-time algorithm, heuristics are applied to speed up the process.First, partial sequence matches, called /seeds`, are quickly found usingeither Burrows Wheeler Transform (BWT) followed with Ferragina-Manzini Index(FM), or a simple hash table. Next, the candidate locations are veriedusing a dynamic programming alignment algorithm that calculates Levenshteinedit distance (mismatches, insertions, deletions dierent from reference), whichruns in quadratic time. Although these heuristics are substantially faster thanlocal alignment, because of the repetitive nature of the human genome, they oftenrequire hundreds of verication runs per read, imposing a heavy computationalburden. However, all of these billions of alignments are independent from eachother, thus the read mapping problem presents itself as embarrassingly parallel.In this thesis we propose novel algorithms that are optimized for multiplegraphic processing units (GPGPUs) to accelerate the read mapping procedurebeyond the capabilities of algorithmic improvements that only use CPUs. Wedistribute the read mapping workload into the massively parallel architecture ofGPGPUs to performing millions of alignments simultaneously, using single ormany GPGPUs, together with multi-core CPUs. Our aim is to reduce the needfor large scale clusters or cloud platforms to a single server with advanced parallelprocessing units