Geri Dön

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

  1. Tez No: 317907
  2. Yazar: MUSTAFA KORKMAZ
  3. Danışmanlar: PROF. DR. CEVDET AYKANAT, YRD. DOÇ. DR. CAN ALKAN
  4. Tez Türü: Yüksek Lisans
  5. Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2012
  8. Dil: İngilizce
  9. Üniversite: İhsan Doğramacı Bilkent Üniversitesi
  10. Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. 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

  1. 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

    İngilizce

    2022

    Moleküler TıpKoç Üniversitesi

    Moleküler Biyoloji ve Genetik Ana Bilim Dalı

    DR. ÖĞR. ÜYESİ GÖZDE KORKMAZ

    DOÇ. DR. NATHAN A. LACK

  2. Read mapping methods optimized for multiple gpgpus

    Çoklu gpgpu sistemleri için eniyilenmiş dizi hizalama yöntemleri

    AZITA NOURI

    Yüksek Lisans

    İngilizce

    İngilizce

    2016

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    YRD. DOÇ. DR. CAN ALKAN

  3. 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

  4. 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

    Türkçe

    1997

    İnşaat Mühendisliğiİstanbul Teknik Üniversitesi

    Ulaştırma Ana Bilim Dalı

    PROF. DR. HALUK GERÇEK

  5. 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

    İngilizce

    2020

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent Üniversitesi

    Mühendislik Bilimleri Ana Bilim Dalı

    YRD. DOÇ. CAN ALKAN