hrvatski

SWIG - Poravnanje struktura korištenjem iterativne primjene Smith-Waterman algoritma

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.

Smith-Waterman; CUDA; simulirano kaljenje; bioinformatika; paralelizacija; poravnanje struktura

nije evidentirano