Read mapping methods optimized for multiple gpgpus
Çoklu gpgpu sistemleri için eniyilenmiş dizi hizalama yöntemleri
- Tez No: 436342
- Danışmanlar: YRD. DOÇ. DR. CAN ALKAN
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2016
- Dil: İngilizce
- Üniversite: İhsan Doğramacı Bilkent Üniversitesi
- Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 70
Özet
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
Özet (Çeviri)
DNA sequence alignment problem can be broadly de ned as the character-level comparison of DNA sequences obtained from one or more samples against a database of reference (i.e., consensus) genome sequence of the same or a similar species. High throughput sequencing (HTS) technologies were introduced in 2006, and the latest iterations of HTS technologies are able to read the genome of a human individual in just three days for a cost of $1,000. With HTS technologies we may encounter massive amount of reads available in di erent size and they also present a computational problem since the analysis of the HTS data requires the comparison of >1 billion short (100 characters, or base pairs) \reads“ against a very long (3 billion base pairs) reference genome. Since DNA molecules are composed of two opposing strands (i.e. two complementary strings), the number of required comparisons are doubled. It is therefore present a dicult and important challenge of mapping in terms of execution time and scalability with this volume of di erent-size short reads. Instead of calculating billions of local alignment of short vs long sequences using a quadratic-time algorithm, heuristics are applied to speed up the process. First, partial sequence matches, called \seeds”, are quickly found using either Burrows Wheeler Transform (BWT) followed with Ferragina-Manzini Index (FM), or a simple hash table. Next, the candidate locations are veri ed using a dynamic programming alignment algorithm that calculates Levenshtein edit distance (mismatches, insertions, deletions di erent from reference), which runs in quadratic time. Although these heuristics are substantially faster than local alignment, because of the repetitive nature of the human genome, they often require hundreds of veri cation runs per read, imposing a heavy computational burden. However, all of these billions of alignments are independent from each other, thus the read mapping problem presents itself as embarrassingly parallel. In this thesis we propose novel algorithms that are optimized for multiple graphic processing units (GPGPUs) to accelerate the read mapping procedure beyond the capabilities of algorithmic improvements that only use CPUs. We distribute the read mapping workload into the massively parallel architecture of GPGPUs to performing millions of alignments simultaneously, using single or many GPGPUs, together with multi-core CPUs. Our aim is to reduce the need for large scale clusters or cloud platforms to a single server with advanced parallel processing units
Benzer Tezler
- Sahada programlanabilir kapı dizileri ile lojik devre tasarımı ve VHDL kullanılarak bazı devrelerin gerçekleştirilmesi
Başlık çevirisi yok
ATEŞ BERNA
Yüksek Lisans
Türkçe
1998
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiElektronik ve Haberleşme Mühendisliği Ana Bilim Dalı
PROF. DR. AHMET DERVİŞOĞLU
- Distributed stream-processing framework for graph-based sequence alignment
Çizge tabanlı okuma hizalandırması için dağıtık akıntı işleme sistemi
ALİM ŞÜKRÜCAN GÖKKAYA
Yüksek Lisans
İngilizce
2020
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiMühendislik Bilimleri Ana Bilim Dalı
YRD. DOÇ. CAN ALKAN
- Massively parallel mapping of next generation sequence reads using GPU
Yeni nesil dizileme bölütlerinin grafik işleme birimi kullanılarak yoğun paralel eşlenmesi
MUSTAFA KORKMAZ
Yüksek Lisans
İngilizce
2012
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. CEVDET AYKANAT
YRD. DOÇ. DR. CAN ALKAN
- Mimari doku okumalarında sosyal ağ modeli (dosam): Gölyazı örneği
A social network model for architectural pattern analysis (sonemapa): The Gölyazi case
SELAY YURTKURAN TOK
- Large structural variation discovery using long reads with several degrees of error
Farklı hata oranlarına sahip uzun okumalar ile büyük yapısal varyasyon tespiti
EZGİ EBREN
Yüksek Lisans
İngilizce
2020
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ CAN ALKAN