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
- Tez No: 317907
- Danışmanlar: PROF. DR. CEVDET AYKANAT, 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: 2012
- 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ı: 63
Özet
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.
Özet (Çeviri)
The high throughput sequencing (HTS) methods have already started to fundamentally revolutionize the area of genome research through low-cost and high-throughput genome sequencing. However, the sheer size of data imposes various computational challenges. For example, in the Illumina HiSeq2000, each run produces over 7-8 billion short reads and over 600 Gb of base pairs of sequence data within less than 10 days. For most applications, analysis of HTS data starts with read mapping, i.e. finding the locations of these short sequence reads in a reference genome assembly.The similarities between two sequences can be determined by computing their optimal global alignments using a dynamic programming method called the Needleman-Wunsch algorithm. The Needleman-Wunsch algorithm is widely used in hash-based DNA read mapping algorithms because of its guaranteed sensitivity. However, the quadratic time complexity of this algorithm makes it highly time-consuming and the main bottleneck in analysis. In addition to this drawback, the short length of reads ( ~100 base pairs) and the large size of mammalian genomes (3.1 Gbp for human) worsens the situation by requiring several hundreds to tens of thousands of Needleman-Wunsch calculations per read. The fastest approach proposed so far avoids Needleman-Wunsch and maps the data described above in 70 CPU days with lower sensitivity. More sensitive mapping approaches are even slower. We propose that efficient parallel implementations of string comparison will dramatically improve the running time of this process. With this motivation, we propose to develop enhanced algorithms to exploit the parallel architecture of GPUs.
Benzer Tezler
- Interrogation of the functionality of ERα binding sites with STARR-seq
Östrogen reseptör α bağlanma bölgelerinin STARR-seq ile sorgulanması
ELİF YAPICI
Yüksek Lisans
İngilizce
2022
Moleküler TıpKoç ÜniversitesiMoleküler Biyoloji ve Genetik Ana Bilim Dalı
DR. ÖĞR. ÜYESİ GÖZDE KORKMAZ
DOÇ. DR. NATHAN A. LACK
- Read mapping methods optimized for multiple gpgpus
Çoklu gpgpu sistemleri için eniyilenmiş dizi hizalama yöntemleri
AZITA NOURI
Yüksek Lisans
İngilizce
2016
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. CAN ALKAN
- Identification and control of nonlinear dynamical systems using neural networks
Doğrusal olmayan dinamik sistemlerin yapay sinir ağları ile tanınması ve denetimi
MEHMET ÖNDER EFE
Yüksek Lisans
İngilizce
1996
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolBoğaziçi ÜniversitesiPROF.DR. OKYAY KAYNAK
- Yapay sinir ağları ile ulaştırma taleplerinin modellenmesi
Başlık çevirisi yok
YUSUF KAAN DEMİR
Yüksek Lisans
Türkçe
1997
İnşaat Mühendisliğiİstanbul Teknik ÜniversitesiUlaştırma Ana Bilim Dalı
PROF. DR. HALUK GERÇEK
- 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