Tez No |
İndirme |
Tez Künye |
Durumu |
576081
|
|
Accelerating the understanding of life's code through better algorithms and hardware design / Yaşamın kodunu anlamayı daha iyi algoritmalar ve donanım tasarımlarıyla hızlandırmak
Yazar:MOHAMMED H. K. ALSER MOHAMMED H. K. ALSER
Danışman: Assist. Prof. Dr. CAN ALKAN ; Prof. Dr. ONUR MUTLU
Yer Bilgisi: İhsan Doğramacı Bilkent Üniversitesi / Mühendislik ve Fen Bilimleri Enstitüsü / Bilgisayar Mühendisliği Ana Bilim Dalı
Konu:Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control
Dizin:
|
Onaylandı
Doktora
İngilizce
2018
160 s.
|
|
G¨un¨um¨uzde insan genomları konusundaki anlayı¸sımız, modern bili¸sim teknolojisinin
bir bireyin t¨um genomunu hızlı ve do˘gru bir ¸sekilde belirleyebilme
yetene˘ginden etkilenmektedir. Ge¸cti˘gimiz on yıl boyunca, y¨uksek verimli dizileme
(HTS) teknolojileri, zaman ve maliyette ¨onemli bir azalma ile birlikte, tek
bir ¸calı¸smada y¨uz milyonlardan milyarlarcaya kadar DNA par¸cası ¨uretme kabiliyeti
sayesinde dikkat ¸cekici biyomedikal ke¸siflere kapı a¸cmı¸stır. Ancak,
bu dizileme verisi bollu˘gu mevcut algoritmaların ve donanımların i¸slem kapasitelerinin
sınırlarını zorlamaya devam etmektedir. Bir hastanın genomunu analiz
etmek i¸cin, "okuma" adı verilen bu par¸caların her biri referans genomundaki aday
b¨olgelerle olan benzerliklerine bakılarak, referans genomu ¨uzerine yerle¸stirilir.
Yakla¸sık karakter dizgisi e¸sle¸stirme problemi ¸seklinde form¨ule edilen ve hizalama
olarak adlandırılan benzerlik hesaplaması, i¸slemsel bir darbo˘gazdır ¸c¨unk¨u: (1)
ikinci dereceden devingen programlama algoritmaları kullanılarak hesaplanır ve
(2) referans genomundaki aday b¨olgelerin b¨uy¨uk bir b¨ol¨um¨u ile verilen okuma
par¸cası birbirlerinden y¨uksek d¨uzeyde farklılık g¨osterdiklerinden dolayı hizalanamaz.
Bu ¸sekilde yanlı¸s belirlenen aday b¨olgelerin hizalanabilirli˘gin hesaplanması,
g¨un¨um¨uzdeki okuma haritalandırıcı algoritmaların ¸calı¸sma s¨urelerinin
b¨uy¨uk b¨ol¨um¨un¨u olu¸sturmaktadır. Bu nedenle, hesaplama olarak maliyetli bu
hizalama algoritmalarını ¸calı¸stırmadan ¨once, do˘gru olmayan aday b¨olgeleri tespit
edebilen ve bu b¨olgeleri aday b¨olge olmaktan ¸cıkaran, hızlı ve etkili bir filtre
geli¸stirmek ¸cok ¨onemlidir.
Bu tezde, ¨on hizalama a¸saması olarak i¸slev g¨oren ve yanlı¸s aday konumlarının
¸co˘gunu filtrelemeyi hedefleyen d¨ort yeni algoritma sunuyoruz. Algoritmalarımızı
GateKeeper, SLIDER, MAGNET ve SneakySnake olarak adlandırıyoruz.
Onerilen ¨on hizalama filtrelerinin ilk temel fikri, iki dizi arasında payla¸sılan ¨
t¨um benzer segmentleri do˘gru bir ¸sekilde tespit ederek y¨uksek filtreleme
do˘grulu˘gu sa˘glamaktır. ˙Ikinci temel fikir, ¨onerilen d¨ort filtreleme algoritmamızın
hızlandırılması i¸cin modern FPGA'ların ¸cok b¨uy¨uk ¨ol¸cekte paralel mimarisini
kullanmaktır. SneakySnake'i esas olarak biyoinformatisyenlerin mevcut olan, donanım
karma¸sıklı˘gı ile u˘gra¸smak zorunda olmadıkları emtia masa¨ust¨u ve sunucularında
kullanabilmeleri i¸cin geli¸stirdik. On okuma filtreleme yakla¸sımımızın ¨
avantaj ve dezavantajlarını 12 ger¸cek veri setini, farklı okuma uzunlukları ve
mesafe e¸sikleri kullanarak ayrıntılı olarak de˘gerlendirdik. De˘gerlendirmemizde,
donanım ¨on hizalama filtrelerimizin e¸sde˘ger CPU uygulamalarına g¨ore iki ila
¨u¸c derece hızlı olduklarını g¨osteriyoruz. Donanım ¨on hizalama filtrelerimizi
son teknoloji okuma hizalayıcılarıyla entegre etmenin hizalayıcının ¸calı¸sma
s¨uresini d¨uzenleme mesafesi e¸si˘gine ba˘glı olarak 21.5x. Son olarak, ¨on hizalama
filtrelerinin etkin CPU uygulamasının hala ¨onemli faydalar sa˘gladı˘gını
g¨osteriyoruz. SneakySnake'in en iyi performansa sahip CPU tabanlı okuma
ayarlayıcıları Edlib ve Parasail'in y¨ur¨utme s¨urelerini sırasıyla 43x ve 57,9x'e
kadar azalttı˘gını g¨osteriyoruz. Bu tezin ana sonucu, hızlı ve verimli bir filtreleme
mekanizması geli¸stirilmesi ve bu mekanizmanın do˘grulu˘gunun daha iyi
anla¸sılması, hizalayıcıların yeteneklerinden hi¸cbir ¸sey ¨od¨un vermeden, okuma
hizalamasının ¸calı¸sma s¨uresinde ¨onemli bir azalmaya yol a¸cmaktadır. Yeni mimarilerimizin
ve algoritmalarımızın, mevcut ve gelecekteki genom analiz planlarında
benimsenmelerini katalize etti˘gimizi umuyor ve buna inanıyoruz.
|
|
Our understanding of human genomes today is affected by the ability of modern
computing technology to quickly and accurately determine an individual's entire
genome. Over the past decade, high throughput sequencing (HTS) technologies
have opened the door to remarkable biomedical discoveries through its ability to
generate hundreds of millions to billions of DNA segments per run along with a
substantial reduction in time and cost. However, this flood of sequencing data
continues to overwhelm the processing capacity of existing algorithms and hardware.
To analyze a patient's genome, each of these segments - called reads - must
be mapped to a reference genome based on the similarity between a read and
"candidate" locations in that reference genome. The similarity measurement,
called alignment, formulated as an approximate string matching problem, is the
computational bottleneck because: (1) it is implemented using quadratic-time
dynamic programming algorithms, and (2) the majority of candidate locations
in the reference genome do not align with a given read due to high dissimilarity.
Calculating the alignment of such incorrect candidate locations consumes an
overwhelming majority of a modern read mapper's execution time. Therefore, it
is crucial to develop a fast and effective filter that can detect incorrect candidate
locations and eliminate them before invoking computationally costly alignment
algorithms.
In this thesis, we introduce four new algorithms that function as a prealignment
step and aim to filter out most incorrect candidate locations. We
call our algorithms GateKeeper, Slider, MAGNET, and SneakySnake. The first
key idea of our proposed pre-alignment filters is to provide high filtering accuracy
by correctly detecting all similar segments shared between two sequences.
The second key idea is to exploit the massively parallel architecture of modern
FPGAs for accelerating our four proposed filtering algorithms. We also develop
an efficient CPU implementation of the SneakySnake algorithm for commodity
desktops and servers, which are largely available to bioinformaticians without the
hassle of handling hardware complexity. We evaluate the benefits and downsides
of our pre-alignment filtering approach in detail using 12 real datasets across different
read length and edit distance thresholds. In our evaluation, we demonstrate
that our hardware pre-alignment filters show two to three orders of magnitude
speedup over their equivalent CPU implementations. We also demonstrate that
integrating our hardware pre-alignment filters with the state-of-the-art read aligners
reduces the aligner's execution time by up to 21.5x. Finally, we show that
efficient CPU implementation of pre-alignment filtering still provides significant
benefits. We show that SneakySnake on average reduces the execution time of
the best performing CPU-based read aligners Edlib and Parasail, by up to 43x
and 57.9x, respectively. The key conclusion of this thesis is that developing a fast
and efficient filtering heuristic, and developing a better understanding of its accuracy
together leads to significant reduction in read alignment's execution time,
without sacrificing any of the aligner' capabilities. We hope and believe that our
new architectures and algorithms catalyze their adoption in existing and future
genome analysis pipelines. |