Implementacija Smith Waterman algoritma koristeći grafičke kartice s CUDA arhitekturom (CROSBI ID 368243)
Ocjenski rad | sveučilišni preddiplomski završni rad
Podaci o odgovornosti
Korpar, Matija
Šikić, Mile
hrvatski
Implementacija Smith Waterman algoritma koristeći grafičke kartice s CUDA arhitekturom
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)).
Smith-Waterman ; CUDA ; paralelizacija ; bioinformatika ; poravnavanje sljedova
nije evidentirano
engleski
Smith-Waterman algorithm implementation using graphic cards with CUDA architecture
nije evidentirano
Smith-Waterman algorithm implementation using graphic cards with CUDA architecture
nije evidentirano
Podaci o izdanju
31
29.06.2011.
obranjeno
Podaci o ustanovi koja je dodijelila akademski stupanj
Fakultet elektrotehnike i računarstva
Zagreb