Naslov
SWIG - Poravnanje struktura korištenjem iterativne primjene Smith-Waterman algoritma
(SWIG - Aligning structures using iterative application of Smith-Waterman algorithm)

Autori
Rahle, Bruno

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

Fakultet
Fakultet elektrotehnike i računarstva

Mjesto
Zagreb

Datum
29.06

Godina
2012

Stranica
38

Mentor
Šikić, Mile

Ključne riječi
Smith-Waterman; CUDA; simulirano kaljenje; bioinformatika; paralelizacija; poravnanje struktura
(Smith-Waterman; CUDA; simulated annealing; bioinformatics; parallelization; aligning structures)

Sažetak
Algoritam dinamičkog programiranja Smith-Waterman služi nam da deterministički pronađemo lokalno poravnanje neka dva proteina. Možemo ga prilagoditi da, umjesto supstitucijske matrice, kao sredstvo ocjene koristi fizičke udaljenosti između dvije molekule proteina u prostu. Metoda simuliranog kaljenja omogućava nam da pronađemo lokalni maksimum neke funkcije. Ako kao funkciju energije koristimo algoritam Smith-Waterman, a za pronalazak susjeda rotiramo i translatiramo drugi protein, možemo provjeriti koliko su dva proteina fizički slična bez obzira na njihovu početnu poziciju. Implementacijom tih algoritama na grafičkim karticama koristeći CUDA tehnologiju, možemo dobiti nekoliko redova veličine brži kod, pogotovo kod većih proteina. Kod manjih proteina, efekt je nažalost obratan i dobivamo sporiji kod jer je konstanta skrivena u O notaciji relativno velika.

Izvorni jezik
Hrvatski

POVEZANOST RADA