Naslov
Implementacija Smith Waterman algoritma koristeći grafičke kartice s CUDA arhitekturom
(Smith-Waterman algorithm implementation using graphic cards with CUDA architecture)

Autori
Korpar, Matija

Vrsta, podvrsta i kategorija rada
Ocjenski radovi, diplomski rad, preddiplomski

Fakultet
Fakultet elektrotehnike i računarstva

Mjesto
Zagreb

Datum
29.06

Godina
2011

Stranica
31

Mentor
Šikić, Mile

Ključne riječi
Smith-Waterman ; CUDA ; paralelizacija ; bioinformatika ; poravnavanje sljedova
(Smith-Waterman algorithm implementation using graphic cards with CUDA architecture)

Sažetak
Smith-Waterman, deterministički algoritam ocjenjivanja sličnosti i poravnavanja sljedova, jedan od najvažnijih algoritama bionformatike, zbog svoje velike složenosti O(nm) često je zamjenjivan puno bržim heurističkim algoritmom BLAST. CUDA (Compute Unified Device Architecture), tehnologija paralelizacije posla na grafičkim karticama, omogućila je ponovni povrat Smith- Watermanu. U ovom radu predstavljena je jedna od mogućih implementacija Smith-Watermanova algoritma na tehnologiji CUDA. Dobiveno ubrzanje raste eksponencijalno s porastom veličine sljedova, od 10 puta pri većim proteinima, do 400 puta na manjim sljedovima DNK- a. Problem odabira parametara CUDA tehnologije riješen je primjenom genetskog algoritma čiji su rezultati uzrokovali daljnje ubrzanje algoritma za 15-20%. Uporabom Hirschbergova algoritma memorijska složenost algoritma spuštena je s O(nm) na O(min(m, n)).

Izvorni jezik
Hrvatski

Znanstvena područja
Informacijske i komunikacijske znanosti

POVEZANOST RADA