Pri implementaciji vzporednega algoritma nismo uporabili obstojeˇce cenilke iz orodja CmDock, ampak cenilko na osnovi odsekoma linearnega potenciala (PLP) [25]. Cenilko smo izbrali, ker je enostavna in dovolj dobra za zaˇcetno verzijo algoritma. Cenilka PLP je sestavljena iz ˇstirih ˇclenov (2.1):
fP LP =fplp+fclash+ftors+csite. (2.1) Prvi ˇclen (fplp) opisuje interakcije med atomom liganda in atomom recep-torja. Odvisen je od razdalje med atomoma in tipom interakcije. Izraˇcunati jo je potrebno za vsak par ligand-receptor atomov. Definiranih je 5 tipov atomov: donator, prejemnik, donator/prejemnik, nepolarni vodik in kovina.
Glede na tip atomov imamo 5 razliˇcnih interakcij med dvema atomoma (vo-dikova in kovinska vez ter globoka, nepolarna in odbojna interakcija). Ima dve razliˇcni formuli glede na vrsto interakcije. Odbojna interakcija ima svojo formulo (2.2), vse ostale interakcije pa svojo (2.3). Poleg razliˇcnih uteˇzi, ki se nahajajo v tabeli 3 v [25], so v formuli tudi optimizacijski parametri. Upo-rabljeni so bili optimizacijski parametri M5 modela, ki se nahajajo v tabeli 7 v [25]. Vrednost celotnega ˇclena je vsota prispevkov vsakega para.
rep(r, A, B, C, D) =
Diplomska naloga 9
Drugi ˇclen (fclash) opisuje interakcije med pari atomov liganda, med ka-terima so vsaj tri vezi. Odvisen je od razdalje med atomoma in vrsto inte-rakcije. Vsak atom liganda je klasificiran v enega izmed treh tipov. Glede na tip atomov v paru se doloˇcijo tri razliˇcne vrste interakcij, vsaki pripadata dve razdalji. Predpisana razdalja (rclash) je odvisna od ˇstevila vezi med ato-moma. ˇCe so med atomoma natanˇcno tri vezi, se uporabi prva razdalja, ˇce jih je veˇc, pa druga razdalja. ˇCe je dejanska razdalja med atomoma (r) veˇcja od predpisane razdalje rclash, potem pribitka pri oceni ni, ˇce pa je manjˇsa, se pribitek para izraˇcuna po formuli (2.4). Vrednost celotnega ˇclena je vsota prispevkov vsakega para.
clashpar(r) = 50∗ (r2clash−r2)
rclash2 (2.4)
Tretji ˇclen (ftors) opisuje torzijski potencial, ki se ga izraˇcuna za vse ro-tacijske vezi v ligandu. Uporabili smo implementacijo torzijskega potenciala, doloˇceno vtripos force field [10]. Vsaki rotacijski vezi se doloˇcita parametrak ins glede na tipe atomov, ki sestavljajo vez. ˇCe posamezna kombinacija tipov atomov ni doloˇcena, se parametroma nastavi privzeto vrednost. Parametra se nato uporabita skupaj s trenutnim kotom vezi za izraˇcun torzijskega po-tenciala po formuli (2.5). Vrednost celotnega ˇclena je vsota prispevkov vsake vezi.
torsvez(k, s, kot) =k∗(1 +s/|s| ∗cos(|s| ∗kot)) (2.5) Cetrti ˇˇ clen (csite) izloˇci primere, ki so izven vezavnega mesta. Doloˇci
10 Tine Erent vezavno mesto. Preveri se vse teˇzke atome liganda, tj. atome, ki niso vodiki, ˇce so znotraj tega mesta. ˇCe je atom izven, se doda konstantni pribitek 50 celotni oceni osebka.
Poglavje 3
Pregled programa CmDock
V nadaljevanju bomo predstavili programsko opremo za sidranje molekul na CPE, ki je sluˇzila kot izhodiˇsˇce za vzporedni algoritem.
CmDock temelji na programu RxDock, ki sam temelji na programu rDock.
Izdan je kot odprtokodni program (angl. open source) in se uporablja za si-muliranje sidranja ligandov na proteine in nukleinske kisline. V primerjavi z RxDock in rDock razliˇcicama prinaˇsa CmDock kolekcijo optimizacij, upo-rabniˇskih izboljˇsav in poveˇcanje vzporednosti izvajanja [21].
Program rDock je napisan v jeziku C++ in se prevede na operacijskem sistemu Linux s prevajalnikom GNU g++ [43].
Platforma rDock vsebuje skupino ukazno-vrstiˇcnih orodij, namenjenih vi-soko zmogljivostnemu sidranju (angl. docking) in presejanju (angl. screening). Program je bil skupaj z metodami razvit in validiran v letih 1998 -2002 v podjetju RiboTargets (sedanji Vernalis) za lastno uporabo [42].
Nekaj glavnih komponent platforme so hitre cenilke, validirane na prote-inih in ribonukleinsko kislinskih tarˇcah ter stohastiˇcni iskalni algoritem, ki temelji na GA in genetskem filtriranju po sidranju [43].
Glavna tehnika je uporaba GA s tronivojsko energijsko minimizacijo, ki ji sledi vrednotenje elektrostatiˇcne energije [28]. Med razliˇcnimi stopnjami GA se spreminjajo parametri cenilke, kar izboljˇsa konvergenco [42]. Ker so stopnje med seboj odvisne, se morajo izvesti zaporedoma. Sledi lokalna
12 Tine Erent optimizacija z uporabo metode Monte Carlo (MC) in principi linearnega programiranja [43].
Kromosomi GA so sestavljeni iz genov, ki kodirajo srediˇsˇce mase, ori-entacijo in kote dihedralnih vezi liganda (prikazano v tabeli 3.1). Srediˇsˇce mase in orientacija liganda so predstavljeni s ˇstevili v plavajoˇci vejici, ki se pri kriˇzanju in mutaciji obravnavajo neodvisno. Zaˇcetni populaciji se na zaˇcetku nastavijo nakljuˇcne vrednosti [42].
Element Vsebovana lastnost Dolˇzina
pozicija srediˇsˇce mase 3
orientacija Eulerjev kot glavnih osi 3 dihedral dihedralni kot za vrtljive vezi 1 za vsako vez Tabela 3.1: Povzetek tabele kromosomskih elementov [42]
Tekom izvajanja GA se izvede kriˇzanje in/ali mutacija na nakljuˇcnem kro-mosomu. Velikost mutacije je doloˇcena s pravokotniˇsko distribucijo vnaprej doloˇcene ˇsirine. Generacija se zakljuˇci, ko se ˇstevilo novih osebkov izenaˇci s ˇstevilom zaˇcetne populacije. GA se izvaja, dokler populacija ne konvergira (ni veˇc nobenih izboljˇsav v generaciji) [43].
Poglavje 4
Vzporedni algoritem
Vzporedni algoritem vsebuje eno stopnjo GA, prilagojenega iz CmDock, in cenilko PLP. Implementiran je v ogrodju OpenCL in se izvaja na GPE. GA je stohastiˇcni proces in kot tak podvrˇzen nakljuˇcnim zaˇcetnim vrednostim in tudi nakjuˇcnemu spreminjanju kromosomov, zato se izvede veˇc neodvisnih zagonov celotne optimizacije. Vsi zagoni se izvajajo hkrati (veˇc populacij naenkrat), prav tako tudi posamezni osebki GA.
Pri implementaciji algoritma moramo za preslikavo kromosoma osebka na model liganda implementirati funkcijo za izraˇcun lastnih vrednosti in lastnih vektorjev simetriˇcne 3×3 matrike - uporabimo Koppovo reˇsitev [24]. Upora-bimo tudi lokalno redukcijo po Baileyevem zgledu [6]. Za urejanje osebkov potrebujemo urejevalni algoritem - implementiramo preprostega, ki na prvi stopnji izvede urejanje z mehurˇcki, nato urejanje z zlivanjem.
Vse vhodne podatke vzporednega algoritma izvozimo iz programa Cm-Dock. Izhod vzporednega programa so najboljˇse lege ligandov, shranjene v datoteki v standardnem formatu sdf.
4.1 OpenCL
Vzporedni algoritem, ki se izvaja na GPE, je implementiran s pomoˇcjo Open-CL, kar nam omogoˇci izvajanje na razliˇcnih GPE in tudi na veˇcprocesorskih
14 Tine Erent CPE.
OpenCL je odprti, brezplaˇcen standard za veˇcplatformno, vzporedno pro-gramiranje razliˇcnih pospeˇsevalnikov v superraˇcunalnikih, oblaˇcnih streˇ zni-kih, osebnih raˇcunalnikih, mobilnih napravah in vgradnih platformah [36].
Programiranje ˇsˇcepcev (angl. kernel), ki se izvajajo na pospeˇsevalnikih, izvedemo v programskem jeziku OpenCL C, ki temelji na standardu ISO C99, vendar z omejitvami. Programski vmesnik (angl. OpenCL API) skrbi za nadzor platform in izvajanje programov na pospeˇsevalnikih [38].
Sˇˇcepci se lahko izvajajo na veˇcjedrnih CPE, pospeˇsevalnikih GPE, FPGA in tensor [40], procesorjih digitalnih signalov in strojni opremi po naro-ˇcilu [36].
V ogrodju OpenCL imamo vedno enega gostitelja, na katerem se izvaja gostiteljski program in eno ali veˇc zgoraj naˇstetih naprav, ki so z njim pove-zane in na katerih se izvaja eden ali veˇc ˇsˇcepcev [38].
Gostitelj vstavlja ukaze v vrsto (izvedi ˇsˇcepec, kopiraj podatke na po-speˇsevalnik, kopiraj podatke na gostitelja itd.), ki se izvedejo zaporedno, tako tudi doseˇzemo sinhronizacijo. Medtem ko se ukazi v vrsti izvajajo, lahko CPE ˇcaka ali izvaja druge stvari.
Delo ˇsˇcepca je razdeljeno v delovne skupine (angl. work-group) in delavce (angl. work-item, t.i. nit). Globalna velikost (angl. global size) definira, ko-liko delavcev ˇzelimo pognati v celoti. Lokalna velikost (angl. local size) definira, koliko delavcev ˇzelimo pognati skupaj v eni delovni skupini. De-lavce znotraj ene delovne skupine, ki si delijo hiter lokalni pomnilnik, lahko sinhroniziramo s pomoˇcjo preprek. Optimalna lokalna velikost je odvisna od GPE in ˇsˇcepca. Skupno ˇstevilo delovnih skupin dobimo, ˇce globalno velikost delimo z lokalno velikostjo. Za laˇzje programiranje so velikosti razdeljene v eno, dve ali tri dimenzije. Vsak delavec ima po vseh dimenzijah svojo glo-balno in lokalno identifikacijsko ˇstevilko in identifikacijsko ˇstevilko delovne skupine, ki ji pripada (angl. global ID, local ID in group ID, pridobljene s klici funkcije v ˇsˇcepcu). Z identifikacijskimi ˇstevilkami jim dodelimo razliˇcne vloge in delo (npr. samo delavec z lokalnim ID=0 zapiˇse skupni rezultat
Diplomska naloga 15 izraˇcuna v globalno tabelo na mesto z indeksom ID-ja delovne skupine) [38, 18].
Pri implemetaciji vzporednega algoritma je potreben algoritem za gene-riranje nakljuˇcnih ˇstevil. Uporabljena knjiˇznica za OpenCL, ki je sposobna vzporedno generirati nakljuˇcna ˇstevila, je RandomCL [41]. RandomCL je zbirka 22 generatorjev pseudo-nakljuˇcnih ˇstevil, namenjenih za GPE. Knji-ˇznica generira nakljuˇcna ˇstevila nekajkrat hitreje od ostalih knjiˇznic [9].