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