INFORMATICA 2/1980 KEM IJSKI IN FORMACI JSKI SISTEMI II ALGORITMI ZA OBRAVNAVO IN OBDELAVO KEMIJSKO-STRUKTURNIH INFORMACIJ UDK: 681.3 : 54 B. DŽ0N0VA-JERMAN-BLA2IC N.TRINAJSTlC* INSTITUT JOŽEF STEFAN, LJUBLJANA *INSTITUT RUDJER BOŠKOVIČ, ZAGREB Vsebina: V prispevku smo podali kratek pregled algorihnov zo obravnavo in obdelavo računalniško zapisanih kemijskihstruktur. Poskusili smo oceniti njihovo učinkovitost in uporabnost z ozirom na funkcije v okviru kemijsko-informacijskega sistema. CHEMICAL INFORMATION SYSTEMS II: ALGORITHMS FOR HANDLING AND PROCESSING CHEMICAL INFORMATIONS. Abstract: The paper discusse the computer-based algorithms that support the handling and processing of information about chemical substances. Some assesments are made about the efficiency and usefulness of the algorithms that performe interconversion, regi- stration, structure and substructure searching, according to the funcHons they reallze in the chemical information systems. 1 . UVOD Vsak informacijski sistem definirajo štiri funkcional- ne enote( 1 ): - zbiranje in shranjevanje informacij tekom določenega ča- sovnega intervala, - tehnike in metode vnašanja novih informocij ter poizvedo- vanje o zahtevanih informacijah, ali z drugimi besedam! priprava odgovorov no vprašanja uporabnikov, - skupina Ijudi, ki vodi in oblikuje informacijski sistem. Skuplna izloča uporabne informacije, dopolnjuje podaf- kovno bozo, ažorira podatke v podatkovni bazi, priprav- Ija vprašanja, posreduje odgovore uporabnikom ter imple- mentira in dopolnjuje tehnike \n metode za izvajanje roz- ličnih funkcij šistema, - skupina uporabnikov sistema, ki ovrednoti sistem glede na svoje potrebe in kriterije. Kemijski informacijski sistemi (KIS v nadaljevanju) imajo vse značilnosti splošnih informaci jskih sistemov, so pa glede na svojstvenosti metod obdelave in posredovanja infor- macij dobili posebno mesto v okviru splošnih inforcnacijskih sistemov (2). Najbolj pogoste zahteve, oziroma vprasanja uporabnikov KIS najdemo v naslednji skupini vprašanj: - ali je določena spojina že navedena v literaturi (kdaj in qd koga), - ali obstajajo spojine, ki so podobne po sfrukturi spojini definirani v vprašanju, - katere so lastnosti \e spojine (fizikalne, biološke, kemij- ske ipd.), - kakšne so in katere so skupne lastnosti spojin iz navedene skupine spojin, - kako pripravimo oziroma kako sinteHziramo navedeno spo- jino ali serijo spojin, - kdoj je spojina prvič sinteHzirana, kateri so postopki sinteze ipd., - katere spojine imajo navedene lastnosti. Vsa navedena vprošanja zahtevajo, ali idenfifika- cijo spojine v podatkovni datoteki ali poizvedovanje o last- nosti.spojine. Vprašanja v katerih je strukh/ra spojine na- tančno definirana in, ki zohtevajo identifikacijo spojine v sistemu imenujemo strukturno-definirana vprašanja. Vprašanja v katerih so definirane fizikalno-kemijske lasfnosti spojine in, ki kot odgovor zahtevajo ime spojine ali skupine spojin, ki kažejo določene lastnosti imenujemo vprosanja za iskanje po vsebini datoteke(3). Ta vprašanja se definirajo s pomočjo deskriptorjev (4). Deskriptorji so besede ali kode s katerim so opisane lastnosti spojin ali kakšen drug pojem kot je: število in identiteta atomov v spojini, število in identiteta kemijskih zvez v spojini, molekulska teža, število in identiteto obročev, opis okolja določene podstruktui o v spojini, molekulska povezanost, molekulska geometrija, mo- lekulski tnodel v prostoru ipd.(4). Na sl. 1 smo pokazcili kof ilustracijo elemente, ki definirajo podatkovno bazo "Toxicology Data Bank" (3) realizirane v okviru programa Library's Toxicology Information Program v ZDA. Večina obsfoječih KIS je načrtovano tako da omo- goča dostop do informacij na oba omenjena načina: glede na strukturo spojine in glede na vsebino datoteke. Za te namene v okviru KIS najbolj pogosto se kreirajo invertirane datoteke, ki omogočajo hiter dostop do informacij z rozlič- nimi ključi oziroma deskriptorji (5), (6). Poleg tega zaradi fleksibilnosti in vse večjih poheb uporabnikov, je v velikih KIS omogočeno zapisovanje strukture spojine na več načinov. Primerno temu, so implementirane tehnike, ki omogočojo transformacije med različnirni zapisi, ali drugače povedano interkonverzijo med zapisi. Algoritmi, ki omogočajo avtomat- sko interkonverzijo med rozličnim! predstavitvami spojin rea- lizirajo nekatere funkcije v KIS, od katerih navajomo noj- bolj pomembne: - obdelava strukfurnih diagramov ter priprava strukturnih formul v obliko sprejemljivo za publiciranje, - prikazovanje strukturnih diagramov na video-terminalih, na podlagi zapisov z lineamimi notocijaini, - .transformacija strukturnih diagramov iz video-terminalov v zapise z obliko tabele povezanosrt, - !zmenjava podatkov med razticnimi bazami podafkov. V nadaljevanju bomo na kratko obdelali ter anali- zirali skupino najbolj pomembnih algoritmov, na katerih sloni realizacija vseh osnovnih funkcij KIS. 48 Toxicology Dota Bank Podatkovni elementi 1. Identifikacija substance a) kemijsko ime b) registrsko Stevilka službe CAS c) sinonimi d) molekulska formula e) molekulska teža f) zapis v Wiswesserjevi notaciji 2. Rozvrstitev substance a) kemijski razred b) najbolj pogosta uporaba 3. Kemijsko/fizikalne lostnosti a) temperatura topljenja b) temperatura vrenja c) gostota/specifična teža d) barva/oblika e) stabilnost/življenjska doba molekulskih obel f) spektroskopski in drugi podatki g) raztopljivosf 4. Toksikološki učinki: eksperimentalne šhjdije: a) na živalih b) z Ijudmi 5. Tbksikološke vrednosti a) minimalna strupena količina b) maksimalno dovoljena dnevna količina c) LD-vrednosH 6. Laborotorijske metode in sinteze 7. Interakcije v bioloških sistemih 8. Formakologija a) metabolizem b) absorpcija, dlstribucija, izločanje 9. Farmakoterapija 10". Ukrepi v primerlh zastrupitve oziroma eksplozije 11. Informacije proizvajalcev T3F. Metode prevoza TS. Podatki v zvezi z okoljem a) meje eksplozivnosti b) možnosti vžiga c) meje shrupenosti d) meje radioakHvnosti d) meje onesnaženja f) meje izpostavljanja g) prag mejnih vrednosti h) kopičenje, razgrajevanje in obstojnosf v okolju. Slika 1. 2. REGISTRACIJA SPOJINE Registrocija spojine je algoritemski postopek, ki omogoča' sprejemanje, povezovanje in uredHev vseh informa- cij v KIS, ki se nanašajo na določeno spojino. Postopek mora nojprej ugotoviti ali se v datofeki nahaja snov, ki je po strukturi ekvivalentna kandidatu za vpis v podatkovni datoteki. V primeru da takšne spojine ni, zapis nove spojine ter ostale informacije se uvrstijo na ustrezno mesto glede na lastnosti !n konfiguracijo spojine. Postopek za registracijo spojin je ozko vezan in omejen z osnovnim sistemom zo predstavitev spojin . Najbolj pomembna faza je primerjava strukture kandidata s strukhj- rami spojin v osnovni datoteki sistema. Uporabljene metode so zelo različne in prilagojene uporabljeni notaciji za pred- stavit-ev kemijskih slruktur. Zo vse metode pa velja naslednje: - kandidat za registracijo je zmeraj zapisan na enoličen in nedvoumen način, - osnovna datoteka je urejena tako da omogoča urejanje spojin v skupine s skupnim struktumim značajem, - poleg osnovnega zapisa, omogočeno je vnašanje dodatnih paramefrov, (to je najbolj pogosfo molekulska teia ali molekulska formula), zorodi kontroliranja napak. Če je datoteka organizirana fako da so spojirie grupirane v skupine, najprej najdemo odgovarjajočo skupino in zatem začnemo s primerjavo med spojinami. Učinkovifost posfopka je odvisna od velikost! skupin oziroma od izbire parametrov, ki ločijo posamezne skupine. Največji vpliv na čas za registracijo spojine ima uporabljena metoda za zapi- sovanje spojin. Linearne notacije omogočajo dokaj hitro pre- iskovanje podatkovnih datotek zarodi enoličnosK, nedvoum- nosH ter kompaktnosH zaplsov. Registracija Spojine zapisane v Wisweserjevt nol*actji se izvaja v okviru sistemo CROSSBOW (7). V sistemih, kjer je osnovni zapis spojin v obliki fabel povezonosti so nujno potrebne tehnike za generiranje enoličnlh in nedvoumnih zapisov iz poljubno podanih tabel povezanosti. Ti zapisi so znani pod imenom "kanonične fa- bele povezanosti" (8), (9). Problem generiranja kanonične tabele povezanosti se sestoji v izbiri invarianfnega oštevit- čenja atomov. Problem invariantnega ošfevilčenja atomov in zapisa v tabeli povezanosti je ekvivalenten problemu izomor- fizma grafov. Molekulske strukturne formule lahko opisujemo kot grofe, ki imajo vozlišča s semantično vsebino. Če sta enolična in nedvoumna zapisa dveh grafov Gl in G2 enaka, ozirotna še sta njihovi kodi enaki, potem sta Gl in G2 izo- morfna in sam postopek kodlranja je izomorfizem (10). Naj- bolj preprost postopek za zapis spojin v kanonični obliki je generiranje vseh n! možnih tabel povezanosti, oziroma vseh možnih oštevilčenj afomov v motekulskem grafu in leksikografski ureditvi n! fabei. Kanonična oblika fabele bi bila tista, ki bi imela najnižjo leksikografsko uredifev. Ta način izbire kanonične oblike je izredno zamuden in je primeren le če imamo spojine z zelo majhnim številom ato- mov. V primeru da je število atomov 20 hipofefičen računal- nik, ki lahko generiro eno matriko in to matriko primerja z drugo v eni mikrosekundi bi porabil več kof 75000 \et (11) za izpeljavo 20! operacij. V preteklosH je bilo več poizkusov za izpeljavo (8), (12), (13a, 13b), matemaHčne funkcije, ki bi omogo- čala hifro identifikacijo izomorfizma grafov. Do danes ni take funkcije, ki bi to opravila v poltnomskem času za po- I jubni graf. Na splošno problem izomorfizma grafov se nahaja v skupini NP-popolnih problemov. NP-popolni problemi so dobro raziskani problemi imenovani teški problemi. V le pro- bleme Itejemo: problem trgovskega potnika s področja opera- cijsklh raziskav, problem faufolog!je iz propozicijskega ra- čOna ter druge podobne kombinatorične probleme. NP-popolni problemi imajo to lastnost do če je en problem iz skupine NP-popolnih problemov rešljiv z algoritmom, ki imo polinom- ski čas, potem so vsi ostali problemi fudi rešljivi v polinom- skem času. Seveda za vsak problem je treba dokazaH do res pripada skupini NP-popolnih problemov. Pri reševanju probtemov iz skupine NP-popolnih pro- blemov, so zelo pogosto bili uporabljeni hevristični algo- filrni, posebej takrat ko je rešitev problema bila povezana z dejansko realizacijo kokšnega sistema za obdelavo podatkov. Tako so Ungar (14) ter drugi avtorji (15), (16), (17) po- izkusili zmanjSati časovno kompleksnost algorifmov za ugofav- Ijanje izomorfizma grcfov s pomočjo hevrstičnih pravil. Uspeh je bil dosežen le pri načrtovanju olgoritmov zo ugotavljanje izomorfizma ravninskih grafov (18), (19), (20). Predlagani algorUmi imajo polinomske čase. Ti algoritmi so neuporabni za splošne grafe. Dosedanje izkušnje so pokazale da problem izomor- fizma grafov nasplošno, ni mogoče rešiM z dobriro algorU- mom, zato se je trebo pri konkretnih problemih zadovoljiti s hevrističnimi algorifmi, ki dajejo dobre reiifve v večini pri- merov. Algoritem te vrste, ki se je v praksi pokazal kot zelo učinkovit,so razvili in implementiroli v KIS složbe CAS (5). Algoritem za kanonično osfevilčenje atomov, omejuje generiranje vseh možnih fabel povezonosti, tako da pred- časno uredi atome in shrani rezultate začetnih poizkusov 49 oštevilčenja. Algoritem je implemenriran na IBM 370/168 v obliki programa za registracijo spojine. Program obdela pri- bližno 13000 spojin tedensko, poprečen čas obdelave je 1000 sfruktur na minuto CPU(5). Zaradi nekatere spojine s simetrijo v strukturi, ki zahtevajo veliko število iteracij, implemenfaci ja algoritmo predvideva prekinitev obdelave, če je čos porabljen za eno strukturo večji od 3 sec. Med 677000 struktur obdelanih tekom 1975 leta obdetava 990 je zahtevala več kot 3sec. Zgled spojine fe vrsfe je ferocene (sl.2). Za te primere se uporablja posebna tehnika oštevil- Slika 2. čenjo, ki je znana kot tehnika za sortiranje in registriranje izomerov. Da bi posfopek pojašnili, smo v nadaljevanju po- nazorili algoritem za hitro generiranje kompakfne kanonične tabele povezanosti. Delovanje algorihna smo ilustrirali z zgledorn preproste spojine (slika 3): Algoritem zo generiranje kononične tabele poveza- nosti v sistemu službe CAS: N - množica poljubno oštevilčenih atomov n N, n je atom iz N z zaporedno itevilko n ' 1. določi vrednost povezanosti ln vsem elementom iz N: If, je enako številu neogljikovih otomov vezanih na atorn n (i zo to korak je. enako 1 ), 2. določi spremenljivko k', k1 je enako številu različnih vrednosti I' , 3. i -» i + 1, določi novo vrednost povezanosfi I, 'n ™ 'i Cn ie enako vsoH I vseh r atomov vezanih ' . na atom n) 4. določi ipremenljivko k , 5. če je k'rnih ali notaci jskih zapisih, je podstruktura lahko zapisana s simboli, ki se razlikujejo od simbolov uporabljenih za zopis popolne struknire, spet zaradi različnega okolja v katerem se pod- shruktura nahaja v različnih spojinah. Iskanje po podsfrukturoh se lohko odvlja na več ni- vojev natančnosH . Najnižji nivo natančnosK je iskanje v daloteki kjer imamo zapis spojin s fragmentacijskimi kodami ali če iščemo s pomočjo mask. Maslce (5) se naibolj pogoslo uporabljajo pri preiskovonju velikih bank poda*' substifuenf in naj bo vezan na atomu št. 3. Pri iskanju je bilo uporabljeno podatkovna baza NIH-EPA Mass Spectral Search System (22), (23), ki vsebuje okrog 30000 različnih spojin in njihdve masne spektre. V prvi in- vertirani datoteki s podatki o obročih je bilo najdeno 18 spo- jin, s po enim ali dveh obročkov. V drugi datoteki s podatki o fragmenfih je bilo najdeno 180 strukkir, ki vsebujejo fragment s substikient-om iz slike 6. Presek množic spojin iz a) defmicija podstrukture .Q večkratne povezave ji Tp ter H crtomi niso določeni U«\^ ^v\ /Ct številke označujejo oštevilčenje otomov v tabeli povezanosti c, c c s b) definicija zahtevanega fragmenta Ct10 ^3 ~C 2 Slika 6. 51 obeh datofek je dalo le eno spojino pokazano na sliki 7. Sevedo, večkrat se zgodi, da presek dveh datotek da več kot eno spojino, v tem primeru se uporabljo natančnejši način iskanja, znan kot "iskanje atom zo atomom" (27). najdena struktura Cl' molekutska formula : C8CU03 registrska številka CAS: 112088 Sliko 7. Pri vseh kompleksnih KIS, se natančno poizvedova- nje po podslrukturah izvaja z iskanjem arom za afomom. To iskanje je precej zamudno in zaradi tega se povsod pred tem izvajo predhodno iskanje po fragmentih (tako kot je bilo no- vedeno v primero zgoraj), po nomenkloturnih zapisih, ali po linearnih notacijah. V okviru sistema CAS je predliodno iskanje izvedeno s pomočjo nomeklatornih zapisov. Pri tem so bili uporabljeni najnovejši dosežki s področja preiskova- nja tekstov in računalniško čitljivih datofek z obliko teksto (24). • _ _ V sistemu z Dyjon-IUPAC-ovo notacijo predhodno' iskanjp se izvaja s pomočjo datotek s permutfranimi indeksi (25). Wiswesserjeva notacija je bila uporabljeno za isti namen v sistemu "Institut-a for Scientific InformoHon" (26). Uspeh iskanja je zelo odvisen tudi od uporabnika oziroma od spo- sobnosti da se pravilno opiše in kodira pričakovano okolje podstrukture. V koliko je to bolj uspešno v toliko je manjše števiio spojin za natončnejše preiskovanje. Nofančno poizvedovanje o tem ali se določena pod- struktara nahaja v nekaterih sfrukfurah je možno le s primer- janjem atomov iz podstrukfure z afomi strukfure in z primer- janjem povezav iz podstrukture s povezavami iz slrukture. Primerjanje je možno le če so strukture zapisane v topološki obliki, oziroma če zapis spojln izhaja iz njihovih grafov. V dosedanji tehnologiji KIS srečamo dva algoritma za primerja- vo podsfrukture s strukturo implementiranih v nairazličnejših enačicoh. To so: iterativna tehnika primerjanja atom z ato- mom (27) in fehnika postopnega izločanja množic (16). Oba algoritma v svoji prvotni obliki, so bila načrfovana za pri- merjanje popolnih struktur, oziroma za ugotavljanje izomor- fizma dveh grafov. Univerzalnost postopkov je omogočila uporabo tudi pri določanju izomorfizma podgrafov. 3.1 Iterativno iskanje in primerjanje atom z atomom Iterativno iskanje se sestoji v primerjanju atomov iz prdstrokture z atomi iz strukture do popolnega ujemanja ali neujemanjo. Da bi skrajšali čas primerjonja in hitreje izlo- čili neprimerne strukture, se primerjanje začne z atomom iz podstrukture, ki se najmanj pogosto sreča v datoteki. Vse strukture, ki ta atom ne vsebujejo odpadejo že na začetku. Po prvi uspešni pricnerjavi dveh atomov, se iskanje nadaljuje na enak način. Za naslednji afom.se vzame afom vezan na predhodnega in ki se najmanj pogosto sreča v datoteki. Če do ujemanja pride, se primerjanje nadaljuje z noslednjim so- sedom, ki se izbira po enakih kriterijih. V primeru dp pride do neujemanjo, postopek se vrne v točki zadnjega ujemanja in se primerjanje nadaljuje z drugirti atonnom. Prehojena pot primer|anja se sproM zaznamuje zaradi vračanja v primerih neujemanja. Postopek je iferativen in teie do ugotovitve popolnega ujemanja med podstrukturo in kaklnim delom strukture. V primeru da posfopek prehodi celofno strukturo in do ujemanja ne pride, postopek konča, kar pomeni da podstrukhjra ni vsebovana v strukhjri. 3.2. Postopno izločanje množic atomov Postopek postopnega izločanja množic je popolnoma rozličen od posfopka primerjonja atom z atomom in je bolj ročunalniško pobarvan. Avtor algoritma je Sussenguth (16), posamezne spremembe s ciljem izboljšanja algorifmo so pred- lagali Ming in Tauber (29). Postopek je izpeljan na podlagi naslednjih hrditev: - če sfa grafa G in G* izomorfna, potem podmnožice vozlilč grafo G, ki se razlikujejo med seboj glede na nekatere lastaosti vozlišč, so ekvivalenfne podmnožicam grafa G*, - če podmnožice vozlišč grafov G in G* z enakimi lastnost- mi vozlišč nimajo enako število elementov pofem G in G* nista izomorfna. V primeru izomorfizma tned grafom G in podgrafom grafa G* so pogoji oslabljen! in glasijo: odgovarjajoča vozli- šča grafo G so vsebovana v rnnožice vozMSč grafa G* z ena- kimi lastnostmi. Zapisana z matematičnim jezikom te dve trditvi dobita naslednjo obliko: a) graf G je izomorfen grafu G* vrednost vozlišča (x: vrednost (x )=v) = (x*: vrednosf (x* )=v ) vrednost povezave (x: vrednost ((x,y))=b)=(x*: vrednosf ((x*,y*))=b) vatenca (x:valenca (x)= d) = (x*:valenca (x* )= d) stopnjo zasedenosti (x:stopnja (x)=d) = (x*:stopnja (x*) = d) povezonosf A = A* —- /~A = /* A* /*x - množica vozlišč vezana na vozlišče x b) graf G je izomorfen podgrafu grafa G* vrednost vozlišča (x: vrednost (x)=v) •= (x*:vrednost (x*)=v) vrednost povezave (x:vrednost((x,y))=b) S (x*: vrednost ((x*,y**))=b) valenca (x:valenca(x)=d) = (x*: valenca (x*)=d) stopnjo zasedenosti (x: stopnja (x)= d)