Sequence-to-graph alignment on a processing-in-memory system
Bellek-içi-işlem sistemi üzerinde dizi-çizge hizalaması
- Tez No: 972928
- Danışmanlar: 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: 2025
- 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ı: Belirtilmemiş.
Özet
Genom çizgeleri, tek bir birey yerine bir popülasyonun genetik bilgisini ve varyasyonlarını temsil etmek amacıyla kullanılmaktadır. Dizi-çizge hizalama (Sequence-to-Graph Alignment, SGA) problemi ise, bir sorgu dizisinin bir genom çizgesi üzerinde en uygun eşleşmesinin bulunması olarak tanımlanır. Ancak çizge temsillerinin düzensiz yapısı, SGA algoritmalarını bellek darboğazına duyarlı hale getirmekte ve yapılan karşılaştırmalara göre bazı uygulamalarda %50'nin üzerinde bellek bağımlılığı gözlemlenmektedir. Bu nedenle, SGA probleminin bellek-içi-işlem (Processing-in-Memory, PIM) teknolojilerinden fayda görmesi beklenmektedir. PIM mimarisi, verilerin CPU'ya aktarılması için bellek veri yolunun kullanılmasındansa, hesaplamaların ana belleğe yakın konumda yapılmasına olanak tanıyan, von Neumann dışı güncel bir mimaridir. UPMEM tarafından geliştirilen mevcut bir PIM çözümü, her biri bellek içinde çok daha hızlı ve verimli çalışabilen binlerce DPU'dan (DRAM Processing Unit) oluşmaktadır. Katkımız olan SEGAPIM, genom çizgesinin DPU'lar arasında dağıtılması, kısa tipte sorguların tohum konumlarına göre ilgili DPU'lara yönlendirilmesi ve dizi-çizge hizalama işleminin DPU'lar içerisinde gerçekleştirilmesini içeren bir program tasarımıdır. Tüm bunlar tasarıma dahil olmalarına rağmen hayata geçirdiğimiz uygulamanın asıl odağı, sınırlı bellek koşullarına uygun biçimde her sorgunun her tohumunun çizge dalga cephesi hizalama algoritması (Graph Wavefront Alignment, GWFA) kullanılarak hizalama puanlarının hesaplanması ve elde edilen sonuçların ana CPU'da birleştirilmesidir. Önerilen yaklaşımın doğruluk ve çalışma süresi açısından vg ve GraphAligner gibi güncel araçlarla karşılaştırmaları sunulmakta; mevcut PIM mimarisinin SGA problemi için umut verici bir hızlanma ve enerji tasarrufu sağladığı sonucuna ulaşılmaktadır.
Özet (Çeviri)
Genome graphs are used to represent the genetic information and variation of a population rather than a single individual. The sequence-to-graph alignment (SGA) problem can be defined as finding the best match between a query sequence and a genome graph. SGA algorithms are expected to suffer from a memory bottleneck due to the irregularity of graph representation, and benchmarks confirm more than 50% memory boundness found in some applications. Therefore, the SGA alignment problem can benefit from processing-in-memory (PIM) technologies. PIM is an upcoming non-von Neumann architecture that allows computing near the main memory without the need to utilize the memory bus for data transfers to the CPU and back. One of the currently available PIM technologies developed by UPMEM is an architecture consisting of thousands of DPUs (DRAM Processing Units) that allow for much faster and energy-efficient memory access. Our contribution includes SEGAPIM, the design of a pipeline that partitions and distributes a genome graph across DPUs, directs short reads to the relevant DPUs according to their seed locations, and performs alignment solutions within DPUs. Although these distribution and routing components are part of the envisioned full system, the implemented portion of our work focuses on calculating alignment scores for each seed of each read using an adaptation of the graph wavefront alignment algorithm (GWFA) under very limited memory, followed by collecting and finalizing the results on the host CPU. We present comparisons for accuracy and run-time of our implementation to state-of-the-art tools such as vg and GraphAligner, and conclude that the PIM architecture at hand provides a promising speed-up and energy-saving for the SGA problem.
Benzer Tezler
- Multi-object tracking by associations on temporal window
Geçici pencerede çağrışımlara dayalı çoklu nesne takibi
GÜLTEKİN GÜNDÜZ
Yüksek Lisans
İngilizce
2018
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolGalatasaray ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. TANKUT ACARMAN
- Programlanabilir lojik kontrolörler için tasarım yöntemleri
Başlık çevirisi yok
ERDAL ÖZKAN
Yüksek Lisans
Türkçe
1996
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiDOÇ.DR. SALMAN KURTULAN
- Madencilikte bilgisayar uygulamaları ve SURPAC 2000 yazılımı ile bir saha çalışması
Başlık çevirisi yok
TANER ERDOĞAN
Yüksek Lisans
Türkçe
1998
Maden Mühendisliği ve Madencilikİstanbul Teknik ÜniversitesiKazı Mekanizasyonu Bilim Dalı
YRD. DOÇ. DR. HASAN ERGİN
- 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
- Characterization of short tandem repeats using local assembly
Lokal DNA birleştirme metodu ile mikrosatellitlerin bulunması
GÜLFEM DEMİR
Yüksek Lisans
İngilizce
2017
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. CAN ALKAN