E ÖTVÖS L ORÁND T UDOMÁNYEGYETEM I NFORMATIKAI K AR A LGORITMUSOK ÉS A LKALMAZÁSAIK TANSZÉK
Heurisztikák kidolgozása és összehasonlító elemzése részgráfok keresésére
D IPLOMAMUNKA
Témavezet˝ok:
Szerz˝o:
Dr. Tichler Krisztián
Kovács Dániel
Egyetemi adjunktus
Programtervez˝o informatikus MSc
ELTE IK
ELTE IK
Algoritmusok és Alkalmazásaik Tanszék
nappali tagozat
Kovács Péter Programtervez˝o matematikus ChemAxon Kft.
Budapest, 2012
Köszönetnyilvánítás Köszönöm Dr. Hunyadvári László docens úrnak, az ELTE IK Algoritmusok és Alkalmazásaik Tanszék vezet˝ojének, hogy lehet˝oséget biztosított számomra a tanszéken való munkához. Köszönetet szeretnék mondani témavezet˝oimnek : Dr. Tichler Krisztián adjunktus úrnak és Kovács Péternek, hogy értékes szakmai tanácsokkal láttak el a diplomamunka készítése folyamán. Kovács Péternek külön köszönettel tartozom, amiért megismertetett a témakörrel, és felkeltette érdekl˝odésemet iránta. Köszönet illeti az ELTE IK Információs Rendszerek Tanszékét, hogy lehet˝oséget biztosítottak az egyetemi adatbázisok használatára diplomamunkám során. Köszönöm munkahelyemnek a Nyugdíjfolyósító Igazgatóságnak, különösképpen f˝onökeimnek Honti Bertalannak és Gál Zoltánnak, hogy lehet˝oséget adtak diplomamunkám tesztelésére ipari min˝oség˝u gépeken, valamint, hogy minden eszközzel maximálisan támogatták tanulmányaimat. Köszönöm dr. Fekete István docens úrnak, hogy megszerettette velem az algoritmusok világát, és segítségét, hogy diplomamunkám a TÁMOP-pályázat keretein belül készülhetett el. Köszönöm a ChemAxon Kft.-nek, hogy akadémiai licencet biztosítottak programjaikhoz, ezzel lehet˝oséget adva a diplomamunka gyakorlati vonatkozásainak hangsúlyozásához.
A projekt az Európai Unió támogatásával, az Európai Szociális Alap társfinanszírozásával valósult meg (a támogatás száma TÁMOP 4.2.1./B-09/1/KMR-2010-0003).
Tartalomjegyzék 1. Bevezetés
3
2. Felhasználói dokumentáció
4
2.1. A kit˝uzött feladat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
2.2. Rendszerkövetelmények . . . . . . . . . . . . . . . . . . . . . . . . . .
5
2.3. Telepítés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
2.4. Futtatás . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
2.5. A melléklet tartalma . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
3. Elméleti háttér
7
3.1. Molekulák reprezentációja . . . . . . . . . . . . . . . . . . . . . . . . .
7
3.1.1. Matematikai absztrakció . . . . . . . . . . . . . . . . . . . . . .
7
3.1.2. SMILES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
3.2. A kit˝uzött feladat és annak absztrakciója . . . . . . . . . . . . . . . . . .
11
3.3. Algoritmusok . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
14
3.3.1. A „naiv” megközelítés . . . . . . . . . . . . . . . . . . . . . . .
14
3.3.2. Az Ullmann-algoritmus . . . . . . . . . . . . . . . . . . . . . .
18
3.3.3. A VF2 algoritmus . . . . . . . . . . . . . . . . . . . . . . . . .
19
3.3.4. A QuickSI algoritmus . . . . . . . . . . . . . . . . . . . . . . .
21
3.3.5. Algoritmusok ekvivalenciája . . . . . . . . . . . . . . . . . . . .
24
3.4. Molekulaleírók . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
27
3.5. El˝osz˝urések . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
31
3.6. Heurisztikák . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
32
4. Fejleszt˝oi dokumentáció
34
4.1. A program felépítése . . . . . . . . . . . . . . . . . . . . . . . . . . . .
34
4.2. Vezérlés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
35
4.2.1. Input / Output . . . . . . . . . . . . . . . . . . . . . . . . . . . .
35
4.2.2. Keresés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
39
4.3. Molekulák reprezentációja . . . . . . . . . . . . . . . . . . . . . . . . .
42
4.4. Molekulaleírók, el˝osz˝urések megvalósítása . . . . . . . . . . . . . . . .
45
4.5. Algoritmusok, heurisztikák megvalósítása . . . . . . . . . . . . . . . . .
47
5. Eredmények
49
5.1. Naplófájlok értelmezése . . . . . . . . . . . . . . . . . . . . . . . . . .
50
5.2. Tesztek futtatása . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
51
5.3. Algoritmusok eredményei . . . . . . . . . . . . . . . . . . . . . . . . .
54
5.3.1. Reprezentációs különbségek . . . . . . . . . . . . . . . . . . . .
57
5.3.2. Következtetések . . . . . . . . . . . . . . . . . . . . . . . . . .
58
5.4. Tároló megoldások eredményei . . . . . . . . . . . . . . . . . . . . . . .
59
5.4.1. MySQL-b˝ol olvasás . . . . . . . . . . . . . . . . . . . . . . . .
61
5.4.2. Oracle-b˝ol olvasás . . . . . . . . . . . . . . . . . . . . . . . . .
61
5.4.3. DB2-b˝ol olvasás . . . . . . . . . . . . . . . . . . . . . . . . . .
63
5.4.4. Fájlból olvasás . . . . . . . . . . . . . . . . . . . . . . . . . . .
64
5.4.5. Következtetések . . . . . . . . . . . . . . . . . . . . . . . . . .
66
6. Összefoglalás, kitekintés
68
7. Függelék
70
7.1. A program beállításai . . . . . . . . . . . . . . . . . . . . . . . . . . . .
70
7.1.1. A konfigurációs fájl felépítése . . . . . . . . . . . . . . . . . . .
70
7.1.2. Parancssori paraméterezés . . . . . . . . . . . . . . . . . . . . .
75
7.2. Licencelt programkönyvtár . . . . . . . . . . . . . . . . . . . . . . . . .
75
7.3. Példa nem rendezett SMILES-ra . . . . . . . . . . . . . . . . . . . . . .
76
7.4. A naplóállomány váza . . . . . . . . . . . . . . . . . . . . . . . . . . .
77
Hivatkozások
79
1.
Bevezetés
A kémiai informatika egy dinamikusan fejl˝od˝o, multidiszciplináris tudományterület, amely a kémia, a biológia, az informatika és a matematika határán található. A tudományterület els˝odleges célja a számítógépek megjelenítési lehet˝oségeinek és számítási teljesítményének felhasználása kémiai, biológiai célokra – ide értve az orvos-, és gyógyszertudományok egészét éppúgy, mint a genetikát, vagy akár a molekuláris biológiát. Az egyik nagyon gyakran felmerül˝o kérdés az úgynevezett részstruktúra-keresés [6], amikor arra vagyunk kíváncsiak, hogy egy molekula (atom és kötés megfeleltetéssel) megtalálható-e egy másikban. Ha a matematika és informatika szemszögéb˝ol közelítjük meg a kérdés, akkor látható, hogy ez gyakorlatilag a jól ismert részgráf-izomorfia eldöntési probléma [2]. A kérdés felhasználóbarát id˝o alatt való megválaszolása azonban nem könny˝u, hiszen a részgráf-izomorfia klasszikus NP-teljes feladat [14]. A molekulákat él- és csúcscímkézett gráfokként felfogva azonban nem általános gráfok lesznek, hanem rendelkeznek bizonyos speciális tulajdonságokkal. Olyan tulajdonságokkal is, amelyek lehet˝ové teszik a feladatot gyorsan megoldó algoritmusok elkészítését, és ezek már a gyakorlatban is jól használhatóak. A diplomamunkában három algoritmus vizsgáltunk [7, 31, 35], amelyek mindegyike másképp közelíti meg a problémát, másra helyezi a hangsúlyt. Ezek közül kett˝ot Java nyelven megvalósítottunk, harmadikként a ChemAxon Kft. ipari, implementációját használtuk. Készítettünk egy olyan keretprogramot, amellyel lehet˝ové vált az algoritmusok hatékonyságának elemzése, teljesítményük egymáshoz hasonlítása. Kit˝uzött célunk az volt, hogy megtudjuk: az új eredmények, megközelítések milyen viszonyban vannak a „jól bevált” megvalósításokkal, érdemes-e valamilyen új ötletet beemelni az eddigiek közé. Ezen kívül röviden megvizsgáltuk néhány relációs adatbázisrendszer alkalmazhatóságát a problémakörben.
3
2.
Felhasználói dokumentáció
A diplomamunkához készített program egy, a részgráf-izomorfia problémát (3.2. definíció) kémiai gráfokon (3.1. definíció) megoldó alkalmazás. A program bemenete lehet egy vagy több SMILES (lásd 3.1.2.) formátumú fájl, és esetleg egy, az 5.4-es alfejezetben definiált adatbázis. A SMILES formátum egy elterjedt, alapvet˝o, szöveges formátum molekulaszerkezetek tárolására. A program kimenete egy szövegfájl, valamint opcionálisan egy naplófájl, az 5.1-es alfejezetben megadottak szerint.
2.1.
A kituzött ˝ feladat
Tényleges feladatunk többféle lehet: fennáll-e részgráf-izomorfia, megkérdezhetjük a különböz˝o izomorfizmusok számát is, ahogy kíváncsiak lehetünk az egyes izomorfizmus függvényekre is. Példának tekintsük az 1-es ábrát, ahol a kisebb molekula részstruktúrája a nagyobbnak, és hat különböz˝o izomorfia található közöttük. A magyarázat: a gy˝ur˝uk kétféleképpen illeszthet˝oek egymásra – hiszen tengelyesen szimmetrikusak, ahol a tengelyt a kapcsolódó nitrogén határozza meg. Érdekességként megjegyezzük, hogy a nagyobb molekula nyolc automorfizmussal (önmagára vett izomorfizmussal) rendelkezik – ugyancsak a körök szimmetriája miatt. A feladat részletes specifikációját lásd a 3. fejezetben.
1. ábra. Példa részgráf-izomorfiához 4
2.2.
Rendszerkövetelmények
A feladat jellegéb˝ol adódóan nehéz ajánlott rendszerkövetelményeket megállapítani. Sok függ attól, hogy milyen környezetben szeretné használni az ember a programot: fájlból olvas vagy kiforrott adatbázis-kezel˝ot használ. A program futásához azonban nélkülözhetetlen egy Java 1.6 kompatibilis operációs rendszer (Windows XP/Vista/7; valamely Linux disztribúció, stb.), és a JRE 1.6 (vagy újabb) verziójának megléte. Az Eredmények fejezetben az egyes esetekben részletesen specifikáljuk, hogy milyen rendszer(ek)en futtattuk a mellékelt programot.
2.3.
Telepítés
A program telepítése egyszer˝u : a mellékelt CD tartalmazza az alkalmazást egy JAR állományban, de az általa használt publikus, illetve licencelt programkönyvtárakat nem. A lemezen lév˝o SSS (annyi mint Substructure search – azaz részstruktúra-keresés) mappát másoljuk a merevlemezünkön lév˝o tetsz˝oleges helyre, ahonnan a következ˝o alfejezetben leírt módon futtatható, a programkönyvtár telepítése után (lásd 7.2.). Az alkalmazás közvetlenül a lemezr˝ol nem indítható, a szükséges programkönyvtárak hiánya miatt.
2.4.
Futtatás
Indítsunk egy parancssori feldolgozást: lépjünk be a merevlemezre másolt SSS mappába, majd adjuk ki a JAVA - JAR SSS. JAR parancsot. Ekkor a mellette lév˝o config.properties fájlban beállított értékek alapján a program futtatásra kerül, a konzolra kiírva, hogy éppen hol tart. Alapállapotban a konzolra egy, az alábbihoz hasonló sor kerül: [===========/
] 57% (6/10 IN QUERIES , 2347/5234
TARGETS COMPLETED )
Az elején egy állapotjelz˝o látható, mely vizuálisan megmutatja, hogy hol tart a futás. Utána egy százalék érték, hogy hol tart összességében a feldolgozás, majd a pontos darabszám, 5
hogy hányadik lekérdez˝o molekula feldolgozásával végzett a program, azon belül is hányadik célmolekula feldolgozásával végzett. A config.properties állomány részletes felépítése megtalálható a Függelékben (lásd 7.1.).
2.5.
A melléklet tartalma
A mellékelt CD lemez tartalma:
• a diplomamunka pdf formátumban, annak forrása LATEX állományokban; • az elkészített program java bájt kódként, illetve annak forráskódja; • az eredmények átlagolásához használt keretprogram forráskódja; • a tesztadatokat tartalmazó állományok, és ezek meghatározása egy szövegfájlban; • az eredményeket részletez˝o napló- és táblázatállományok, és ezek meghatározása egy szövegfájlban.
6
3.
Elméleti háttér
A kémiai informatika [6, 11] elméleti háttéranyaga hatalmas (mint az látható például [11] hivatkozásjegyzékének hosszából is, amely 236 bejegyzést tartalmaz). Ebben a fejezetben a terület azon alapvet˝o ismereteit, fogalmait foglaltuk össze, amelyek a dolgozat megértéséhez feltétlenül szükségesek. Tárgyaljuk a molekulák számítógépes gráfreprezentációját, majd megvizsgáljuk a kit˝uzött feladathoz kapcsolódó irodalmat: a részgráf-izomorfia eldöntési problémáját.
3.1.
Molekulák reprezentációja
3.1.1.
Matematikai absztrakció
3.1. Definíció (Molekulagráf): Vegyünk egy G = (V, E, l, w) véges, irányítatlan, egyszer˝u, de nem feltétlenül összefügg˝o gráfot, ahol:
• V az n elem˝u csúcshalmaz, elemei a csúcsok (u, v, illetve ezek indexelt változatai); • E az m elem˝u élhalmaz, elemei az élek (e és indexelt változatai); • l a csúcscímkefüggvény, l : V → L, ahol L a csúcscímkehalmaz; • w az élcímkefüggvény, w : E → W , ahol W az élcímkehalmaz.
Legyen L a periódusos rendszerben szerepl˝o elemek, W pedig a kémiai (els˝osorban a kovalens) kötések halmaza. Emiatt a továbbiakban egyszer˝usítésként néhol atomokról írunk, amikor a csúcsokra gondolunk, illetve kötésekr˝ol írunk, amikor az élekre gondolunk. Az így definiált G gráfot nevezzük kémiai gráfnak, molekulagráfnak vagy pongyolán molekulának. Az egyszer˝uség kedvéért bevezetjük a következ˝o jelöléseket: V (G) a G gráf csúcsainak, E(G) a G gráf éleinek halmaza. Ezen kívül bevezetjük (u ∈ V (G) esetén) a degG (u) jelölést, ami u fokszámát adja meg. Tegyük fel továbbá, hogy a csúcsoknak adott valamilyen sorba rendezése, ekkor az indexOfG (u) jelölés u sorszámát adja vissza a 7
sorrendezésben (számítógépes reprezentációban ez tipikusan egy tömbindexnek feleltethet˝o meg). / Fontos megjegyeznünk, hogy ez matematikai absztrakció, és a valós kémiai tulajdonságok némelyike egyes konkrét implementációk, összehasonlítások során elveszhet. Bizonyos kémiai jellemz˝oknek, például az úgynevezett aromás gy˝ur˝uknek többféle lerajzolási módja is elterjedt, amelyek matematikai értelemben különböz˝o (nem izomorf) reprezentációt eredményeznek. Például a 2-es ábrán láthatjuk, hogy egy adott molekulát hogyan tudunk nem izomorf gráfokkal reprezentálni. Ilyen problémákkal a diplomamunka keretében nem foglalkoztunk. A diplomamunkában két különböz˝o reprezentációt használtunk fel. Az egyik egy ipari környezetben használt, univerzális megvalósítás a ChemAxon Kft. Marvin Beans publikus csomagjában található CHEMAXON . STRUC .M OLECULE osztály (és ahhoz kapcsolódóan a CHEMAXON . STRUC .M OL ATOM
és CHEMAXON . STRUC .M OL B OND osztályok). A másik
a diplomamunka témájához elegend˝o interfésszel rendelkez˝o, sokkal egyszer˝ubb molekula ábrázolás. A program egyes futásai során vagy az egyik vagy a másik reprezentációt használtuk. A molekulák elterjedt ábrázolási konvenciója szerint általában a hidrogénatomokat nem tüntetik fel, mert a kémia szabályai alapján tudják, hogy „hol mennyinek kellene lennie” – ezekre szoktak implicit hidrogénekként hivatkozni. Ebb˝ol kiindulva mi is csak a nem hidrogén atomokat (vagyis a nehéz atomokat) vizsgáltuk.
2. ábra. A koffein aromás és Kekulé-formájú ábrázolása
8
3.1.2.
SMILES
A molekulák reprezentálásának egyik elterjedt, kézenfekv˝o megoldása azok szövegként való tárolása. Erre rengeteg szerializációs módszert fejlesztettek ki, mi a SMILES [23, 39] formátumot használtuk (Simplified Molecular-Input Line-Entry System), amely az egyik legismertebb és a kémiai informatikában alapvet˝onek számító kódolás. A formátum alapjai egyszer˝uen megérthet˝oek, itt egy gyors áttekintést adunk róla. A formátum el˝onyei többek között, hogy nagyon egyszer˝u, tömör, könnyen hordozható, egyszóval „kényelmes”. Az angol szakirodalomban gyakran line notationként emlegetik, hangsúlyozva azt a jellemz˝ojét, hogy a fájl egy sorában egy molekula leírása található. Ez több szempontból is rendkívül praktikus: például a SMILES használható akár egyszer˝u parancssori paraméterként is. Ugyanakkor egyszer˝usége hátrányos is lehet egyes alkalmazásokban, hiszen nagyon kevés járulékos adatot tudunk tárolni benne. Általánosságban azonban a SMILES által nyújtott szolgáltatások b˝oven elegend˝oek. A SMILES szabvány a molekulagráf bejárásán alapul: vesszük a gráf egy tetsz˝oleges atomját, abból valamilyen (általában mélységi) bejárást indítunk, és az ez által meghatározott sorrendben jegyezzük le az atomokat és kötéseket. Az egyszeres (kovalens) kötéseket SMILES-ban nem jelöljük (ez az alapértelmezett kapcsolat). A kett˝os kötéseket = karakter, a hármasokat # karakter jelöli. Az atomokat kémiai vegyjelükkel reprezentáljuk, nagy ASCII karakterként – a két bet˝us elemek els˝o bet˝uje nagy, a második kis karakter (pl.: C – szén, Co – kobalt). A körök jelölésére az egyes atomokat sorszámozhatjuk, ekkor a sorszám következ˝o el˝ofordulása a stringben azt jelenti, hogy „körbe értünk”. Ezután az adott sorszám újrafelhasználható (minden páratlanadik definíció lesz, minden párosadik megjelenés hivatkozás, példának lásd a 3-as ábrát). Amennyiben több számjegy˝u hivatkozásokra van szükségünk
3. ábra. C1CCCCC1C1CCCCC1
9
4. ábra. c(O)(oc[si]1CC)sc1 a %<számjegyek> jelölést használhatjuk. Nem összefügg˝o molekulák esetén az egyes komponenseket ponttal választhatjuk el egymástól. Az aromás gy˝ur˝uket úgy jelöljük, hogy a benne szerepl˝o atomokat kisbet˝uvel írjuk (pl.: C helyett c szén esetén). Az eddigiek alapján a SMILES nem engedné meg a „furcsa” aromás gy˝ur˝uket, például amiben klór vagy kobalt található – csak az olyan elterjedt fajtákat, amik a mindennapi használat során el˝ofordulhatnak (amikben szén, nitrogén, oxigén, stb. van). Ennek oka egyszer˝u : a c1coccc1 nem lenne egyértelm˝u, hogy öt szénatom és egy oxigén alkot aromás gy˝ur˝ut, avagy négy szénatom és egy kobalt. Emiatt vezették be azt, hogy a nem egy karakter˝u vegyjelek írhatóak [] jelek közé, az el˝oz˝o példát hozva: c1coccc1 esetén oxigén van az aromás gy˝ur˝uben, míg c1[co]ccc1 esetén kobalt. []-ek közé egyéb kiegészít˝o adatok is írhatóak, például egy az atomhoz kapcsolódó hidrogén (így [CH] esetén tudhatjuk, hogy a szénhez biztosan implicit hidrogén kapcsolódik, nem pedig szabadon van az utolsó elektronja), vagy az adott atom töltése (pl.: [N-] vagy [N+]). Az elágazások jelölésére a () karakterek alkalmasak. Ebben az esetben a ( el˝otti atomról elindítunk egy ágat, amelynek leírása a )-lel ér véget, ezután a ( el˝otti atomtól folytatjuk ismét a molekula leírását. Példának lásd a 4-es ábrát. Az eddigieken túl további jelölések is találhatók a SMILES specifikációban, például az úgynevezett sztereokémia tárházából (a kötések térbeli konformációját leíró jelölések), és sok más kémiai tulajdonsághoz is. A fentiek alapján nyilvánvaló, hogy egy molekula SMILES-ként való szerializációja nem egyértelm˝u. Bármelyik atomból indíthatjuk a bejárást, a gráfban szerepl˝o köröket is 10
tetsz˝oleges helyen „köthetjük körbe”, és az egyes elágazásoknál sincs meghatározva, hogy merre haladjunk tovább. Példának nézzük az L-aszkorbinsav (C-vitamin) molekulájának kétféle leírását [34]:
a) OC=1C(OC(=O)C=1O)[C@@H](O)CO b) C([C@@H]([C@@H]1C(=C(C(=O)O1)O)O)O)O
5. ábra. C-vitamin A SMILES-ban is megfigyelhet˝o az implicit hidrogén jelenség : hidrogén (H) csak akkor kerül be a SMILES reprezentációba, ha az egyértelm˝uség eldöntésében fontos szerepet játszik – mint például az aszkorbinsavnál a térbeli elhelyezkedés szempontjából.
3.2.
A kituzött ˝ feladat és annak absztrakciója
A diplomamunka keretében a kémiai informatika egyik fontos problémáját vizsgáljuk meg : a részstruktúra-keresést. A tipikus felhasználás szerint adva van kevés számú lekérdez˝o molekula – n darab ún. query – és egy nagy rekordszámú molekula-adatbázis a célmolekulákkal – M darab ún. target. A kérdés az, hogy az egyes lekérdez˝o molekulák a molekula-adatbázis egyes molekuláiban megtalálhatóak-e, illetve hogy pontosan hányszor találhatóak meg (ún. hits, amire: hits ∈ N0 ). A 3.1. definíció alapján könnyen látható, hogy a most megfogalmazott kémiai feladat a gráfelmélet részgráf-izomorfia eldöntési problémája [2]. 3.2. Definíció (Részgráf-izomorfia molekulagráfokon):
Legyen adott két molekulagráf
Q = (VQ , EQ , lQ , wQ ) és T = (VT , ET , lT , wT ). Azt mondjuk, hogy Q részgráf-izomorf T -vel, ha ∃ϕ : VQ → VT injektív függvény, amelyre:
11
i) ∀u ∈ VQ : lQ (u) = lT (ϕ(u)) ; ii) ∀u, v ∈ VQ : (u, v) ∈ EQ ⇒ (ϕ(u), ϕ(v)) ∈ ET és wQ (u, v) = wT (ϕ(u), ϕ(v)).
Jelölés: Q T , azt is mondhatjuk, hogy a Q molekula részstruktúrája a T molekulának. A fenti tulajdonságokkal rendelkez˝o ϕ függvényt nevezzük izomorfizmus függvénynek.
/
A matematikai szakirodalomban elterjedt egy másik részgráf-izomorfia definíció is, amely csak akkor tekinti részgráf-izomorfnak Q-t T -vel, ha Q a T egy feszített részgráfjával izomorf. A változás a definíció második pontjában figyelhet˝o meg : ⇒ helyett ⇔ szerepel. Mi a továbbiakban a fenti, nem feszített részgráfos definíciót fogjuk alkalmazni, mert kémiai alkalmazásokban általában erre van szükség. Mindenesetre ha találtunk egy részgráfizomorfizmus függvényt, akkor az, hogy az feszített értelemben is izomorfizmus-e, nagyon egyszer˝uen eldönthet˝o lineáris id˝oben. A 6. ábrán látható példában (a) gráf részgráfja (b)-nek és (c)-nek, feszített részgráfja (b)-nek, de nem feszített részgráfja (c)-nek. A vizsgált feladat nehézségét jól mutatja, hogy a részgráf-izomorfia eldöntése általános gráfokra nézve NP-teljes feladat [14]. Célkit˝uzésünk azonban nem csak ennek az eldöntési problémának a megoldása, mi kétféle kérdést szeretnénk megválaszolni:
1) Létezik-e izomorfizmus függvény? 2) Hány különböz˝o izomorfizmus függvény létezik?
(a)
(b)
(c)
6. ábra. Részgráf és feszített részgráf összevetése
12
Jól látszik, hogy az els˝o kérdés eldöntése részfeladata a második feladat kiszámításának. Valójában, amikor az els˝o kérdést tesszük fel, ugyanaz a megoldás menete, mint a második esetben, csupán amint találunk megfelel˝o ϕ függvényt, abbahagyjuk a keresést, nem keressük meg a többit. Érezhet˝o, hogy egy NP-teljes feladat n · M -szeri megoldása sok id˝ot vehet igénybe, még kis gráfok esetén is. Szerencsénkre a molekulagráfoknak vannak bizonyos speciális tulajdonságai, amelyeket kihasználva a részstruktúra-keresés feladata a gyakorlatban lényegesen könnyebbé válik. Ezen tulajdonságokból néhány, a teljesség igénye nélkül:
• A molekulagráfok fokszámkorlátosak (az általunk vizsgált molekulák esetén jellemz˝oen 4 a csúcsok fokszámkorlátja, ritkább esetekben elérheti a 10-et). Ezt a fokszámkorlátot az egyes molekulákban szokás ∆-val jelölni. • A molekulák jellemz˝oen nem túl nagy gráfok. Esetünkben a legnagyobb vizsgált molekula is kevesebb mint 300 nehéz atomból áll, és nagyon kevés makromolekula (100-nál több atomot tartalmazó molekula) található az általunk vizsgált adatbázisban [24]. • A csúcs- és élcímkehalmazok viszonylag kicsik (csúcscímkéb˝ol jelenleg 109 van, élcímkéb˝ol ötöt vizsgáltunk). Mivel a molekulagráfok csúcs- és élcímkézettek, ezért a lehetséges illesztések száma sok esetben nagyságrendekkel csökken a nem címkézett gráfokhoz képest. • A molekulagráfoknak vannak úgynevezett jellemz˝o részstruktúrái (lásd például az aminosavak definícióját [33], amely egy részstruktúrára épül).
Ezen és más speciális tulajdonságokat kiaknázva lehet˝oségünk van az általános részgráfizomorfiát eldönt˝o algoritmusoknál hatékonyabb megoldások implementálására, különböz˝o heurisztikák megvalósítására (lásd 3.6.), ahogy azt a következ˝o alfejezetekben kifejtjük. Ezen kívül élhetünk bizonyos sz˝urési eljárásokkal (lásd 3.5.), amely alapján a gráfillesztések számát csökkenthetjük, ha szerencsénk van, akár nagyságrendekkel.
13
3.3.
Algoritmusok
A részgráf-izomorfia probléma sok néz˝opontból megközelíthet˝o, de az algoritmusok magja általában valamilyen visszalépéses kereséses [8, 25] eljárás. Mi ebben az alfejezetben négy különböz˝o módszert ismertetünk, amelyeket a programban felhasználtunk – hármat mi implementáltunk, egyet pedig a ChemAxon Kft. publikus könyvtárából használtunk.
3.3.1.
A „naiv” megközelítés
Kit˝uzött feladatunk szerint két gráf közötti izomorfizmus függvények számosságára vagyunk kíváncsiak. Vagyis valamilyen módon reprezentálnunk kell a 3.2-es definícióban szerepl˝o ϕ függvényt. Mivel NP-teljes feladatról van szó, ezért egyértelm˝u, hogy az úgynevezett „brute-force”, O(|V (T )||V (Q)| ) futási idej˝u megközelítések a gyakorlatban használhatatlanok, de nincs is ilyen algoritmusokra szükségünk. Ha belegondolunk, a ϕ függvény, mint injektív leképezés eltárolását megtehetjük rendezett párokkal: vi ∈ V (Q), vj ∈ V (T ) : ϕ(vi ) = vj esetén nekünk (vi , vj ) pár kell. Számítógépes reprezentációnál a csúcsokat általában valamilyen tömbben vagy listában tároljuk, tehát minden csúcshoz egyértelm˝uen hozzá tudunk rendelni egy számot (az indexét). Eszerint nekünk elég az adott csúcsok indexeinek párjait eltárolnunk. Erre egy kézenfekv˝o tárolási módszer egy |V (Q)| × |V (T )| dimenziós BOOLEAN mátrix, amelyben: TRUE , ha ϕ(v ) = v i j ϕmatrix [i, j] := FALSE , egyébként Azonban, mivel ϕ injektív, a most definiált mátrix nagyon ritkán lesz kitöltve: minden sorban pontosan egy, és minden oszlopban legfeljebb egy
TRUE
érték lesz: |V (Q)| =
= |V (T )| esetén minden oszlopban lesz TRUE értékünk, |V (Q)| < |V (T )| esetén pedig |V (T )| − |V (Q)| oszlopban nem lesz TRUE érték. Ez alapján a tulajdonság alapján egyszer˝usíthetünk a reprezentáción: elég egy |V (Q)| dimenziós számtömb, amelyben: ϕvector [i] := j, ha ϕ(vi ) = vj 14
Feladatunk ezek után az, hogy megtaláljuk azokat az ϕvector tömböket, amelyek a két gráf közötti izomorfizmust határoznak meg – igazából arra vagyunk kíváncsiak, hogy hány különböz˝o ϕvector tömb létezik (a továbbiakban ϕvector helyett egyszer˝uen ϕ-t írunk). Ezt az absztrakciót vizsgálva kézenfekv˝o az 1. algoritmushoz hasonló megvalósítás használata. Mint látható, az algoritmus, futása közben parciális leképezéseket fog tárolni a két molekula között, ami azt jelenti, hogy a lekérdez˝o molekula egyes atomjainak már megtaláltuk a lehetséges párját a célmolekulában, a többit viszont még nem. Az algoritmus könnyen érthet˝ové válik, ha a leírt vektor-reprezentáció mellett ismerjük a visszalépéses kereséses algoritmusok általános „elképzelését”. Eszerint a visszalépéses keresés gyakorlatilag egy fa bejárása lenne, ahol az egyes csúcsok az egyes állapotok – esetünkben az egyes különböz˝o részleképezések a két molekula között. A fa magassága |V (Q)|, és minden szinten minden csúcsnak |V (T )| gyermeke van. Könnyen belátható, hogy a fa levelei a V (Q) → V (T ) leképezések, amely leveleknek csak egy részhalmaza lesz injektív leképezés, ténylegesen izomorfizmus pedig még sokkal kevesebb. A feladatunk ekkor az, hogy a levelekr˝ol eldöntsük, melyek felelnek meg a 3.2-es definíciónak, ezek az úgynevezett érvényes leképezések, és ezeknek a számosságára vagyunk mi kíváncsiak. Az 1. algoritmus ennek a fának a bejárását valósítja meg, egy segédfüggvény használatával. Jól látszik, hogy ha csak az izomorfia eldöntési problémáját szeretnénk megválaszolni ?
(vagyis arra vagyunk kíváncsiak, hogy Q T , de arra nem, hogy hány különböz˝o ϕ létezik), akkor nincs más dolgunk, mint a hits változó növelése helyett visszatérnünk a programból 1-gyel. A keresési tér mérete O(|V (T )||V (Q)| ), ahol a m˝uvelet nem elemi, hanem annak eldöntése, hogy az adott leképezés érvényes-e. Vagyis a teljes fa bejárása nem elfogadható megoldás, mivel a futási id˝o nagyon nagy lenne. Ezért a visszalépéses keresés két lényegi kifejezést vezet be, ezek pedig a vágás és a visszalépés. Vágásnak mondjuk azt, amikor a fa egy adott csúcsában járva felismerjük azt, hogy a csúcs alatti részfában biztosan nem lehet részgráf-izomorfiát reprezentáló levél – ekkor a teljes részfát kihagyhatjuk, úgymond „kivághatjuk”. Ennek feltételeit láthatjuk a 2. alprogram elején : ha nem megfelel˝o típusú atomot illesztenénk vagy ha egy atomot a lekérdez˝o molekulából másodszor akarnánk illeszteni, akkor az accept függvény hamis értékkel tér vissza, és a program nem járja be 15
Algoritmus 1 „Naiv” visszalépéses keresés Input : Q, T molekulagráfok Output: hits, az izomorfizmusok száma hits := 0; for i := 0..|V (Q)| − 1 do ϕ[i] := −1; end for depth := 0; while depth ≥ 0 and depth < |V (Q)| do ϕ[depth] := ϕ[depth] + 1;
. következ˝o illesztés
if ϕ[depth] = |V (T )| then
. nem tudjuk ϕ[depth]-et többre kiterjeszteni
ϕ[depth] := −1;
. kivesszük a leképezésb˝ol
depth := depth − 1;
. visszalépés
else if accept(ϕ, depth, Q, T ) then
. érvényes az illesztés
if depth = |V (Q)| − 1 then
. új ϕ-t találtunk
hits := hits + 1; . megpróbáljuk kiterjeszteni
else depth := depth + 1; end if end if end if end while return hits;
16
Algoritmus 2 accept(ϕ, depth, Q, T ) Output: BOOLEAN, ϕ érvényes leképezés-e if lQ (uindexOfQ (depth) ) 6= lT (vindexOfT (ϕ[depth]) ) then . különböz˝o atomok
return FALSE ; end if for i := 0..depth − 1 do if ϕ[depth] = ϕ[i] then
. már a leképezésben van
return FALSE ; end if end for for i := 0..depth − 1 do if (uindexOfQ (i) , uindexOfQ (depth) ) ∈ EQ and ((vindexOfT (ϕ[i]) , vindexOfT (ϕ[depth]) ) ∈ / ET or (wQ (uindexOfQ (i) , uindexOfQ (depth) ) 6= 6= wT (vindexOfT (ϕ[i]) , vindexOfT (ϕ[depth]) ))) then
. nem egyeznek a kötések
return FALSE ; end if end for return TRUE ;
a keresési tér azon részfáját. Az accept második fele azt vizsgálja meg, hogy az eddigi (rész)leképezés megfelel-e ϕ definíciójának. Visszalépésre akkor kerül sor, ha egy adott csúcsból nem tudunk több bejárást indítani, ekkor a fában fellépünk az adott csúcs szül˝ojére, és onnan folytatjuk: vagy a többi gyerekkel, vagy ismét visszalépünk, ha már nem maradt több bejárható lehet˝oségünk. Az 1. programban amikor elérünk a fában egy érvényes levelet, akkor növeljük a hits számlálót, és ezután a program átlép a következ˝o lehetséges illesztésre, keresve ezzel a többi megoldást.
17
3.3.2.
Az Ullmann-algoritmus
Julian R. Ullmann 1976-ban publikált egy, a részgráf-izomorfiát eldönt˝o algoritmust [35], amely az azóta eltelt években nagyon széles körben elterjedt, és a szakirodalomban Ullmann-algoritmusként hivatkoznak rá. Érdekesség, hogy Ullmann szintén a kémiai gráfokat hozta a cikkben példának az algoritmus használatára, de a bemutatott eljárás nem használ ki olyan tulajdonságot, amely csak a molekulagráfokra lenne jellemz˝o : az Ullmann algoritmus bármilyen él- és csúcscímkézett gráfra alkalmazható. Ez az algoritmus szintén egy visszalépéses keresésen alapuló eljárás. Ullmann észrevette azt, hogy az egyszer˝u megközelítés egyik legnagyobb problémája az, hogy a keresési fában túl sok olyan ágon próbál illeszteni, ami már korában megjósolható módon nem fog eredményt hozni. Ezen gondolatot követve úgynevezett finomítási kritériumokat vezetett be, amik alapján egy-egy ágról a fa korábbi szintjein eldönthet˝o, hogy található-e rajta izomorfiát reprezentáló levél vagy sem. Ennek nyomon követése érdekében definiál egy úgynevezett leképezési mátrixot, amellyel nyilvántartja, hogy az aktuális állapotból milyen leképezések képzelhet˝oek el a kés˝obbi szinteken. Minden illesztés után ezt a leképzési mátrixot „ritkítja” a finomítási kritériumok alapján, ezzel csökkentve a kés˝obb megvizsgálandó leképezések számát. Az algoritmus hátrányaként memóriaigényét szokták említeni: amikor visszalépést hajtunk végre a fában, a leképezési mátrix ott érvényes értékeit is vissza kell tudnunk állítani, tehát kénytelenek vagyunk a keresési fa minden szintjén a mátrix aktuális állapotát eltárolni. Annak ellenére, hogy az Ullmann-algoritmus publikálása óta évtizedek teltek el, és hogy memória igénye meglehet˝osen nagy lehet, ez az egyik leggyakrabban használt eljárás a részgráf-izomorfia eldöntésére, általános hatékonysága miatt [7].
18
3.3.3.
A VF2 algoritmus
A VF2 algoritmust [7] els˝osorban nagy, irányított gráfokon való részgráfkereséshez dolgozták ki a szerz˝ok. A VF2 szintén a visszalépéses keresés elvén épül fel, különbsége az el˝oz˝oekben tárgyalt algoritmusokhoz képest a keresési fa felépítésében rejlik. Vagyis a VF2 ugyanúgy, mint a korábbi algoritmusok, minden lépésben egy részleképezést tekint a két gráf között, és ezt próbálja úgy b˝ovíteni, hogy a legvégén teljes izomorfizmust kapjunk. A VF2 gondolatmenete szerint minden lépésben meghatározunk lehetséges (u, v) párokat (u ∈ V (Q), v ∈ V (T )), amelyekkel kiterjeszthetjük az eddigi parciális izomorfizmusunkat. Ezután csak ezekkel a párokkal próbáljuk meg b˝ovíteni az eddigi részleképezést, és amikor mindegyikkel végeztünk, akkor lépünk vissza a keresési fában az el˝oz˝o szintre. Feltételezzük, hogy a gráfok csúcsain adott egy teljes rendezés, amely mentén bejárjuk o˝ ket az algoritmus során – legegyszer˝ubb esetként vehetjük a számítógépes reprezentációban kapott tömbindexeken, mint természetes számokon értelmezett rendezést. Az eredetileg, a [7]-ben publikált VF2 algoritmus a részgráf-izomorfia eldöntési problémáját oldja meg, irányított gráfokon. Néhány átalakítással alkalmazható irányítatlan gráfokra, és izomorfizmus függvények számának meghatározására is, ezt a verziót ismertetjük most. Algoritmus 3 VF2(ϕ, Q, T, hits, depth) if depth = |V (Q)| then hits := hits + 1; else for all p in possibleM aps(ϕ, Q, T, depth) do addM apping(ϕ, p, depth); if accept(ϕ, Q, T, depth) then V F 2(ϕ, Q, T, hits, depth); end if removeM apping(ϕ, p, depth); end for end if
19
A 3-as algoritmus kulcsa a korábbiakban megismert accept függvény (amely megegyezik a 2-es algoritmusban bemutatott döntési eljárással), valamint a lehetséges következ˝o megfeleltetett atomok halmazának kiszámolása. Az addM apping és removeM apping segédfüggvények értelemszer˝uen ϕ és depth megfelel˝o módosításait hajtják végre. Kezdetben természetesen az algoritmus „üres” ϕ-vel, hits = depth = 0 paraméterekkel kerül meghívásra. A lehetséges csúcsok halmazának kiszámítása és nyilvántartása „ügyetlen” reprezentáció esetén igencsak költséges tud lenni. Ezt a VF2 megalkotói úgy küszöbölték ki, hogy bevezettek kiegészít˝o információkat tároló tömböket, amelyek karbantartása gyorsan megoldható, és segítségükkel a lehetséges csúcsok halmazának kiszámítása nagyon effektíven elvégezhet˝o. Ezért vezessük be az alábbiakat:
• ϕQ [i] := j, ha ϕ(i) = j, −1 egyébként (∀i ∈ [0..|V (Q)| − 1]); • ϕT [j] := i, ha ϕ(i) = j, −1 egyébként (∀j ∈ [0..|V (T )| − 1]); • ∀i ∈ [0..|V (Q)| − 1] : ψQ [i] := −1, kivéve, ha: ◦ ϕQ [i] 6= −1, akkor ψQ [i] := d, ahol d a keresési fa azon mélysége, amikor vi -t bevettük a leképezésbe; ◦ ϕQ [k] = −1 és vk ∈ V (Q) : ∃vi ∈ V (Q) : ϕQ [i] 6= −1 és (vi , vk ) ∈ E(Q) esetén ψQ [k] := max{ψQ [i] |vi ∈ V (Q) : ϕQ [i] 6= −1 és (vi , vk ) ∈ E(Q)}; ◦ informálisan: ψ tömbben tároljuk el, hogy az adott atomot mikor vette be a leképezésbe, és annak szomszédait mikor „látta utoljára” az algoritmus; • ψT legyen analóg ψQ -val a célmolekulára nézve; • ezen tömbök karbantartását is az addM apping és removeM apping függvények végzik; • f irstm o i-t (i ∈ [n..m]), amire a paraméterben kapott i=n ( BOOLEAN ) jelölje az els˝ kifejezés igaz, ha pedig nincs ilyen akkor értéke legyen N U LL.
20
Algoritmus 4 possibleM aps(ϕ, Q, T, depth) Output: az izomorfiába bevehet˝o atompárok halmaza |V (Q)|−1
query := f irsti=0
(ϕQ [i] = −1 and 0 < ψQ [i] ≤ depth);
if query = N U LL then |V (Q)|−1
query := f irsti=0
(ϕQ [i] = −1 and ψQ [i] = 0);
end if return {query}× {j|v ∈ V (T ) : j = indexOfT (v) és ϕT [j] = −1 és ψT [j] ≤ depth}; Ezekkel a jelölésekkel egyszer˝uen meghatározhatjuk a lehetséges következ˝o csúcsok halmazát (lásd a 4-es szubrutint). Látható, hogy a VF2 alapgondolata szerint mindig csak azon atomok közül kell választanunk, amelyek szomszédosak az eddig leképzett atomokkal – vagy nem összefügg˝o gráf esetén, ha az adott komponenst már teljesen leképeztük, akkor egy másik komponensb˝ol válasszunk. Ha a lehetséges következ˝o csúcsok halmaza üres, akkor értelemszer˝uen visszalépést hajtunk végre a keresési fában.
3.3.4.
A QuickSI algoritmus
A Quick Subgraph Isomorphism (röviden QuickSI) [31] algoritmus megalkotói ismét egy másik utat követtek, és sok gráfot tartalmazó adatbázisok esetén jól m˝uköd˝o elképzeléssel álltak el˝o. Ez az algoritmus a keresési fa méretét más elvek mentén csökkenti. 3.3. Definíció (QI-sorozat): Vegyünk egy G molekulagráfot (3.1. definíció), és vegyük G egy tetsz˝oleges feszít˝ofáját. Ekkor QIG = T0 R0,0 . . . R0,j0 . . . Tn−1 Rn−1,0 . . . Rn−1,jn −1 sorozat G egy QI-sorozata, ahol: • Ti három adatot tárol: Ti .v az adott csúcs indexét a gráfban, Ti .l az adott csúcs címkéjét, Ti .p a feszít˝ofabeli szül˝ojének indexét a QI-sorozatban; • Ri,j kétféle kiegészít˝o adatot tárolhat: ha degG (Ti .v) > 2, akkor [deg : degG (Ti .v)]-t, ezen kívül tárolhat plusz él információt (amik a feszít˝ofában nincsenek benne, de a gráfban benne vannak) [edgeTo : p] formában. 21
Belátható, hogy egy QI-sorozat egy adott gráfot egyértelm˝uen meghatároz, míg egy adott gráfhoz több QI-sorozat készíthet˝o. / A 7-es ábrán látható molekulához például meghatározhatjuk a 8-as ábrán látható QI-sorozatokat.
7. ábra. Példa QI-sorozathoz [Ti .p, Ti .l, Ti .v] or R
[Ti .p, Ti .l, Ti .v] or R
T0
[−1, N , 0]
T0
[−1, C, 3]
T1
[0, C, 1]
T1
[0, C, 4]
R1,0
[deg : 3]
T2
[0, C, 2]
T2
[1, C, 2]
T3
[1, C, 5]
T3
[2, C, 3]
T4
[3, C, 6]
T4
[3, C, 4]
T5
[4, C, 1]
T5
[4, C, 5]
R5,0
[deg : 3]
T6
[5, C, 6]
R5,1
[edgeTo : 2]
R6,0
[edgeTo : 1]
T6
[5, N , 0]
8. ábra. A 7. ábrán látható molekula két lehetséges QI-sorozata Jól látható, hogy bármely QI-sorozatból egyértelm˝uen visszaállítható a gráf. A QuickSI algoritmusban, hasonlóan a korábban tárgyaltakhoz, egy ϕ tömbben tudjuk tárolni az aktuális parciális izomorfizmust, és ugyanúgy a különböz˝o izomorfizmusok számát meg tudjuk számolni. A [31]-ben definiált algoritmus összefügg˝o, csúcscímkézett gráfokra lett megalkotva, a részgráf-izomorfia problémáját eldöntend˝o. Átalakításokkal alkalmassá tehet˝o nem feltétlenül összefügg˝o, csúcs- és élcímkézett gráfokon az izomorfizmusok számosságának megszámolására.
22
Ez az algoritmus is a visszalépéses keresés elvén m˝uködik. Bemenetként várja a lekérdez˝o molekula egy QI-sorozatát és a célmolekulát. A futás során a lekérdez˝o molekulában a QI-sorozat szerinti következ˝o atomot próbálja leképezni a célmolekulára. Amennyiben bármelyik Ri,j feltétel sérül, a leképezés nem érvényes, lépünk a következ˝o leképezésre. Ehhez a feltételrendszerhez kell még hozzáillesztenünk saját kiegészít˝oinket, ha az általunk vizsgált kérdést szeretnénk megválaszolni ezzel az algoritmussal. Egyértelm˝uen látható, hogy a lekérdez˝o molekula különböz˝o QI-sorozatai esetén a visszalépéses keresés keresési fája mindig teljesen másképp fog felépülni: függ a csúcsok és a kiegészít˝o adatok sorrendjét˝ol az adott QI-sorozatban. Ezen megfigyelést követve van értelme optimális QI-sorozatról beszélnünk. Rövid gondolatmenet után belátható, hogy az adott két molekula esetén optimális QI-sorozatot akkor tudjuk meghatározni, ha ismerjük már az összes izomorfizmust a lekérdez˝o és a célmolekula között. Azonban készíthetünk adatbázis-hatékony QI-sorozatot a célmolekulák adatbázisa alapján : lehetséges konstruálni minden egyes lekérdez˝o molekulára olyan QI-sorozatot, amely az adott célmolekula adatbázis tulajdonságai alapján általánosságban nagyon hatékony lesz. 3.4. Definíció (Atomtípus tartója):
Vegyünk egy D molekula-adatbázist, és legyen
G ∈ D, ekkor egy a atomtípus tartója a következ˝o valós szám: σ(a) :=
|{u|u ∈ V (G) és l(u) = a}| |{G0 ∈ D|∃u ∈ V (G0 ) : l(u) = a}|
Informálisan: az adott atomtípusnak a számossága az adatbázisban, osztva azoknak a molekuláknak a számával, amelyek legalább egy ilyen típusú atomot tartalmaznak. A továbbiakban u ∈ V (G) esetén legyen σ(u) := σ(l(u)). 3.5. Definíció (Kötéstípus tartója):
/
Vegyünk egy D molekula-adatbázist, és legyen
G ∈ D, ekkor egy b kötéstípus tartója a következ˝o valós szám: σ(b, a1 , a2 ) :=
|{e|e = (u, v) ∈ E(G) és w(e) = b és l(u) = a1 és l(v) = a2 }| |{G0 ∈ D|∃e = (u, v) ∈ E(G0 ) : w(e) = b és l(u) = a1 és l(v) = a2 }|
Informálisan: az adott kötéstípusnak (amit a típusa, és a két általa összekötött atom sorrendje és típusa határoz meg) a számossága az adatbázisban, osztva azoknak a molekuláknak a számával, amelyek legalább egy ilyen kötést tartalmaznak. A továbbiakban legyen e = (u, v) ∈ E(G) esetén σ(e) := σ(w(e), l(u), l(v)).
23
/
Algoritmus 5 Hatékony QI-sorozat Input : G molekula Output: S, az adatbázis-hatékony QI-sorozat W := V ;
. minden csúcs fehér
S :=<>;
. a QI-sorozat üres
S := S ⊕ getF irstSpanningBond(W, G); while W 6= ∅ do S := S ⊕ getN extSpanningBond(W, G); end while return S; Nyilvánvaló, hogy bármely a atomra σ(a) és bármely b kötésre σ(b) legalább 1, ha az adott atom illetve kötés szerepel az adatbázisban és 0, ha nem. Miután a célmolekulák adatbázisa alapján kiszámoltuk az összes nem nulla tartót (angolul average inner support), az egyes lekérdez˝o molekulákra elkészíthetjük az adatbázis-hatékony QI-sorozatot (5, 6, 8, és 7 algoritmusok). Mivel a QI-sorozat egy feszít˝ofát határoz meg, így kézenfekv˝o a Prim-algoritmus [8] egy, az igényekhez igazított variánsát alkalmaznunk. A Prim-algoritmus a gráf minimális összköltség˝u feszít˝ofái közül határoz meg egyet. Nekünk is erre van szükségünk, csupán az egyes élek költségének számolása nem kézenfekv˝o, és a kiegészít˝o adatokat is kezelnünk kell (ezt hivatott jelölni a ⊕ m˝uvelet).
3.3.5.
Algoritmusok ekvivalenciája
A bemutatott négy algoritmus mindegyike alapvet˝oen a visszalépéses keresés elvére épül. Ennek következtében az algoritmusok elég közel állnak egymáshoz, és az implementáció során (lásd 4.5.) teljesen világossá vált számunkra, hogy mennyire is igaz ez. Az algoritmusok egyértelm˝u, hogy ugyanazt a feladatot oldják meg – hiszen így definiáltuk o˝ ket –, de egymásba viszonylag könnyen át is alakíthatóak.
24
Algoritmus 6 getF irstSpanningBond(W, G) Output: az adatbázis-hatékony QI-sorozat els˝o kötése P := {e|e ∈ E(G) : ∀e0 ∈ E(G) : σ(e) ≤ σ(e0 )};
. minimális tartójú kötések
if |P | > 1 then P 0 := {e|e = (u, v) ∈ P : ∀(u0 , v 0 ) ∈ P : degG (u) + degG (v) ≤ degG (u0 ) + degG (v 0 )}; P := P 0 ;
. minimális fokú atomokkal rendelkez˝o kötések
end if if |P | > 0 then (u, v) :∈ P ;
. válasszunk egyet
W := W − {u, v};
. az atomok már nem fehérek
return (u, v); else return getN extSpanningAtom(W, G); end if
Algoritmus 7 getN extSpanningAtom(W, G) Output: az adatbázis-hatékony QI-sorozat következ˝o atomja P := {u|u ∈ W : ∀u0 ∈ W : σ(u) ≤ σ(u0 )};
. minimális tartójú atomok
if |P | > 0 then u :∈ P ;
. válasszunk egyet
W := W − {u};
. az atom már nem fehér
return u; else return ∅; end if
25
Algoritmus 8 getN extSpanningBond(W, G) Output: az adatbázis-hatékony QI-sorozat következ˝o kötése P := {e|e = (u, v) ∈ E(G) : u ∈ / W és v ∈ W : ∀e0 = (u0 , v 0 ) ∈ E(G) : u0 ∈ / W és v 0 ∈ W : σ(e) ≤ σ(e0 )};
. minimális tartójú kimen˝o kötések
if |P | > 1 then P 0 := {e|e = (u, v) ∈ P : u ∈ / W és v ∈ W : ∀e0 = (u0 , v 0 ) ∈ P : u0 ∈ / W és v 0 ∈ W : |{x ∈ V (G)|x ∈ / W és (x, v) ∈ E(G)}| ≥ ≥ |{x0 ∈ V (G)|x0 ∈ / W és (x0 , v 0 ) ∈ E(G)}|} P := P 0
. új atomok a legtöbb vissza/keresztéllel
end if if |P | > 1 then P 0 := {e|e = (u, v) ∈ P : ∀e0 = (u0 , v 0 ) ∈ P : degG (v) ≤ degG (v 0 )}; P := P 0 ;
. új atomok a legkevesebb kimen˝o éllel
end if if |P | > 0 then (u, v) :∈ P ;
. válasszunk egyet
W := W − {u, v};
. az atomok már nem fehérek
return (u, v); else return getN extSpanningAtom(W ); end if
26
3.4.
Molekulaleírók
Az egyes molekulákhoz rendelhetünk különböz˝o tulajdonságokat, ezeket nevezi a szakirodalom általában molekulaleíróknak (molecular descriptor) [11]. A korábban megismert QI-sorozat (3.3. definíció) is tekinthet˝o például egy speciális leírónak. Ilyen leíróból készíthetünk egyszer˝ueket és bonyolultakat. Az általános cél az, hogy ezek összehasonlítása gyorsan megtörténhessen, és valamilyen olyan tulajdonságot írjanak le, amely alapján jól m˝uköd˝o el˝osz˝urést (lásd 3.5.) vagy heurisztikát (lásd 3.6.) tudunk készíteni. Az, hogy a leíró kiszámolása gyors legyen, általában nem cél, hiszen gyakorlati alkalmazásoknál a célmolekulák adatbázisban vannak tárolva, és a hozzájuk tartozó leírókat egyetlen egyszer kell kiszámolnunk. Természetesen a számolás sem tarthat túl sokáig, mert minden egyes lekérdez˝o molekula esetén is ki kell o˝ ket számolnunk, hogy összehasonlítást végezhessünk. A két legegyszer˝ubb leíró talán az atomok számából illetve a kötések számából képzett számok. 3.6. Definíció (Atomszám leíró):
Vegyünk egy G molekulagráfot, a hozzá tartozó
atomszám leíró: δatomCount := |V (G)| / 3.7. Definíció (Kötésszám leíró): Vegyünk egy G molekulagráfot, a hozzá tartozó kötésszám leíró: δbondCount := |E(G)| / Egy fokkal komplexebbek az atomstatisztika és az újraindexelési leírók. 3.8. Definíció (Atomstatisztika leíró): Vegyünk egy G molekulagráfot, a hozzá tartozó atomstatisztika leíró a következ˝o tömb: δatomStatistics [0] := max{atomicN umber(u)|u ∈ V (G)} ∀i ∈ [1..n] : δatomStatistics [i] := |{u|u ∈ V (G) és atomicN umber(u) = i}| Ahol n a periódusos rendszerben szerepl˝o elemek száma, atomicN umber(atom) pedig olyan függvény, ami egy atomhoz az elem rendszámát rendeli hozzá. / 27
3.9. Definíció (Újraindexelési leíró): Vegyünk egy G molekulagráfot, a hozzá tartozó újraindexelési leíró a következ˝o tömb: ∀u ∈ V (G) : δreindexing [indexOfG (u)] := ν(indexOfG (u)) Ahol ν(i)-t úgy kapjuk, hogy:
a) rendezzük V (G)-t az atomok rendszáma szerinti csökken˝o sorrendbe, b) indítsunk V (G) elemein mélységi vagy szélességi bejárást, döntési helyzetben a reprezentáció sorrendje szerint választjuk a következ˝o atomot, c) ν(i) := ahányadikként elértük az i. csúcsot a bejárás során. /
A 3.9-es definícióból is látszik, hogy a leírók képzése valamelyest az egyéni szabadságra és ízlésre van bízva, hiszen ν-t máshogyan is meghatározhattuk volna. Konstruálása két egyszer˝u megfigyelés alapján történt : egyrészt a nagyobb rendszámú atomok jellemz˝oen ritkábban fordulnak el˝o, másrészt a SMILES-ban (lásd 3.1.2.) megjelen˝o bejárás által biztosított sorrendiség tapasztalataink szerint nagyon er˝os „implicit” heurisztika, és ha nem ennek megfelel˝oen adjuk meg az bemenetet (példáért lásd 7.3-at), akkor a „naiv” algoritmus nagyon sok olyan illesztést próbál meg elvégezni, amit nem vezet eredményere. A VF2 és QuickSI algoritmusokban ez a gyenge pont nem található meg, hiszen o˝ k mindenképpen az eddigi parciális izomorfizmusban szerepl˝o atomok szomszédai közül választanak. Készíthetünk még bonyolultabban reprezentálható leírókat is, például a kötésstatisztikát. 3.10. Definíció (Kötésstatisztika leíró): Vegyünk egy G molekulagráfot, a hozzá tartozó kötésstatisztika leíró a következ˝o tömbök tömbje (∀u ∈ V (G)):
• δbondStatistics [indexOfG (u)][0] := u egyes kötéseinek száma; • δbondStatistics [indexOfG (u)][1] := u kettes kötéseinek száma; • δbondStatistics [indexOfG (u)][2] := u hármas kötéseinek száma; • δbondStatistics [indexOfG (u)][3] := u aromás kötéseinek száma;
28
• δbondStatistics [indexOfG (u)][4] := u egyéb kötéseinek száma. / Bár igaz, hogy mi els˝osorban olyan molekulákkal foglalkozunk, ahol az egyes atomok kötésszáma kicsi (jellemz˝oen ∆ = 4), a 3.10-es leíró mégis nagyon hasznos tud lenni, és jó heurisztikát lehet vele képezni. Készíthetünk ezen túl úgynevezett környezet alapú leírókat. Ebben az esetben az egyes atomok valamilyen sugarú környezetét – az abban található kötéseket és atomokat – próbáljuk egy számmal vagy számhalmazzal jól leírni. Ebben a diplomamunkában mi csak az 1-sugarú környezetekkel, másképpen nevezve csillagokkal foglalkoztunk. 3.11. Definíció (Csillag): Vegyünk egy G molekulagráfot, a benne található atomokhoz tartozó csillagok alatt a következ˝o részgráfokat értjük: ∀u ∈ V (G) : S(u) := ({u} ∪ {v|(u, v) ∈ E(G)}, {(u, v)|(u, v) ∈ E(G)}) 3.12. Definíció (Egyedi csillag leíró):
/
Vegyünk egy G molekulagráfot, a hozzá tartozó
egyedi csillag leíró a következ˝o tömb (∀u ∈ V (G)): δindividualStars [indexOfG (u)] :=
Y
bondT oP rime(e) ·
e∈E(S(u))
Y
atomT oP rime(v)
v∈V (S(u))
Ahol atomT oP rime : L → N és bondT oP rime : W → N az atom- és kötéscímkékehez egy-egy prímszámot rendel˝o függvények, amelyek injektívek és értékkészletük diszjunkt (tehát például ha az egyes kötéshez hozzárendeli a bondT oP rime a 2-t, akkor az atomT oP rime sem rendelheti már 2-t semmilyen atomhoz). / A csillag leíró konstrukciójának magyarázata egyszer˝u : a feladat során azt szeretnénk majd gyakran eldönteni, hogy egy csillag része-e vagy egyenl˝o-e egy másikkal. Ebben az esetben célszer˝u ezt a döntési eljárást minél könnyebbé tenni. A definiált csillag leíró ezt lehet˝ové is teszi, ugyanis a prímválasztások és a konstrukció miatt a tartalmazás egy maradékos osztással eldönthet˝o – ha nulla a maradék, akkor része, ha más, akkor nem. A leírók egyik altípusát a szakirodalom ujjlenyomatnak (fingerprint) [6] nevezi. Ezek a leírók nem mások, mint el˝ore megadott hosszúságú bitsorozatok, ahol az adott sorszámú bit egy adott tulajdonság meglétét vagy hiányát jelzi. Mivel a ujjlenyomatok hossza rögzített, ezért általában valamilyen hashelési eljárás is belekerül az azt el˝oállító eljárásba. Az ilyen 29
típusú leírók használata nagyon elterjedt, egyrészt azért, mert könny˝u ellen˝orizni a nekünk kell˝o tulajdonságokat (egyszer˝u bitm˝uveletekr˝ol van szó), másrészt mert kevés memória használatával tudunk akár az egész molekulára jellemz˝o tulajdonságokat eltárolni. Az egyedi csillag leíró egyik nagy hátránya például az, hogy nem mond semmit a molekula egészér˝ol, csakis az egyes atomokról. Viszont könnyen készíthetünk a csillagokról egy ujjlenyomatot, például az alábbi módon. 3.13. Definíció (Csillag ujjlenyomat leíró): Vegyünk egy G molekulagráfot, a hozzá tartozó csillag ujjlenyomat leíró olyan k hosszú bitsorozat, ahol csak a u ∈ V (G) : δstartsF ingerprint [δindividualStars [indexOfG (u)]%k] index˝u bitek 1-ek, az összes többi bit 0, % pedig a maradékképzés m˝uveletét jelzi. Vegyük észre, hogy nem várható el, hogy célmolekula pontosan azokat a csillagokat tartalmazza, mint a lekérdez˝o (lehet, hogy annál b˝ovebbeket is tartalmaz). Ezért legalább a célmolekulák csillag ujjlenyomat leíróiban az összes olyan bitet is 1-esre kell állítanunk, amelyek azokhoz a csillagokhoz tartoznak, amelyeket a célmolekula csillagaiból valahány szomszédos (vagyis nem a ”középs˝o”) csúcs elhagyásával kapunk. / A környezet alapú leírókhoz hasonlóan képezhetünk út alapúakat is. Ebben az esetben az egyes atomokból valamilyen hosszúságú utakat igyekszünk számként reprezentálni. 3.14. Definíció (Egyedi út leíró): Vegyünk egy G molekulagráfot, a hozzá tartozó egyedi út leíró, legfeljebb p hosszú utakhoz, a következ˝o tömbök tömbje (∀u ∈ V (G)): ∀i ∈ [0..r − 1] : δindividualP aths [indexOfG (u)][i] := Y
atomT oP rime(v) ·
v∈V (P (u,i))
Y
bondT oP rime(e)
e∈E(P (u,i))
Ahol atomT oP rime és bondT oP rime ugyanolyan tulajdonságúak, mint a 3.11-es definícióban, r az u atomból kiinduló legfeljebb p hosszú utak számossága, P (u, i) pedig az u-ból kiinduló i. ilyen út. / Az út leíróból is könnyedén készíthetünk a csillagoknál látotthoz hasonló ujjlenyomatot. 3.15. Definíció (Út ujjlenyomat leíró):
Vegyünk egy G molekulagráfot, a hozzá tartozó
út ujjlenyomat leíró, olyan k hosszú bitsorozat, ahol csak a u ∈ V (G) : δpathsF ingerprint [δindividualP aths [indexOfG (u)]%k] 30
index˝u bitek 1-ek, az összes többi bit 0, % pedig a maradékképzés m˝uveletét jelzi. /
3.5.
El˝oszurések ˝
Korábban beláttuk, hogy a vizsgált probléma komplexitása nagy, ráadásul sokszor kell a kérdést megválaszolnunk (minden egyes lekérdez˝o-cél molekula párra). Kézenfekv˝o, hogy ha a vizsgálandó molekulapárok n · M számát bármilyen egyszer˝u módszerrel csökkenteni tudjuk, akkor az a program futásai idejében szignifikáns javulásként jelenhet meg. Ezt az eljárást hívják el˝osz˝urésnek (screening) [6]. Az el˝osz˝urés lényege, hogy valamely gyorsan és könnyen eldönthet˝o tulajdonság alapján megállapítsuk, egyáltalán lehetséges-e, hogy az adott lekérdez˝o molekula részstruktúrája legyen az adott célmolekulának. Vegyük a legegyszer˝ubb el˝osz˝urést: ha a lekérdez˝o molekula több atomból áll, mint a cél, akkor biztos, hogy nem részstruktúrája annak. Az ilyen „biztos, hogy nem” állítások összessége adja az el˝osz˝urési eljárást. Meglep˝o lehet, de valós alkalmazásokban már az említett atomszám ellen˝orzés is nagyon fontos tényez˝o. Gondoljunk bele, hogy ha van egy több millió molekulát tartalmazó adatbázisunk, amiben szeretnénk egy 100 atomból álló molekulával részstruktúra-keresést végezni. A makromolekulák nagyon ritkák, így enélkül az el˝osz˝urés nélkül az algoritmus minden egyes apró molekula esetén végigfuttatná az izomorfizmus-számlálást, és nullát adna vissza. Míg ha élünk ezzel az el˝osz˝uréssel, akkor tudhatjuk, hogy ilyen esetekben biztos nulla lesz az eredmény, és mehetünk tovább, nem kell a költséges ellen˝orzést elvégeznünk. Mi az alább felsorolt öt egyszer˝u, a korábban definiált leírókkal (lásd 3.4.) könnyen eldönthet˝o el˝osz˝urést alkalmaztuk: def.
1. Atomszám sz˝urés ⇐⇒ a lekérdez˝o molekulában legfeljebb annyi atom legyen, mint a célmolekulában – Atomszám leíróval (3.6. definíció) dönthet˝o el. def.
2. Atomstatisztika alapú sz˝urés ⇐⇒ minden, a lekérdez˝o molekulában el˝oforduló atomtípusból legalább annyi legyen a célmolekulában is – Atomstatisztika leíróval (3.8. definíció) dönthet˝o el. 31
def.
3. Kötésszám sz˝urés ⇐⇒ a lekérdez˝o molekulában legfeljebb annyi kötés legyen, mint a célmolekulában – Kötésszám leíróval (3.7. definíció) dönthet˝o el. def.
4. Csillag alapú sz˝urés ⇐⇒ amely csillagok megtalálhatóak a lekérdez˝o molekulában, legalább azok (vagy azok b˝ovített változatai) megtalálhatóak legyenek a célmolekulában is – Csillag ujjlenyomat leíróval (3.13. definíció) dönthet˝o el. def.
5. Út alapú sz˝urés ⇐⇒ amely utak megtalálhatóak a lekérdez˝o molekulában, legalább azok megtalálhatóak legyenek a célmolekulában is – Út ujjlenyomat leíróval (3.15. definíció) dönthet˝o el.
3.6.
Heurisztikák
Az egyes algoritmusokhoz használhatunk bizonyos heurisztikákat, amelyekkel jó esetben csökkenthetjük a visszalépéses keresés lépésszámát. A heurisztikák egyrészt az algoritmus viselkedését befolyásolhatják (melyik ágakat járja be el˝oször a keresési fában), másrészt a döntési eljárást (például plusz vágási feltételekkel). Mi az alább felsorolt hét egyszer˝u, a korábban definiált leírókkal (lásd 3.4.) könnyen megvalósítható heurisztikát alkalmaztuk:
def.
1. Újraindexelés a célmolekulában ⇐⇒ a célmolekulában ne a reprezentáció szerinti következ˝o atomot próbáljuk meg illeszteni, hanem a 3.9-es definíció szerinti következ˝ot. def.
2. Újraindexelés a lekérdez˝o molekulában ⇐⇒ ua., mint az el˝obbi, csak a lekérdez˝o molekulára. def.
3. Kötésszám egyeztetés ⇐⇒ ha a lekérdez˝o molekulából az izomorfizmusba bevenni kívánt atom kötésszáma nagyobb, mint a célmolekulából választott atomnak, akkor tudhatjuk, hogy az illesztés nem jó, hiszen nem fogunk tudni minden szomszédot bevenni a leképezésbe – Kötésszám leíró (3.7. definíció) alapján eldönthet˝o. def.
4. Kötéstípus egyeztetés ⇐⇒ ha a lekérdez˝o molekulából az izomorfizmusba bevenni kívánt atomnak valamilyen típusú kötésb˝ol többje van, mint a célmolekulából választott 32
atomnak a megfelel˝o kötéstípusból, akkor az illesztés biztosan nem jó – Kötésstatisztika leíró (3.10. definíció) alapján eldönthet˝o. def.
5. Csillag egyeztetés ⇐⇒ ha a lekérdez˝o molekulából az izomorfizmusba bevenni kívánt atom csillaga nem része a célmolekulából választott atom csillagjának, akkor az illesztés biztosan nem jó – Csillag leíró (3.12. definíció) alapján eldönthet˝o. def.
6. Út egyeztetés ⇐⇒ ha a lekérdez˝o molekulából az izomorfizmusba bevenni kívánt atomból kiinduló utak közül legalább egy nem található meg a célmolekulából választott atomból induló utak között, akkor az illesztés biztosan nem jó – Út leíró (3.14. definíció) alapján eldönthet˝o. def.
7. Elérhet˝oség-ellen˝orzés ⇐⇒ a „naiv” megközelítés (lásd 3.3.1.) használatakor alapesetben sorrendben próbáljuk az egyes lekérdez˝o molekulabeli atomokat bevonni az aktuális parciális izomorfizmusunkba. Ekkor mindig ellen˝oriznünk kell, hogy az adott atomot bevettük-e már korábban az izomorfizmusba vagy sem. Lehet˝oségünk van azonban egyfajta „rendelkezésre-állási tömb” definiálására, amely egy egyszer˝u BOOLEAN tömb, amelyben TRUE van azokon az indexeken, amely index˝u atomot még nem vettük be az izomorfizmusba, ezután pedig egyszer˝uen azok közül választjuk a soron következ˝o atomot, amely még egyáltalán lehet, elkerülve ezzel egy költségesebb ellen˝orzést.
33
4.
Fejleszt˝oi dokumentáció
Ebben a fejezetben az implementáció lépéseit és a tervezési döntéseket részletezzük. A program f˝o célja különböz˝o algoritmusok hatékonyságának egymáshoz viszonyított vizsgálata, a keretrendszer ennek fényében lett kialakítva. F˝o szempont volt ezen kívül az esetleges kés˝obbi újrahasznosítás, b˝ovítés, programkönyvtárként való felhasználás lehet˝oségét szem el˝ott tartani a komponensek interfészeinek kialakításakor [3].
4.1.
A program felépítése
9. ábra. A program felépítésének legfels˝o szintje A program keretének koncepciója (9. ábra) egyszer˝u : van egy „f˝o osztály”, amely tartalmazza a MAIN függvényt, és meghívja az adatfeldolgozó alrendszert, az pedig végrehajtja a tulajdonképpeni feladatot, használva a létrehozott JVM-et, és a megadott beállításokat. A C ONFIG egyke (singleton) [13] egy szabványos Java properties állomány [9] kezelését végzi, amelynek ugyanabban a könyvtárban kell lennie, mint a futtatott config.properties néven. Kódolása
UTF -8
JAR ,
legyen (tartalmának részleteir˝ol lásd a 7.1.
alfejezetet) A RUN L OG egyke végzi a program futásának naplózását. A napló nem folyamatosan készül, hanem ennek az osztálynak a bels˝o állapota a mindenkor érvényes naplózandó állapot, amely a program futásának végén egy fájlba íródik ki, a C ONFIG-ban megadottak szerint (lásd még 5.1.). 34
4.2.
Vezérlés
10. ábra. Az adatfeldolgozó alrendszer vázlata A program vezérlését a DATA P ROCESSOR egyke végzi. A C ONFIG-ból kiolvasott beállítások alapján létrehozza az I/O-ért felel˝os osztályokat, és összeköti o˝ ket a keresést elvégz˝o osztályokkal (10. ábra). A keresés végeztével az eredményt az I/O rendszeren keresztül kiírja, szintén a C ONFIG-ban beállított eredmény állományba.
4.2.1.
Input / Output
Az Input/Output alrendszer két, egymástól markánsan elválasztható interfésszel rendelkezik, mint az a 11-es ábrán jól látható. Az egyik dimenzió szerint direkt I/O-t végz˝o objektumok hozhatóak létre egy gyártón (factory) [13] keresztül, míg a másik irányban molekula-objektumokat (lásd 4.3.) tartalmazó adatpufferek [18] kezelhet˝oek. Tekintsük el˝oször a direkt Input/Outputot kezel˝o osztályokat. Az interfész dekompozícióból látszik, hogy minden I/O rendelkezik OPEN () és CLOSE () eljárásokkal, amelyek az adott csatorna megnyitását és bezárást végzik el. Az O UTPUT ezen túl rendelkezik egy VOID WRITE L INE (S TRING )
eljárással, amely egy sort (≈rekordot) ír ki. A bemenetnek
több, komplexebb m˝uvelettel kell rendelkeznie, hiszen a szolgáltatás is összetettebb. Az I NPUT interfész m˝uveletei: •
INT GET N UMBERO F I NPUTS () :
visszaadja a megnyitott bemeneten összesen elér-
het˝o molekulák számát; 35
36 11. ábra. Az I/O alrendszer osztálydiagramja
• S UPPORTS [] GET S UPPORTS () : az alrendszeren belül használt eljárás, amely kiszámolja a C ONFIG alapján meghatározott tartókat (3.4. és 3.5. definíciók); • M OLECULE W ITH D ESCRIPTORS READ N EXT () : felolvassa a következ˝o molekulát a bemenetb˝ol; •
VOID SEEK ( INT ) :
a 4.3-ban kifejtett okok miatt a keresés pufferezett bemeneten
zajlik, ezért nagy bemenetszám esetén lesznek olyan molekulák, amit többször kell felolvasnunk. Az ehhez szükséges seekelést végzi el ez az eljárás; •
VOID SET F ILTER M OLECULE (M OLECULE W ITH D ESCRIPTORS ) :
beállítja a sz˝ur˝o-
molekulát. Csak adatbázisok esetén használt jelenleg, ott az adatbázisrendszer felé küldött lekérdezést módosítja, fájlok esetén nem csinál semmit ez az eljárás.
Az O UTPUT-nak jelenleg egy megvalósítása készült el, amely fájlba írja ki a megfelel˝o sorokat. Ezt használja a program az eredményfájl (lásd 4.2.2.) és a naplófájl (lásd 5.1.) létrehozására. Az I NPUT-nak két megvalósítása készült el: fájlból- illetve adatbázisból olvasás. Az adatbázisból olvasást igyekeztünk nem rendszerspecifikusra tervezni. Célunk az volt, hogy bármilyen JDBC driver esetén az adatbázis-elérést és -m˝uködést biztosítsuk. Ezt nem sikerült maradéktalanul elérnünk, a részleteket az 5.4-ben tárgyaljuk. Az IOFACTORY gyártó két osztályszint˝u függvénnyel rendelkezik, amelyek I NPUT vagy O UTPUT interfészt megvalósító osztályt adnak vissza. I NPUT esetén paraméterként várja annak típusát, nevét és egyéb paramétereit; O UTPUT esetén a típusát és a nevét. Mivel az O UTPUT-nak egy megvalósítása készült el, ezért típusának kötelez˝o értéke a I NPUT esetén elvileg bármikor lehetséges
FILE
vagy
DATABASE
FILE .
típus létrehozására. A
gyakorlatban azonban lekérdez˝o molekulák esetén csak a fájlból olvasást teszteltük, a célmolekulák adatbázisa lehet fájl vagy konkrét adatbázis. Fontos tervezési döntés volt, hogy a két bemenetet pufferez˝o osztály (Q UERY B UFFER, TARGET B UFFER) nem egy közös interfészb˝ol származik [3]. Bár két függvényük szinte azonos, használatuk annyira különböz˝o és teljesen más funkciót látnak el, hogy a közös
37
o˝ sosztály félrevezet˝o lehetne. Mindkét puffer rendelkezik
INT GET S IZE ()
függvénnyel,
amely visszaadja az összes, a puffer által elérhet˝o molekulák számát – tehát nem a puffer jelenlegi feltöltöttségét vagy maximális méretét adja vissza, hanem azon molekulák számosságát, amik a puffer által elérhet˝oek. Például ha a bemenetben 10.000 molekula van, a puffer mérete pedig 500, akkor mind a 10.000 molekula elérhet˝o a puffer által, csak nem egyszerre. A M OLECULE W ITH D ESCRIPTORS GET ( INT INDEX ) függvény adja vissza a puffer által elérhet˝o index-edik molekulát. Ha az éppen nincs a pufferben, akkor betölti (ehhez kellhet a korábban definiált SEEK), ha pedig megtalálható a pufferben, akkor csak visszaadja, bels˝o állapotváltozás nélkül. A célmolekulák puffere ezen kívül rendelkezik egy VOID SET Q UERY (M OLECULE W ITH D ESCRIPTORS ) eljárással, ez gyakorlatilag egy interfész-adapter [13] a keresési alrendszer felé, ami közvetlenül nem éri el az I NPUT-ot, csak a puffereken keresztül. A 12-es ábrán láthatjuk az adatfeldolgozó rendszer m˝uködésének alapötletét, amely szerint a DATA P ROCESSOR egyke létrehozza a célmolekulák pufferét. Ez a létrehozás során feltölti önmagát a puffer maximális méretére, amelyet a C ONFIG-ban tudunk meghatározni. Ezután a TARGET B UFFER és a hozzá tartozó I NPUT pihen˝oállapotba kerül. Ugyanez a folyamat eljátszódik a lekérdez˝o molekulák pufferével is. Természetesen ha a puffer mérete nagyobb lenne, mint a belekerül˝o molekulák száma, akkor is megáll a puffer feltöltése. Ezután a DATA P ROCESSOR inicializálja a keresést lebonyolító egykét, és átadja neki a két
12. ábra. A DATA P ROCESSOR m˝uködése
38
feltöltött puffert. A keresés végeztével visszakap egy számhármasokból álló listát (lásd 4.2.2.).
4.2.2.
Keresés
A keresési alrendszer (13. ábra) kifelé egy egyszer˝u interfésszel rendelkezik: a S EARCHER egykével. Ezen objektum létrejöttekor a C ONFIG-ban beállított értékek szerint, a S CREEN FACTORY és A LGORITHM FACTORY gyártókkal létrehoz egy el˝osz˝urést végz˝o (lásd 3.5.) objektumot és egy, a feladatot (3.2. definíció) megoldó objektumot. El˝osz˝ur˝o objektumból három fajta van:
i) P LAIN S CREEN : nem végez semmilyen el˝osz˝urést, bármilyenek legyenek a beállítások (a gyártó PLAIN paraméter esetén hoz ilyet létre); ii) S UB S TRUCTURE S CREEN : a 3.5-ben definiált el˝osz˝urések közül elvégzi azokat, amelyeket beállítottunk a C ONFIG-ban (a gyártó SUB paraméter esetén hoz ilyet létre); iii) DATABASE S UB S TRUCTURE S CREEN : a 3.5-ben definiált el˝osz˝urések közül elvégzi azokat, amelyeket beállítottunk a C ONFIG-ban, kivéve az atom- és kötésszám alapú sz˝urést, mert azokat már elvégezte az adatbázisrendszer (a gyártó DATABASE vagy DB
paraméter esetén hoz ilyet létre).
Algoritmusból ötfélé használható (ebb˝ol hármat implementáltunk a diplomamunka keretében) :
i) NAIVE (lásd 3.3.1.): A „naiv” algoritmus megvalósítása, a gyártó NAIVE vagy NAÏVE paraméter esetén hoz ilyet létre. ii) VF2 (lásd 3.3.3.): A VF2 [7] algoritmus megvalósítása, a gyártó
VF 2
paraméter
esetén hoz ilyet létre. iii) Q UICK SI (lásd 3.3.4.): A QuickSI [31] algoritmus megvalósítása, a gyártó QUICKSI paraméter esetén hoz ilyet létre. 39
40 13. ábra. A keresési alrendszer osztálydiagramja
iv) U LLMANN (lásd 3.3.2.): Az Ullmann-algoritmus [35] ChemAxon Kft. által biztosított egyik megvalósítása, valójában a Marvin programcsomagban található CHEMAXON . MARVIN . MODULES .S UBSTRUCTURE S EARCH osztály köré épített adapter, a gyártó ULLMANN paraméter esetén hoz ilyet létre. v) U LLMANN B (lásd 3.3.2.) : Az Ullmann-algoritmus ChemAxon Kft. által biztosított másik, több keresési funkciót nyújtó, univerzális megvalósítása, a JChem programcsomagban található
CHEMAXON . SSS . SEARCH .M OL S EARCH
osztály köré épített
adapter, a gyártó ULLMANNB paraméter esetén hoz ilyet létre.
A S EARCHER visszatérési értéke számhármasok listája. A számhármasokat egy immutable (nem változó bels˝o állapottal rendelkez˝o) [3, 16] osztály tárolja, amelyet T RIAD-nak neveztünk el. A számhármas felépítése a következ˝o : az els˝o szám megmondja a lekérdez˝o molekula indexét a bemenetben (tehát, hogy hányadik sorban található a lekérdez˝o állományban), a második szám megmondja a célmolekula indexét a bemenetben (tehát, hogy az adott állományban hányadik sorban található vagy hogy az adatbázisban milyen azonosítóval rendelkezik), a harmadik szám megmondja, hogy hány izomorfizmus függvény (3.2. definíció) létezik a két molekula között. Csak azokat a számhármasokat tároljuk, ahol a harmadik szám nagyobb, mint nulla. Ha csak az izomorfia megléte a kérdés, akkor a harmadik szám 1, ha fennáll a részgráf-izomorfia, 0 különben. A 14-es ábrán láthatjuk a keresés m˝uködésének elvét. Miután a 12-es ábra alapján megkapta a lekérdez˝o- és célmolekulákat tartalmazó puffereket, azokon végigiterál. Méghozzá úgy, hogy minden egyes lekérdez˝omolekula esetén megvizsgáltat minden célmolekulát a C ONFIG alapján legyártott algoritmussal, ha azt az el˝osz˝urés során továbbengedtük. A két puffer természetesen az egyes molekulák visszaadása el˝ott végezhet olyan m˝uveletet, amely a saját bels˝o állapotát módosítja : akkor, ha az lekért molekula nincs éppen benne a pufferben. A keresés végén az egyke rendezi a számhármasokból álló listát, úgy, hogy el˝oször az els˝o, majd a második szám szerint növekv˝o legyen a sorozat. A konstrukció miatt az els˝o és második számok párjai maximum egyszer fordulhatnak el˝o, a harmadik szám pedig pozitív.
41
14. ábra. A S EARCHER m˝uködése
4.3.
Molekulák reprezentációja
Mint láthattuk, a molekulák számítógépes reprezentációja általában gráfokként történik (3.1. definíció). Mivel él- és csúcscímkézett, ritka gráfokról van szó, így kézenfekv˝o az éllistás ábrázolás [8]. Nekünk két reprezentáció állt rendelkezésünkre: a ChemAxon Kft. által fejlesztett megvalósítás, amely a publikus könyvtárukban megtalálható (CHEMAXON . STRUC .M OLECULE), és egy sokkal egyszer˝ubb, SMILES (lásd 3.1.2.) importálásra alkalmas megvalósítás, amely a Speciális algoritmusok és adatstruktúrák tantárgy gyakorlatán kit˝uzött beadandó feladathoz volt biztosítva. Mivel mindkét reprezentáció a birtokunkban volt, kézenfekv˝onek t˝unt a diplomamunka keretében ezek összehasonlítása is. Ennek érdekében bevezettünk egy façade [13] rendszert, amely a molekulák, az atomok és a kötések konkrét reprezentációját rejti el. Emellé társítottunk egy gyártót, amely a C ONFIG-ban meghatározott megvalósítást fogja létrehozni a façade mögött. Ennek következtében a 15-ös ábra nem teljes, mert hiányoznak róla ezen façade konkrét megvalósításai, amelyek: • S IMPLE M OLECULE, S IMPLE M OL ATOM, S IMPLE M OL B OND hármas, amelyek az „egyszer˝u” reprezentációt írják le; 42
15. ábra. A reprezentáció osztálydiagramja a leírókkal
43
• C HEM A XON M OLECULE, C HEM A XON M OL ATOM, C HEM A XON M OL B OND hármas, amelyek adapterként viselkednek az általunk létrehozott façade és a konkrét ChemAxonos implementációk között.
Úgy érezzük, hogy a façade-ok m˝uveletei nem szorulnak magyarázatra a ligand kifejezést tartalmazók kivételével, ugyanis az itt használt ligand kifejezés nem esik egybe a kémiában, biokémiában használt kifejezéssel: ligand alatt mi bármely szomszédos atomot értjük. Azaz egy atom i. ligandja az a reprezentációban i. kötésének másik végén lév˝o atomot jelenti. Ennek megfelel˝oen a ligandIndex az adott atom adott ligandjának indexe a reprezentációban. A M OLECULE W ITH D ESCRIPTORS osztály egy kompozíció (composition) [13], amely egy molekulát (pontosabban M OLECULE FACADE-ot) és a hozzá tartozó leírókat (lásd 3.4., 4.4.) fogja össze egyetlen objektummá. Kinyerhet˝o bel˝ole a molekula objektum, bármelyik leíró, illetve adatbázis-kompatibilitási okok miatt a molekula azonosítója – ez azonosítja az adatbázisban vagy a fájlban egyértelm˝uen a molekulát sorszám alapján. Eljárásként lett megvalósítva benne az adatbázis-hatékony QI-sorozat (3.3. definíció) létrehozása. Mivel a reprezentációs alrendszer nagy részét (a façade-ot, a kompozíciót, az egyes leírókat) sok különböz˝o helyen kell direktben használnunk a programban, ezért ezt az alrendszert nem lehet olyan élesen körülhatárolható interfésszel ellátni, mint például az I/O-t vagy a keresést végz˝o alrendszereket [27]. Egyértelm˝u, hogy a M OLECULE W ITH D ESCRIPTORS memóriaigénye nagy lehet. Ha sok molekulával kell a programunknak foglalkoznia, akkor el˝obb-utóbb beleütközünk a hardveres korlátokba. Emiatt vált szükségessé a bemenetek pufferezetté tétele. A megfelel˝o pufferméret kiválasztása természetesen konfiguráció függ˝o. Jelenleg a pufferek úgy m˝uködnek, hogy kezdetben teljesen feltölt˝odnek molekulákkal, és amikor a keresési alrendszer olyan index˝u molekulát kér t˝olük, amely nincs éppen a memóriában, akkor a C ONFIG-ban megadott százalékot leürítik a pufferb˝ol, majd feltöltik, úgy, hogy az els˝o elem lesz a lekért molekula, utána pedig sorban a többi, amíg a puffer ismét meg nem telik.
44
4.4.
Molekulaleírók, el˝oszurések ˝ megvalósítása
Mint a 15-ös ábrán jól látható, az összes leíró (lásd 3.4.) egy közös o˝ sb˝ol, egy generikus interfészb˝ol, a D ESCRIPTOR
-b˝ol származik. Technikai okokból létrehoztunk egy
ENUM
D ESCRIPTORT YPE típust, amelyben a felsorolás értékeihez a konkrét
leíró implementációkat rendeljük hozzá és hozzuk létre a megfelel˝o paraméterezéssel. Ennek köszönhet˝oen a M OLECULE W ITH D ESCRIPTOR osztályban lehet˝ové vált a leírók E NUM M AP-ben való tárolása, és az ENUM, Javaról lévén szó, egyfajta gyártó-primitívként is tud m˝uködni. A leírók közös jellemz˝oje, hogy bels˝o állapotukat egy, a generikus típusparaméterb˝ol származó objektum írja le, amely bels˝o állapot lekérdezhet˝o. Így lehet˝ové tettük azt, hogy az egyes molekulákhoz tartozó leírókat a program futása során minél kevesebbszer kelljen kiszámolni, pontosabban: amíg a molekula a memóriában van, addig ne kelljen soha újraszámolni. A leírók egyik altípusa az összehasonlítható leírók (C OMPARABLE D ESCRIPTOR ). Ezek közös tulajdonsága, hogy önmaguk típusával vett részbenrendezést definiáltunk rajtuk. Pragmatikusan tekintve az összehasonlítható leírókkal végzünk el˝osz˝urést (lásd 3.5.), és a nem összehasonlíthatóakkal képzünk heurisztikákat (lásd 3.6.). Ez a valóságban azonban nem teljesen igaz, mert például a kötésszám leíróval (B OND C OUNT D ESCRIPTOR) sz˝urést is végzünk, és heurisztikaként is felhasználjuk. Az mindenesetre kijelenthet˝o, hogy amely leíróval el˝osz˝urést szeretnénk végezni, az biztos, hogy összehasonlító leíró. Emiatt a M OLECULE W ITH D ESCRIPTOR osztályban szükségünk volt a kétféle leíró megkülönböztetésére, ezért lett két metódus létrehozva, egyik bármely, a másik csak az összehasonlítható leírókat adja vissza. Technikai okokból, a generikus típusok miatt ezt csak „nem ellen˝orzött figyelmeztetés”-sel („unchecked warning”) tudtuk megoldani. Az elvégzett ellen˝orzések miatt azonban biztos, hogy úgynevezett heap pollution nem lép fel, így ennek figyelmen kívül hagyása nem jelenthet gondot (részletekért lásd [17]-et). A 3.12-es és 3.14-es definíciókban említett diszjunkt értékkészlet˝u injektív függvényeket a P RIMES adattípus segítségével valósítottuk meg. Az osztály immutable, olyannyira, hogy
45
bels˝o állapota és két függvénye is osztály szint˝u, statikus, amely függvények az egyes atom- illetve kötéstípusokhoz rendelnek egy-egy prímszámot. Látható, hogy a QIS EQUENCE leíróhoz, amely értelemszer˝uen a QI-sorozatot (3.3. definíció) megvalósító leíró, kapcsolódik egy külön csomag, amelynek részletezésére UML szintjén nem tértünk ki. A csomag kulcsolt adatszerkezetek (M AP-ek) segítségével, és néhány segédosztállyal valósítja meg a tartók kiszámolását és a QI-sorozat elemeinek, azok kiegészít˝o adatainak kezelését. A fentiek után az el˝osz˝urések elvégzése könnyen megtehet˝o : mint említettük, minden el˝osz˝urést végz˝o leíró összehasonlítható leíró. Ezek kritériumaként a részbenrendezés megvalósítását t˝uztük ki, nem volt más dolgunk, mint olyan részbenrendezést definiálni, amelyre: Q T =⇒ δQ ≤ δT , ahol Q a lekérdez˝o-, T pedig a célmolekula, δQ és δT pedig a hozzájuk tartozó összehasonlítható leírók. Nyilvánvaló, hogy ez számunkra használható lesz (ha a jobb oldal nem teljesül, akkor a bal oldal sem teljesülhet). Az öt megvalósított, el˝osz˝urést végz˝o leíróra ezek a rendezések informálisan a következ˝ok: i) ATOM C OUNT D ESCRIPTOR (3.6. definíció) : a természetes számokra vonatkozó rendezés; ii) B OND C OUNT D ESCRIPTOR (3.7. definíció): a természetes számokra vonatkozó rendezés; iii) ATOM S TATISTICS D ESCRIPTOR (3.8. definíció): a lekérdez˝o molekula tömbjének minden eleme legfeljebb akkora legyen, mint a célmolekula tömbjének megfelel˝o eleme; iv) PATHS F INGERPRINT D ESCRIPTOR (3.15. definíció), S TARS F INGERPRINT D ESCRIPTOR (3.13. definíció): legyen δQ és δT rendre a lekérdez˝o- és a célmolekula adott ujjlenyomata. Ekkor legyen: def.
δQ ≤ δT ⇐⇒ δQ &δT = δQ , ahol & a bitenkénti és m˝uveletét jelöli. 46
4.5.
Algoritmusok, heurisztikák megvalósítása
4.2.2-ben láttuk, hogy a programban a 3.3-ban tárgyalt négy algoritmus mindegyike használható, melyek közül az Ullmann-algoritmus (lásd 3.3.2.) két különböz˝o implementációját a ChemAxon Kft. biztosította számunkra. A 13-as ábrán láthatjuk, hogy az egyes algoritmusok mind egy közös interfészt valósítanak meg, melynek egy függvénye van. Ez a függvény két molekulát vár (leírókkal együtt) paraméterként, és visszaadja az izomorfizmusok számát. A „naiv” algoritmus (lásd 3.3.1.) megvalósítása a NAIVE osztály. Nem pontosan a korábbiakban tárgyalt algoritmus került megvalósításra, annak egy kicsit kifinomultabb változata. Illesztettünk például hozzá olyan heurisztikát, amelyet a többi implementációhoz nem: az elérhet˝oség-ellen˝orzést. Használata során egy külön
BOOLEAN
vektorban tároljuk a
még illeszthet˝o atomok indexeit, és csak ebb˝ol a tömbb˝ol választunk következ˝o atomot, ahelyett hogy költségesen ellen˝oriznénk, hogy már illesztve van-e. Természetesen ezt a tömböt is karban kell tartani, ami szintén jár némi többletköltséggel. Ez a legkevésbé absztrahált megközelítés, az implementációban rengeteg vezérlési elágazás található, amelyek a különböz˝o heurisztikák be/kikapcsolt állapota szerint módosítják a m˝uködést. A VF2 algoritmus (lásd 3.3.3.) megvalósítása a VF2 osztály. Az implementáció során igyekeztünk minél kevésbé eltérni a [7]-ben publikált eljárástól. A programozás során a gyakorlatban is igazolást nyert a kiegészít˝o információkat tartalmazó tömbök létjogosultsága, amelyek alapján a szomszédsági halmazt gyorsan ki tudjuk számolni. A diplomamunka korai mérései során azt tapasztaltuk, hogy a VF2 nem a t˝ole várt eredményeket produkálja. Azt vártuk, hogy ez a sz˝uk keresztmetszet a szomszédsági halmaz számolása lesz – tévedtünk, ugyanis a futási id˝o nagy részét a program a kiegészít˝o információkat tartalmazó tömbök karbantartásával töltötte. Ezen tömbök kezelését racionalizáltuk, és néhány plusz segédváltozóval meggyorsítottuk (a cikkben nem térnek ki implementációs részletekre, és a feladat módosítása miatt a kiegészít˝o információk kezelésén is módosítanunk kellett). Azt is megállapítottuk, hogy gyorsabb minden esetben újraszámolni a szomszédsági halmazt, mint eltárolni és mindig hozzátenni/elvenni bel˝ole az indexeket.
47
A QuickSI algoritmus (lásd 3.3.4.) megvalósítása a Q UICK SI osztály. Ez az algoritmus illeszthet˝o a legkevésbé az el˝ore definiált keretrendszerünkbe, leginkább a QI-sorozat leíró miatt, amelyhez nagyon speciális kiegészít˝o adatok szükségesek. A QI-sorozathoz szükségesek adatbázis-globális jellemz˝ok, amelyek kinyeréséhez megfelel˝oen módosítanunk kellett a többi alrendszert (I/O, reprezentáció). Az implementáció során megállapítást nyert, hogy a QuickSI algoritmus valójában egy teljesen új szemlélet˝u atomsorrendezést valósít meg, amely egyértelm˝uen illeszthet˝o a többi algoritmushoz is, és úgy hisszük, hogy sokat gyorsíthat rajtuk. Az ipari felhasználások számára fontos kérdésr˝ol van szó, hiszen egy cégnek nem mindegy, hogy teljesen újra kell írnia a keresési rendszert, vagy csak ki kell egészítenie az eddigit. Sajnos a kérdés beható vizsgálatára id˝o sz˝ukében nem volt lehet˝oségünk. Az Ullmann-algoritmus (lásd 3.3.2.) megvalósításai a U LLMANN és U LLMANN B osztályok. Mivel ezek az osztályok adapterek, így csak a saját adatstruktúrájukkal használhatóak. Tehát ezek az algoritmusok csak akkor m˝uköd˝oképesek, ha a program a ChemAxon-féle molekulareprezentációval fut – ez indokolja a façade-ban a GETA S C HEM A XON M OLECULE ()
függvény létét. Fontos megemlítenünk, hogy ez a két
implementáció nem pontosan ugyanazt a feladatot oldja meg, mint amit mi kit˝uztünk. A S UBSTRUCTURE S EARCH például nem m˝uködik nem összefügg˝o lekérdez˝o molekulákkal, míg a M OL S EARCH mindenképpen aromatizálja a molekulákat. Emiatt a futások eredményei nem teljesen ugyanazok a T RIAD-ok lesznek. Általánosan kijelenthet˝o, hogy a két ChemAxon Kft.-féle megvalósítás a diplomamunka keretében implementáltak által adott megoldások valamilyen részhalmazát fogja visszaadni. A mérési eredményeknél tehát ezt nem szabad figyelmen kívül hagynunk, ahogy azt sem, hogy ezek a megvalósítások sokkal univerzálisabbak, több, itt nem tárgyalt komplikációt figyelembe vesznek. Megjegyezzük továbbá, hogy ez a két osztály teljesen fekete doboz a diplomamunka szempontjából.
48
5.
Eredmények
Ebben a fejezetben részletezzük a korábban definiált algoritmusok (lásd 3.3., 4.5.) futási eredményeit. Megpróbáltuk ezeket az eredményeket úgy kiválogatni, hogy bemutassuk azokat a tipikus helyzeteket, amelyekben a részstruktúra-keresés el˝okerülhet. Minden esetben pontosan megadjuk a konfigurációt, amelyen az adott tesztek futottak. A célmolekulák adatbázisa az Egyesült Államok Rákkutató Intézete (National Cancer Institute – NCI) [30] által kiadott, 250.251 darab molekulát tartalmazó gy˝ujtemény volt [24], vagy annak valamely specifikált részhalmaza. A lekérdez˝o molekulák halmazai megtalálhatóak a mellékleten, informális definíciójuk az alábbi: • test_fullscan.smiles: egy darab molekulát tartalmaz, amely egyetlen szénatomból áll. Használatának célja az I/O sebesség mérése a majdnem teljes NCI gy˝ujtemény esetén; • test_set.smiles: az NCI gy˝ujtemény és különböz˝o részhalmazainak vizsgálata alapján kiválasztott 30 molekulát tartalmazza, amelyek reményeink szerint jól reprezentálhatják a tipikus felhasználások széles körét. Található benne kicsi, nagy, egyszer˝u és összetett molekula is. Az el˝osz˝urések alapján is széles spektrumot képviselnek : van olyan, amelyet majdnem a teljes gy˝ujteménnyel össze kell hasonlítani, és olyan is, amelyet kevesebb, mint száz molekulával; • test_set _db.smiles: az el˝oz˝o azon részhalmaza, amelyben azok a molekulák találhatóak meg, amelyek adatbázis alapú sz˝urés (lásd 5.4.) esetén legfeljebb 30.000 lehetséges célmolekulával rendelkeznek; • test_set _db _2.smiles: hasonló az el˝oz˝ohöz, csak a küszöbszám 1.000 célmolekula volt.
Egy számítógépes program futási idejének elemzése mindig rengeteg hibára ad lehet˝oséget. Igyekeztünk olyan módszereket alkalmazni, amelyek ezek közül minél többet 49
elkerülnek [40]. Id˝omérésre a Java által biztosított legfinomabb módszer választottuk (S YSTEM . NANOT IME ()), és mindig a legsz˝ukebb kódrészleteket mértük. Az egyes diagramokhoz tartozó teljes adatsorok megtalálhatóak a CD mellékleten a diagrams.ods, diagrams_db.ods, diagrams_db_2.ods fájlokban.
5.1.
Naplófájlok értelmezése
Ha a beállításoknál megadtuk, akkor a program futásáról készül egy naplófájl, amelynek formátuma XML [38]. Azért esett erre a választásunk, mert a napló feladata nem a program viselkedésnek elemzése, hanem a futási id˝o, és esetlegesen még néhány más produkált jellemz˝o kiértékelési lehet˝oségének biztosítása. Mivel XML-r˝ol van szó, ezért ez a napló könnyen konvertálható bármilyen áttekinthet˝o formátumba, akár egy egyszer˝u XSLT-vel is [37]. Ebben az alfejezetben a L EVEL .CONFIG naplózási szinttel elkészül˝o XML fájlt elemezzük. A finomabb szintekkel készül˝o naplófájlok futási id˝o mérésére nem alkalmasak (túl sok rész-információt tárolnak el, és torzítják a tényleges futási id˝ot). Mindenesetre a most kifejtett elnevezések alapján a finomabb információkat tároló címkék is könnyen értelmezhet˝oek, azok is „beszél˝o nevekkel” rendelkeznek. A fájl a szokásos XML fejléccel kezd˝odik. Ezután következik az aktuális futás beállításainak leírása, ez a < CONFIG > címke. Az ebbe ágyazott címkék egyesével leírják az adott beállításokat (lásd 7.1.1.), a bennük lév˝o szövegek pedig meghatározzák a futáskor érvényes értéküket. Ezután már a konkrét futás tulajdonságait leíró címkék következnek, jellemz˝oen két beágyazott címkével:
• < ACCESSCOUNT > : az adott címkével leírt programrészlet hányszor lett meghívva; • < FULLDURATION > : az adott címkével leírt programrészlet összesített futási ideje, nanoszekundum felbontással.
50
Az < INIT > címke írja le a program inicializálásával töltött részletet, míg az < OUTPUT > az eredményfájlba való kiírásával töltött id˝o. A < PROCESS > címke a feldolgozással töltött id˝o. Ezen belül a < TARGET R EAD > és < QUERY R EAD > beágyazott címkék értelemszer˝uen a cél- és lekérdez˝o molekulák beolvasásával töltött összes id˝ot jelzik. A < SEARCH > címke jelzi a ténylegesen a részgráfizomorfia eldöntésére fordított id˝ot a program futása során, de ebbe beleszámít a pufferek kezelésének (ürítésének, feltöltésének) ideje is, a kezdeti feltöltés kivételével. A kés˝obbiekben elemzett tesztesetekben mi a < SEARCH > tényleges futási idejére helyeztük a hangsúlyt. A diplomamunkának nem volt célja az I/O és a keretrendszer optimalizálása, ahogy az adatbázisrendszerek finomhangolása sem, mivel ezek minden esetben az adott környezet sajátosságainak részletes elemzése után válnának lehetségessé. Az egyes tesztek által generált naplóállományok megtalálhatóak a mellékleten a logs mappában, mellettük egy szöveges állomány, amelyben leírtuk, hogy melyik napló milyen futás során született. A naplófájl váza látható a Függelékben (7.4.).
5.2.
Tesztek futtatása
A tesztek futtatása során szerettünk volna minél pontosabb eredményeket kapni, ezért az a döntés született, hogy minden egyes tesztesetet egymás után tízszer futtattunk le, és az ezen futások alatt kapott futási id˝oket átlagoltuk. Mivel a naplófájlok egy-egy futás adatait írják le, szükségünk volt egy olyan keretre, amely elvégzi a futtatásokat, és utána a naplófájlokat összef˝uzi egymás után, a megfelel˝o kiegészítésekkel megt˝uzdelve. Ennek megsegítésére írtunk egy kis kiegészít˝o programot (a mellékleten a performance nev˝u könyvtárban található a forrása), amely ezt a feladatot végzi el: azaz a megadott paraméterekkel meghívja a készített programot, és a hívások végén a naplófájlokat egymás után f˝uzi, az egyes futásokat egy-egy új XML-címkébe téve. Ezen program segítségével döntöttük el azt is, hogy milyen el˝osz˝urési módszereket és milyen heurisztikákat fogunk használni a tesztek futtatása során – hiszen nyilvánvaló, hogy
51
az egyes algoritmusok más és más beállítások esetén fogják optimumukat nyújtani. Ennek megfelel˝oen az alábbi beállításokra esett választásunk:
• minden egyes futásnál a 3.5-ben definiált mind az öt el˝osz˝urést alkalmaztuk; • „naiv” algoritmus (lásd 3.3.1.) esetén alkalmazott heurisztikák (lásd 3.6.): ◦ újraindexelés a lekérdez˝o molekulán (REINDEX O N Q UERY = TRUE); ◦ elérhet˝oség-ellen˝orzés az algoritmus futása során (CHECK AVAILABILITY = TRUE); ◦ csillagok illeszkedésének ellen˝orzése az új illesztéseknél (MATCH S TARS = TRUE); ◦ kötésszám ellen˝orzése az új illesztéseknél (MATCH B OND C OUNT = TRUE); ◦ kötéstípus ellen˝orzése vagy nem ellen˝orzése az új illesztéseknél – mindkét beállítással futtattunk (MATCH B OND T YPES = TRUE/FALSE); ◦ újraindexelés a célmolekulán nem történt (REINDEX O N TARGET = FALSE); • VF2 algoritmus (lásd 3.3.3.) esetén alkalmazott heurisztikák: ugyanazok, mint „naiv” algoritmus esetén, de kiemeljük, hogy az elérhet˝oség-ellen˝orzés paramétere nem befolyásolja a VF2 algoritmus futását; • QuickSI algoritmus (lásd 3.3.4.) esetén alkalmazott heurisztikák: ◦ csillagok illeszkedésének ellen˝orzése az új illesztéseknél (MATCH S TARS = TRUE); ◦ kötésszám ellen˝orzése az új illesztéseknél (MATCH B OND C OUNT = TRUE); ◦ kötéstípus nem ellen˝orzése (MATCH B OND T YPES = FALSE); 52
◦ adatbázis-hatékony QI-sorozat (3.3. definíció) használata vagy nem használata – mindkét beállítással futtattunk (CALCULATE O PTIMAL QIS EQUENCE = TRUE/FALSE) ◦ újraindexelés a lekérdez˝o molekulán – mindegy, hogy mire van állítva az értéke, mert mindenképp a QI-sorozat szerint fog az algoritmus illeszteni; ◦ újraindexelés a célmolekulán nem történt (REINDEX O N TARGET = FALSE); • az Ullmann-algoritmus reprezentációi a diplomamunka szempontjából fekete doboznak min˝osülnek, rájuk heurisztika megvalósítás nem történt, de feltételezhet˝o, hogy hasonló heurisztikákat alkalmaznak ezek a megvalósítások is.
Minden más érték a mellékleten található config.properties állományban beállított értéken volt. Megjegyezzük, hogy az adatbázis-hatékony QI-sorozat használatára/nem használatára els˝osorban azért került sor, mert mérni szerettük volna a QuickSI algoritmus teljesítményét adatbázis-hatékony és egyszer˝ubb módon meghatározott QI-sorozattal is. A programban a nem adatbázis-hatékony QI-sorozat a reprezentációban lév˝o molekulasorrendet figyelembe vev˝o Prim-algoritmus [8] alapján került meghatározásra. A továbbiakban az eredmények részletezésekor a következ˝o jelöléseket használjuk: Naive / T – „naiv” algoritmus kötésillesztéssel; Naive / F – „naiv” algoritmus kötéstípus illesztés nélkül; VF2 / T – VF2 algoritmus kötéstípus illesztéssel ; VF2 / F – VF2 algoritmus kötésillesztés nélkül; QuickSI / T – QuickSI algoritmus adatbázis-hatékony QI-sorozattal ; QuickSI / F – QiuckSI algoritmus nem adatbázis-hatékony QI-sorozattal ; Ullmann, Ullmann / B – a 4.2.2-ben meghatározott Ullmann-algoritmusok. Az olvasónak felt˝unhetett, hogy a megvalósításból kimaradtak az egyedi út leírók (3.14. definíció), használatukra sehol nem került sor. Ennek magyarázata az, hogy az egyedi út leírók választott reprezentációja rengeteg helyet igényel. A prímszorzat konstrukció miatt a még rövidnek mondható, öt hosszú utak eltárolása sem oldható meg LONG tömbökben, kénytelenek lennénk a
JAVA . MATH .B IG I NTEGER
53
osztályt használni – ahogy azt tettük
például a csillagok megvalósításánál is. Azonban, ha egy ilyen tömbben szeretnénk eltárolni minden egyes utat, akkor a tömb mérete már kis molekulák esetén is megabájtokban lenne mérhet˝o, és így valószín˝uleg többet ártana, mint amennyi hasznot hozna. Hiszen egy ilyen nagy objektum felépítése, kezelése, karbantartása, mentése és visszaolvasása adatbázisból nagy többletköltségekkel járna, olyan sokkal, amennyit a vele képzett heurisztika nem tudna javítani az algoritmusok futásidején.
5.3.
Algoritmusok eredményei
Az algoritmusok futásidejének vizsgálatát egy személyi számítógépen végeztünk, specifikációjának releváns része:
• Processzor: AMD Phenom II X6 1090T (6 processzor mag, ≈3,2 GHz órajel) • Memória: Corsair XMS3 DDR3 CL9 (4x2 GiB, 1333MHz) • HDD: WD5002AALX (S-ATA3, 32MiB cache) • OS: Window 7 Professional, 64-bit • JRE: 1.6.31, 64-bit
Az algoritmusok teljesítményének vizsgálatához a következ˝oképpen jártunk el: vettük valamely korábban definiált teszthalmazunkat, mint lekérdez˝o molekulákat, és az NCI adathalmazát, mint célmolekulák adatbázisát. A 250.251 molekulát szétosztottuk öt egyenl˝o részre, az egyes részekbe kerül˝o adatokat véletlenszer˝uen választva a teljes halmazból. Ezután az összes algoritmust futtattuk az öt részhalmazra, és az ezen futások által kapott eredményeket átlagoltuk. A szétosztásra azért volt szükség, hogy az I/O idejét minimalizálni tudjuk: a 250.251 molekula nem fért el a számítógép memóriájában, de 50.052 igen, így lehet˝oségünk volt egyszerre beolvasni az egyes részhalmazokat, ezzel elkerülve a pufferezettség által okozott futási id˝o torzulást (hiszen így egy-egy futás során a puffer egyszer feltölt˝odött létrejöttekor, és utána bels˝o állapota nem módosult).
54
16. ábra. Teljes teszthalmazra vonatkozó tesztek Az algoritmusok megvalósítása során végeztünk el˝oteszteléseket. Ezeket olyan adathalmazokkal végeztük el, amelyek célja az volt, hogy minél több különböz˝o speciális részgráfizomorfizmus esetet tartalmazzanak. Azaz ezek a tesztesetek nem a kémiai informatika gyakorlatában el˝oforduló tipikus kereséseket reprezentálják, hanem inkább egy matematikaiinformatikai robusztussági vizsgálatra voltak hivatottak. Ezen el˝otesztelések alapján azt tudtuk lesz˝urni, hogy az algoritmusok helyesen m˝uködnek, illetve nagyjából a cikkekben publikált eredmények alapján teljesítenek egymáshoz képest. Ezeket az eredményeket itt nem részletezzük, de megtalálhatóak a mellékleten. A 16. ábrán látható a teljes teszthalmaz (test_set.smiles) futása alapján kapott átlagolt eredménysor. Jól látszik, hogy a legjobban és legrosszabbul teljesít˝o algoritmusok futási ideje között kétszeres szorzó figyelhet˝o meg. Leggyorsabb az adatbázis-hatékony QI-sorozattal keres˝o QuickSI volt. Leglassabban a VF2 algoritmus teljesített, nem sokkal maradt el t˝ole az egyik Ullmannmegvalósítás sem. Az el˝otesztelések során ez a két algoritmus sokkal el˝okel˝obb helyen szerepelt, de mint említettük, azok nem gyakorlat-orientált tesztek voltak. A futási id˝ok relatív szórása minden esetben 7% alatt volt, tehát az átlag jól jellemzi a futási id˝ot.
55
17. ábra. A sz˝ukített teszthalmazra vonatkozó tesztek
18. ábra. A legsz˝ukebb teszthalmazra vonatkozó tesztek
56
A 17. ábrán látható a sz˝ukített teszthalmaz (test_set_db.smiles) futása alapján kapott átlagolt eredménysor. Az általunk implementált algoritmusok itt már sokkal kiegyenlítettebben teljesítenek, és mindegyikük gyorsabb a két publikus könyvtárból felhasznált megoldásnál. Felhívjuk a figyelmet arra, hogy míg az el˝oz˝o ábrán az Y-tengely értékei a [0-25] másodperc intervallumban mozogtak, itt csak a [0-9] másodpercb˝ol kerültek ki. Leggyorsabban itt is az adatbázis-hatékony QI-sorozattal keres˝o QuickSI teljesített. Megjegyezzük, hogy a különbség a kétfajta QuickSI között úgy t˝unik a gyakorlatban elhanyagolhatóan kicsi, ezért megfontolandó a nem adatbázis-hatékony változatot használni, hiszen ennél a változatnál az I/O valószín˝uleg gyorsabb lesz, mint a másiknál. Leglassabban az Ullmann-algoritmusok teljesítettek. Az átlagok relatív szórása minden esetben 30% alatt volt, valójában csak az Ullmann esetén volt 20% fölött. Ezen tesztek futtatása során meg is ismertük a mérés pontosságának határait : az els˝o és összes találat megtalálása külön tesztfuttatás volt, és a futási id˝ok szórása akkora volt, hogy az Ullmann algoritmus elvileg az összes találatot gyorsabban találta meg, mint az els˝ot – a hiba 0,56 másodperc, tehát ezt is figyelembe kell vennünk ennek az ábrának az értelmezésekor. A 18. ábrán látható a legsz˝ukebb teszthalmaz (test_set_db_2.smiles) futása alapján kapott átlagolt eredménysor. Látható, hogy itt már az algoritmusok sokkal közelebb teljesítenek egymáshoz – az Y-tengely itt már csak a [0-1,8] intervallumot mutatja. A leggyorsabbnak itt is a QuickSI-k bizonyultak, leglassabbnak az Ullmann implementáció. Azonban itt már nagyon kis id˝ointervallumokról volt szó, és az átlagok relatív szórása is jóval magasabb: a „naiv” algoritmus esetén 50-80% volt, míg a többi esetén 10% alatti. Az el˝obbi ábra esetén megfigyelhet˝o hiba itt is megjelenik: nagyjából 0,01 másodperc.
5.3.1.
Reprezentációs különbségek
Mint a korábbi fejezetekben kifejtettük, két különböz˝o molekula reprezentációval rendelkeztünk, és ezek egymáshoz viszonyított teljesítményét is mértük. Azt tudtuk megállapítani, hogy a két reprezentáció egymáshoz viszonyítva nem rendelkezik statisztikailag megállapítható viszonnyal. Teljesen rapszodikus volt, hogy mely tesztadatok esetén melyik teljesített jobban, nem lehetett disztingválni közöttük sem a molekulák 57
mérete sem azok komplexitása alapján. Az NCI adathalmazzal való tesztelés során a ChemAxon Kft. általi molekula ábrázolás átlagosan egy picit gyorsabb számolást tett lehet˝ové. I/O tekintetében azonban az egyszer˝ubb molekulaábrázolás 30-50%-kal gyorsabb beolvasást tett lehet˝ové. Ezek alapján kijelenthet˝o, hogy a cég által megvalósított, iparban is helytálló ábrázolásmód rengeteg el˝onnyel rendelkezik a mi egyszer˝ubb megvalósításunkhoz képest, hiszen amellett, hogy a gyakorlat szempontjából fontos esetekben picit gyorsabb, rengeteg olyan információt is tárol, ami a részstruktúra-keresés esetén nem kell, de általánosan a kémiai informatikai alkalmazások esetén igen. A beolvasással töltött hosszabb id˝ore pedig pontosan ez is az indok: sokkal több információt nyerünk ki a SMILES-ból az I/O folyamán, mint az egyszer˝u reprezentáció esetén.
5.3.2.
Következtetések
A futási eredményekb˝ol jól látszik, hogy az implementált algoritmusok átlagban jobban teljesítenek, mint a ChemAxon Kft. által publikált Ullmann-megvalósítások. Azonban ebb˝ol nem szabad messzemen˝o következtetéseket levonnunk, ugyanis azok az implementációk nem pontosan ugyanazt a feladatot oldják meg, mint a diplomamunka keretében programozottak. A ChemAxon-féle megvalósítások sokkal univerzálisabbak, kezelik például az implicit hidrogének jelenségét, a JChem programcsomagból való pedig az úgynevezett Markush struktúrákat is [5]. Ezen kívül ez a két megvalósítás több memóriát is használ, és nem csak az izomorfizmusok számát, de magukat a megfeleltetéseket is visszaadják index-tömbökként – ezt megtehetnék az általunk programozott megoldások is, több memória használatával és ez valószín˝uleg egy pici lassulást is eredményezne. Másrészr˝ol: az általunk megvalósított algoritmusok esetén 100.000 molekulát is tudtunk volna egyben kezelni, de az Ullmann-megvalósítások ennyi célmolekulával nem fértek el 4GiB memóriában.
58
A „naiv” algoritmus megtestesíti a középmez˝onyt, amelynél jobb eredmények egy ilyen egyszer˝u megközelítést˝ol, kevés heurisztikával nem is nagyon várhatóak el. A VF2 meglepetésünkre sok, véletlenszer˝u molekula esetén rosszul teljesített, de kevés, viszonylag nagy molekula esetén határozottan az élmez˝onybe tartozott. Ennek lehetnek implementációs indokai is, ilyen id˝oskáláknál már nagyon sok múlik a választott adatszerkezetek hatékonyságán, ahogy azok megfelel˝o kezelésén is. A QuickSI algoritmus nagyon jól teljesített. Az adatbázis-hatékony QI-sorozatok nem kerültek tökéletesen használatra, hiszen nem a teljes NCI adathalmaz alapján számoltuk ki o˝ ket, mindig csak az adott teszthalmaz alapján. Valószín˝usíthet˝o, hogy minél nagyobb a célmolekulák halmaza, annál szignifikánsabb a különbség az adatbázis-hatékony és nem adatbázis-hatékony QI-sorozatokat használó algoritmusok között. Az implementáció során felmerült kérdés egy új vizsgálat tárgya lehet. Úgy t˝unik, hogy a QuickSI által használt atomsorrendezés és kiegészít˝o adatok rendkívüli módon hasznosíthatóak az izomorfizmusok meghatározásában. A kérdés az, hogy ez a két tulajdonság használható-e más algoritmusokban is – például az Ullmann-algoritmus házasítható-e a QuickSI-vel. Mint említettük már, ez ipari, gyakorlati szempontból nagyon fontos kérdés.
5.4.
Tároló megoldások eredményei
A diplomamunka keretében megvizsgáltunk összesen hét különböz˝o tárolási megoldást. Három relációs adatbázis-kezel˝o rendszer (Relational Database Management System – RDBMS) esetén két különféle adatbázismodell hatékonyságát vizsgáltuk, ezen kívül tekintettük az egyszer˝u, fájlokból való beolvasást. A mérések a ChemAxon Kft. molekulareprezentációjával történtek. Mindkét adatbázismodell esetén négy táblában tároltuk az adatokat. Az egyik tábla tárolta azt, hogy melyik fájlból kerültek az adott molekulák az adatbázisba – az elemzett tesztesetekben ez lényegtelen információ volt, ám az el˝otesztelések esetén például az algoritmusok eredményeinek ellen˝orzéséhez több, kisebb állományt töltöttünk be. Két másik tábla tárolta a QI-sorozat (3.3. definíció) meghatározásához szükséges tartókat (3.4., 3.5. definíciók).
59
A negyedik táblában tároltuk az egyes molekulákat és leírókat és ez volt az, amely a két modell között különbséget eredményezett : készítettünk egy olyan megvalósítást, ahol az egyes leírókat bináris objektumokként (BLOB-okként) tároltuk el, és egy másikat, ahol igyekeztünk, amit csak lehetett karakteresen (VARCHAR) tárolni. Az el˝osz˝urések (lásd 3.5.) egy részét szerettük volna átterhelni az adott RDBMS-re. Ezt azonban csak a két legegyszer˝ubb leíró esetén (atomok illetve kötések száma, 3.6. és 3.7. definíciók) tudtuk kézenfekv˝o módon megtenni, a bonyolultabbakat ugyanis összetettebb Java objektumok reprezentálják, amelyeket adatbázis szinten nem tudunk kezelni. Azonban néhányból kinyerhet˝oek olyan információk, amelyekkel viszonylag hatékony, az adatbázis-kezel˝o számára is értelmezhet˝o sz˝urési feltételeket tudtunk definiálni. Három ilyet használtunk:
• Az atomstatisztika leíróból (3.8. definíció) kiemeltük a legels˝o elemet, vagyis a molekulában el˝oforduló atomok közül a legnagyobb rendszámú rendszámát – így lehet˝ové vált az ez alapján való sz˝urés (a lekérdez˝o molekula legnagyobb rendszáma kisebb vagy egyenl˝o kell legyen, mint a célmolekuláé); • A két használt ujjlenyomat leíróból (3.13., 3.15. definíciók) kinyertük azok kardinalitását, azaz megszámoltuk, hogy hány darab 1-es bit található bennük – így lehet˝ové vált az ezek alapján való sz˝urés (a célmolekula ujjlenyomatának legalább annyi 1-est kell tartalmaznia, mint a lekérdez˝o molekuláénak).
A két adatbázismodellt az egyes rendszerekre meghatározó DDL állományok megtalálhatóak a melléklet DDL mappájában.
60
5.4.1.
MySQL-b˝ol olvasás
Az 5.3-ban definiált számítógépre telepítettünk egy 5.5.20-as verziójú lokális MySQL szervert. A bináris objektumokkal felépített adatbázis esetén a teljes NCI adathalmaz betöltése átlagosan 10 percbe telt, az adatokat tízezresével kötegelve kezeltük. Az adatbázis ≈1,2GiB helyet foglalt el. Az adatbázis végigolvasása egy darab szénatommal átlagosan 35 I/O-val töltött másodpercbe telt. A teljes teszthalmaz futtatása esetén ezzel szemben 8,5 percig használta az adatbázist, a sz˝ukített 19. ábra. MySQL konteszthalmaz 1,5 percig, a csak ritka molekulát tartalmazó teszteset figuráció pedig 2,7 másodpercig. A karakteres adatbázis esetén mindent lehet˝oségünk volt VARCHAR mez˝okben tárolni. A teljes NCI adathalmaz betöltése átlagosan 26 percbe telt, az adatbázis ≈6,6GiB helyet foglalt el. Az adatbázis végigolvasása 3,5 percbe telt, a teljes teszthalmaz futtatása esetén pedig 38,5 perc volt az I/O-val töltött id˝o. A sz˝ukített teszthalmaz átlagosan 6 percig használta az adatbázist, míg a legsz˝ukebb halmaz 2 másodpercig. MySQL esetén a programunkban létrehozott adatbázis interfész (lásd 4.2.1.) minden hiba nélkül m˝uködött.
5.4.2.
Oracle-b˝ol olvasás
Az ELTE IK Információs Rendszerek Tanszékének OraHP nev˝u adatbázisát volt lehet˝oségünk használni. Ez egy PC-szerveren futó Oracle 11gR2 adatbázis, SLES 11 operációs rendszeren, a szerver processzora Intel Core 2, memóriája pedig 2GiB. A kliensgép az 5.3-ban meghatározott számítógép volt, amely az Interneten keresztül csatlakozott az OraHP-hoz. 61
20. ábra. Oracle konfiguráció A bináris objektumokkal felépített adatbázis esetén a teljes NCI adathalmaz betöltése átlagosan 86 percbe telt. Az adatbázis ≈1GiB helyet foglalt el. Az adatbázis végigolvasására a teljes és a sz˝ukített adathalmazzal nem volt lehet˝oségünk: a szerveren a kapcsolat id˝okorlátja 180 perc, és azalatt nem végeztek a keresések. A legsz˝ukebb adathalmazzal átlagosan 113 I/O-val töltött percbe telt a keresés. A karakteres adatbázis esetén két oszlopot voltunk kénytelenek BLOB-ban tárolni, minden mást szám és szöveges mez˝okbe mentettünk. A teljes NCI adathalmaz betöltése átlagosan 74 percbe telt. Az adatbázis ≈610MiB helyet foglalt el. Az adatbázis végigolvasására a teljes és a sz˝ukített adathalmazzal nem volt lehet˝oségünk, ismét az id˝okorlát miatt, de ezzel a reprezentációval jóval több rekordot sikerült ugyanannyi id˝o alatt a rendszernek feldolgoznia. A legsz˝ukebb teszthalmazzal a rendszer átlagosan 1,5 percet töltött I/O-val. Az elérés hosszú ideje semmiképpen nem meglep˝o, egyrészt az adatbázis tulajdonságai miatt az adatokat kétszázötvenesével kötegelve tudtuk kezelni. Másrészt az adatbázist az Interneten keresztül értük el, így a hálózati kommunikációs id˝o is jelent˝os volt – hiszen ezt a több, mint fél gigabájtnyi adatot kellett mozgatnunk a hálózaton, az egyes futtatások alatt akár többször is (a teljes, 30 molekulát tartalmazó teszthalmazban nem egy volt, amelynél több mint 200.000 rekordot kellett a szervernek a klienshez elküldeni). Oracle esetén a programunkban létrehozott adatbázis interfész (lásd 4.2.1.) problémákba ütközött. Ugyanis az Oracle által megvalósított JDBC driver csak bizonyos, egyszer˝u SELECT-ek esetén támogatja a visszafelé is mozgatható kurzorokat. Ezért kénytelenek voltunk módosítani az adatbázisból olvasást, elkerülve az ilyen típusú keresést.
62
5.4.3.
DB2-b˝ol olvasás
A Nyugdíjfolyósító Igazgatóság IBM System z10 BC Z01 típusú mainframe-jén lév˝o egyik z/OS tesztszerveren futó IBM DB2 V9.1 adatbázis-kezel˝ot volt lehet˝oségünk használni a diplomamunka tesztelésének céljából. A cég bels˝o hálózatán keresztül a mainframe-hez kapcsolódó kliensgép egy Dell OptiPlex 360 típusú asztali gép volt. A gép specifikációjának releváns részei:
• Processzor: Intel Core2 Duo E3700 (2 processzor mag, ≈2.66 GHz órajel) • Memória: DDR2, 2 GiB • OS: Windows XP Professional, 32-bit • JRE: 1.6.29, 32-bit
21. ábra. DB2 konfiguráció A bináris objektumokkal felépített adatbázis esetén a teljes NCI adathalmaz betöltése átlagosan 33 percet vett igénybe. A pontos tárfoglalást sajnos nem tudjuk megmondani, ennek oka a z/OS és a DB2 egyedi munkamegosztásán, és a DB2
BLOB -kezelésében
keresend˝o. Röviden arról van szó, hogy a DB2 az összes, nagy objektumot tároló adatbázis oszlopot külön kiegészít˝o táblában (auxiliary table) tárolja, amelyekre külön indexeket, külön táblatereket (tablespace) kell definiálni. A z/OS a táblatereket állományokként definiálja, de a tartalom mindennem˝u kezelését a DB2-re bízza. A DB2 rendszertáblái azonban nem szolgáltatnak pontos információt a bennük található adatok által lefoglalt területr˝ol. Emiatt amit biztosan ki tudunk jelenteni: az adatbázis kevesebb mint 62GiB helyet foglalt el. 63
Az adatbázis végigolvasása egy darab szénatommal átlagosan 19 I/O-val töltött perccel tudott megtörténni. A teljes teszthalmazzal a futtatást nem kíséreltük meg, a sz˝ukített teszthalmazzal átlagosan 13 percet vett igénybe, míg a csak nagy molekulákat tartalmazó teszthalmaz esetén csak 23 másodpercet. A karakteres adatbázis esetén lehet˝oségünk volt mindent VARCHAR mez˝okben tárolni. A teljes NCI adathalmaz betöltése átlagosan 22 percbe telt, az adatbázis ≈2,7GiB helyet foglalt el. Az adatbázis végigolvasása átlagosan 4 I/O-val töltött percbe telt. A teljes teszthalmaz esetén ez 40,5 perc volt, a sz˝ukített teszthalmaznál 6,5 perc, míg a legsz˝ukebb teszthalmazzal 5 másodperc. DB2 esetén a programunkban létrehozott adatbázis interfész (lásd 4.2.1.) problémákba ütközött. Ugyanis az IBM által megvalósított JDBC driver nem képes értelmezni a „fetchSize” utalást, amellyel megadhatjuk az adatbázisnak, hogy egyszerre hány rekordot szeretnénk megkapni t˝ole feldolgozásra. Ennek megfelel˝oen kénytelenek voltunk ezeket az utalásokat kitörölni az adatbázisból olvasás megvalósításból.
5.4.4.
Fájlból olvasás
Fájlból olvasás esetén vettük a teljes NCI adathalmazt tartalmazó nci.smiles fájlt, és vettük a teszthalmazainkat. A pufferméretet 50.000 molekulára véve azt kaptuk, hogy a teljes halmaz végigolvasása egy darab szénmolekulával valamivel több, mint 2 percbe telik (a korábban, 5.3-ban definiált számítógépen). A várakozásoknak megfelel˝oen a lekérdez˝o molekulák számával nagyjából egyenes arányban n˝ott az I/O-val töltött id˝o, hiszen ekkor mindig elölr˝ol kellett olvasnia a fájlt a programnak, újra és újra szekvenciálisan feltöltve majd leürítve a puffert. A teljes teszthalmaz esetén a program 53 percet, a sz˝ukített esetén 23 percet, míg a legsz˝ukebb esetén majdnem 9 percet töltött az adatok beolvasásával.
64
Rendszer
Modell
BLOB
Betöltés (min:s)
Tárhely (GiB)
Teszthalmaz
Futás (min:s)
Végigolvasás
0:35
Teljes
8:25
Sz˝ukített
1:29
Legsz˝ukebb
0:03
Végigolvasás
3:32
Teljes
38:34
Sz˝ukített
5:44
Legsz˝ukebb
0:02
Végigolvasás
> 180:00
Teljes
> 180:00
Sz˝ukített
> 180:00
1,20
10:05
MySQL
VARCHAR
BLOB
6,62
26:11
0,98
85:49
Legsz˝ukebb
113:17
Végigolvasás
> 180:00
Teljes
> 180:00
Sz˝ukített
> 180:00
Oracle
VARCHAR
BLOB
0,59
73:47
≤64,00
32:59
Legsz˝ukebb
1:23
Végigolvasás
18:46
Teljes
−
Sz˝ukített
12:54
Legsz˝ukebb
0:23
Végigolvasás
3:50
Teljes
40:30
Sz˝ukített
6:37
Legsz˝ukebb
0:05
Végigolvasás
2:08
Teljes
53:01
Sz˝ukített
23:06
Legsz˝ukebb
8:59
DB2
VARCHAR
Fájl
SMILES
2,66
21:50
≤0,01
−
22. ábra. Összefoglaló táblázat a tároló rendszerek teljesítményeinek átlagairól
65
5.4.5.
Következtetések
Mint már leírtuk, a diplomamunka és a program els˝odleges célja az algoritmusok tesztelése volt, és az I/O alrendszer, az adatbázisok finomhangolása nem történt meg. Nem is történhetett meg, hiszen ezeket mindig az adott környezethez kell igazítani. Ezenkívül egy valós kémiai informatikai alkalmazásban jóval több feladatot kell ellátnunk. Nem csak a részstruktúra-keresésre kell felkészülnünk, hanem rengeteg más problémára is, így a tárolt adatok mennyisége is jelent˝osen megn˝ohet. A 22-es ábrán lév˝o táblázat alapján azonban levonhatunk néhány következtetést. Ezek közül talán a legfontosabb az, hogy az id˝o nagy része az adatok mozgatásával telik. Vagyis azt, hogy az objektumokat direktben (BLOB-ként) tároljuk az adatbázisban, egyrészt a tárterület, másrészt a hálózat terhelése miatt, nem tehetjük meg. A következ˝o megfontolandó tényez˝o az, hogy a relációs adatbázisok akkor teljesítettek kimagaslóan jól I/O szempontjából, ha a visszaadott célmolekula halmaz kicsi volt, tehát az adatbázis szintjén el tudtunk végezni „er˝os” el˝osz˝uréseket. Ennek könnyítésére célszer˝u lehet más, jelen munkában nem tárgyalt el˝osz˝urési eljárásokat is bevezetni [10, 42]. Tesztelést ugyan nem végeztünk, de érdemes elgondolkodni egy olyan adatbázismodellen, ahol rekordonként nem egy molekulát tárolunk, hanem molekulák olyan csoportját, amelyek között adatbázis szinten amúgy sem tudnánk dönteni, és ezeket a molekulákat mindenképpen visszaadná az adott lekérdezés. Ez megvalósítható például úgy, hogy keverjük a relációs és nem relációs adatbázisok elveit (nem egy RDBMS támogatja már az XML-t, mint típust) [26]. El kell gondolkodni azon is, hogy az egyes molekula leírókat érdemes-e tárolni. Úgy t˝unik, hogy az egyszer˝uen, számként reprezentálható leírókat mindenképpen, de a bonyolultabb tömbleírókat nem. A probléma az, hogy nagy az adatmennyiség, és a hálózati adatforgalom lassabb annál, mintha a lokális gép kiszámolná újra és újra a leírókat. Az ujjlenyomatok másik kategóriát képviselnek, ezek tárolása racionálisabb módszerekkel nagyon hatékonnyá tehet˝o lenne (a bitsorozatok tömörítése, számként kódolása, stb.).
66
Az is megállapítható, hogy az I/O pufferezetté tétele adatbázisok esetén nem indokolt. Nem a memóriába olvasás ideje a szignifikáns, hanem a hálózaton töltött id˝o. Ezen kívül a gyakorlati, ipari felhasználások szempontjából nagyon fontos megjegyeznünk, hogy bármilyen adatbázisról legyen is szó, a feldolgozást aszinkronná kell tenni. A felhasználó számára nagyon fontos, hogy az els˝o eredményeket minél hamarabb lássa, az hogy az összes eredmény mikorra van meg, kevésbé számít (értend˝o most az els˝o eredményt mind az els˝o molekula párra, mind az els˝o izomorfizmusra nézve). Azaz az eredményeket azonnal publikálni kell a felhasználó felé, miközben a háttérben tovább fut a feldolgozás.
67
6.
Összefoglalás, kitekintés
A diplomamunkában a kémiai informatika egyik fontos, gyakran el˝okerül˝o feladatát, a részstruktúra-keresést vizsgáltuk. Mint beláttuk, ez a matematikából jól ismert részgráfizomorfia probléma, amelyre a problématér sajátosságai miatt az általános megvalósításoknál jobb algoritmusok adhatóak. Ezen algoritmusok közül hármat implementáltunk, és összehasonlítottuk teljesítményüket a ChemAxon Kft. által kiadott megvalósításokkal. Sikerült a cég által publikáltnál gyorsabban m˝uköd˝o megoldásokat mutatnunk, de a megoldott probléma nem pontosan ugyanaz, így az arra adott válasz sem, ezért az eredményeket óvatosan kell értelmeznünk. Úgy t˝unik, hogy mindenképpen érdemes a cég által kiadott algoritmusokat fejleszteni az új eredmények [7, 31, 36] fényében. Fontos kiemelnünk, hogy a diplomamunkában sok olyan jellegzetességet figyelmen kívül hagytunk, amelyek valós ipari alkalmazásokban nagyon fontosak lehetnek, és jelent˝osen befolyásolhatják az algoritmusok futási idejét. Példaként vegyük az aromatizálási problémát, amelynél bizonyos esetekben többféle él lehet jó az illesztésben (lásd Kekulé-forma és aromás forma, a 2-es ábrán, a 8. oldalon). A diplomamunkában elhanyagolt implicit hidrogén jelenség is befolyásolhatja mind az algoritmusok bonyolultságát, mind a futási id˝oket. Ezen kívül tekinthetjük például az úgynevezett Markush struktúrákat [5], amelyekkel bevezethetünk behelyettesíthet˝o atomokat és kötéseket (mint a „joker-karakterek” szöveges keresések esetén), vagy leírhatunk különböz˝o kombinatorikus változékonyságokat – érthet˝o, hogy az ilyen struktúrák esetén nem is feltétlenül kellenek nagy molekulák ahhoz, hogy a futási id˝o drasztikusan megnövekedjen. A feladat rengeteg párhuzamosítási lehet˝oséget rejt magában. Példaként kiemelve kett˝ot: egyértelm˝u, hogy ha a célmolekulák adatbázisát felosztjuk részekre, és a lekérdez˝o molekulákat odaadjuk minden feldolgozó egységnek, akkor egy egyszer˝u „küls˝o” párhuzamosítást hajtottunk végre. Másfel˝ol az algoritmusok maguk is párhuzamosíthatóak lennének – például a keresési fa valamilyen szétvágása által, egyfajta „bels˝o” párhuzamosításként.
68
A gráfok adatbázisban való tárolására is kifejlesztettek már sokkal kifinomultabb módszereket, amelyek nem feltétlenül relációs adatbázisokkal dolgoznak [1, 26], ahogy ezek indexelése is külön kutatási szakirány [10, 22, 41]. Az ujjlenyomatok [6] paraméterezésére a diplomamunka nem tért ki (a tesztek futtatása során a bitsorozatok hossza rögzített volt). Ezek paraméterezési lehet˝oségeinek vizsgálata, valamint az új leírók fejlesztése, azokból ujjlenyomatok képzése sokat javíthat az itt ismertetett el˝osz˝urések hatékonyságán. Az el˝osz˝urési eljárások [6] is tovább b˝ovíthet˝oek. Készítettek olyan el˝osz˝urési technikákat, amelyek a QuickSI [31] algoritmushoz hasonlóan kihasználnak adatbázis-globális jellemz˝oket [28, 42]. Ezen túl a diplomamunka keretében nem foglalkoztunk a jellemz˝o részstruktúrákkal, amelyek alapján szintén jó el˝osz˝urések és heurisztikák képezhet˝oek, ezek megtalálása szintén elvégezhet˝o futási id˝on kívül, kötegelt feldolgozással az adatbázisban [20, 21]. Régóta ismert tény, hogy a gráfok síkbarajzolhatósága lineáris futási id˝oben eldönthet˝o [4, 19]. Eppstein [12] mutatott olyan megoldást, amely síkbarajzolható gráfok és rögzített (konstans) méret˝u lekérdez˝ográf esetén az itt bemutatottnál nagyságrendben kevesebb m˝uveletet végez. Érdekes vizsgálati kérdés, hogy javít-e a futási id˝on a síkbarajzolhatóság ellen˝orzése és utána egyszer˝usített algoritmus futtatása a most elért eredményekhez képest, ha az adatbázisra jellemz˝o résztstruktúrákat keressük. Ez egyben fontos kérdés is, hiszen például a vizsgált NCI adatbázis több mint 94%-a síkbarajzolható [21, 24]. A kémiai informatika egy kicsit másik részterülete a hasonlósági keresés [6]. Az ezen a szakterületen használt technikákat (pl. : a Tanimoto-távolságot [32], de sok mást is [15]) kombinálva a jellemz˝o adatstruktúrák keresésével [21, 29, 42] úgy érezzük, hogy szintén jó, adatbázis szint˝u el˝osz˝uréseket lehetne alkotni. Összességében kijelenthet˝o az elért eredmények alapján: a területen megfigyelhet˝o innováció, és az új eredményeket érdemes lehet az eddig megalkotott keres˝orendszerekbe beleilleszteni. További, a kémiai informatika, adatbázis-elmélet, matematika és informatika más területeir˝ol származó technikák és technológiák összeszövése is jelent˝os eredményeket hozhat az alkalmazásokban. 69
7.
Függelék 7.1.
A program beállításai
7.1.1.
A konfigurációs fájl felépítése
Az alábbiakban megadjuk a program beállításait elvégz˝o fájl felépítését. A fájl kódolása UTF -8,
feldolgozása soronként történik, és a fájlban úgynevezett szakaszoló megjegyzések
és beállító sorok találhatóak. A megjegyzés sorok # karakterrel kezd˝odnek, a beállító sorok a < BEÁLLÍTOTT TULAJDONSÁG NEVE >=< ÉRTÉK > minta szerint épülnek fel. Az alábbi felsorolásban az egyes tulajdonságok után felsoroljuk a lehetséges értékeket. Fontos megjegyeznünk, hogy a program nem végez ellen˝orzést arra vonatkozóan, hogy az egyes beállításokhoz társított értékek az alábbi specifikációnak megfelelnek-e, ez minden esetben a programot futtató felel˝ossége. Amennyiben a config.properties fájl nem felel meg az alábbi specifikációnak, a program m˝uködésére semmilyen garanciát nem adunk.
• # CONFIG – általános vezérlés (lásd még 4.2.1.) ◦
PRINT C ONSOLE O UTPUT : TRUE , FALSE
– írjon-e a program üzeneteket a
standard kimenetre; a paraméter nem különbözteti meg a kis- és nagybet˝uket (case-insensitive) ◦
PRINT P ROGRESS BAR : TRUE , FALSE
– írjon-e a program a konzolra állapot-
jelz˝ot (lásd 2.4.); a paraméter nem különbözteti meg a kis- és nagybet˝uket ◦
PROGRESS BAR N EW L INE : TRUE , FALSE
– ha ír állapotjelz˝ot, akkor minden
egyes új állapot új sorba kerüljön (\ R \ N), vagy ugyanabba a sorba írjuk (\ R); a paraméter nem különbözteti meg a kis- és nagybet˝uket ◦
LOG : TRUE , FALSE
– készítsen-e a program XML naplót (lásd 5.1.); a para-
méter nem különbözteti meg a kis- és nagybet˝uket
70
◦
LOG NAME : JAVA . LANG .S TRING
– ha készít naplót, mi legyen a naplófájl
neve (csak a neve, a . XML kiterjesztést automatikusan utána f˝uzi a program); a paraméter megkülönbözteti a kis- és nagybet˝uket (case-sensitive) ◦
LOG L EVEL : JAVA . LANG .L EVEL ,
azaz egyike az OFF, FINEST, FINER,
FINE, CONFIG, INFO, WARNING, SEVERE értékeknek – ha készít naplót, akkor az milyen szint˝u legyen ; a paraméter megkülönbözteti a kis- és nagybet˝uket ◦
MOLECULE T YPE : CHEM [ AXON ], SIMPLE
rezentációt használjon,
CHEM
illetve
– a program milyen molekularep-
CHEMAXON
esetén a ChemAxon Kft.
által kiadott CHEMAXON . STRUC .M OLECULE osztályt használja, SIMPLE esetén egy sokkal egyszer˝ubb, csak a mostani programhoz elégséges interfésszel rendelkez˝o reprezentációt; a paraméter nem különbözteti meg a kis- és nagybet˝uket ◦
FIRST H IT : TRUE , FALSE
– csak az els˝o leképezést keressük meg, vagy a lehet-
séges leképezések számára vagyunk kíváncsiak ; a paraméter nem különbözteti meg a kis- és nagybet˝uket • # OUTPUT – az eredményfájl tulajdonságai (lásd még 4.2.1.) ◦
OUTPUT T YPE : FILE
– nem állítható paraméter, kötelez˝o értékkel, magyará-
zatát lásd a 4.2.1. alfejezetben; a paraméter nem különbözteti meg a kis- és nagybet˝uket ◦
OUTPUT NAME : JAVA . LANG .S TRING
– a generált kimenet állomány teljes
neve, relatív elérési útként megadva a futtatott állományhoz képest; a paraméter megkülönbözteti a kis- és nagybet˝uket • # QUERY – a lekérdezésre vonatkozó beállítások (lásd még 4.2.1., 4.4.) ◦
QUERY T YPE : FILE
– nem állítható paraméter, kötelez˝o értékkel, magyará-
zatát lásd a 4.2.1. alfejezetben; a paraméter nem különbözteti meg a kis- és nagybet˝uket ◦
QUERY NAME : JAVA . LANG .S TRING
71
– fájl esetén a lekérdez˝o állomány neve
a relatív elérési úttal, adatbázis esetén a megfelel˝o forrás neve; a paraméter megkülönbözteti a kis- és nagybet˝uket ◦
QUERY T HRESHOLD : JAVA . LANG .I NTEGER
(0 < x) – a lekérdez˝o molekulák
pufferének mérete ◦
QUERY E MPTY P ERCENT : JAVA . LANG .I NTEGER
(0 ≤ x < 100) – a lekér-
dez˝o molekulák pufferének ürítési százaléka (ennyi százalékát hagyja meg a pufferben lév˝o értékeknek) ◦
CALCULATE D ESCRIPTORS O N Q UERY : TRUE , FALSE
– a lekérdez˝o moleku-
lákra a beolvasáskor kiszámolja-e a program a leírókat (lásd 3.4.), vagy csak akkor, ha azokra hivatkozás történik ; a paraméter nem különbözteti meg a kisés nagybet˝uket ◦
CALCULATE O PTIMAL QIS EQUENCE : TRUE , FALSE
– a lekérdez˝o moleku-
lákra számoljon-e a program adatbázis-hatékony QI-sorozatot (3.3. definíció), vagy sem; a paraméter nem különbözteti meg a kis- és nagybet˝uket • # TARGET – a molekula adatbázis tulajdonságai (lásd még 4.2.1., 4.4.) ◦
TARGET T YPE : FILE , D [ ATA ] B [ ASE ]
– a célmolekulákat fájlból vagy adatbá-
zisból olvassuk-e be; a paraméter nem különbözteti meg a kis- és nagybet˝uket ◦
DB URL : JAVA . LANG .S TRING
– az adatbázis-kapcsolat JDBC URL-je (pl.:
JDBC : MYSQL :// LOCALHOST :3306/ CHEM ? USER = ROOT );
a paraméter meg-
különbözteti a kis- és nagybet˝uket ◦
JDBC D RIVER : JAVA . LANG .S TRING
– az JDBC-connector osztály kanonikus
neve (pl.: COM . MYSQL . JDBC .D RIVER); a paraméter megkülönbözteti a kisés nagybet˝uket ◦
DB F ETCH S IZE : JAVA . LANG .I NTEGER
(0 < x) – a Java SQL statementek
egyszerre hány rekordot fetcheljenek az adatbázisból ◦
TARGET NAME : JAVA . LANG .S TRING
– fájl esetén a célállomány neve a relatív
elérési úttal, adatbázis esetén a megfelel˝o forrás neve ; a paraméter megkülönbözteti a kis- és nagybet˝uket
72
◦
TARGET T HRESHOLD : JAVA . LANG .I NTEGER
(0 < x) – a célmolekulák puffe-
rének mérete ◦
TARGET E MPTY P ERCENT : JAVA . LANG .I NTEGER
(0 ≤ x < 100) – a célmole-
kulák pufferének ürítési százaléka (ennyi százalékát hagyja meg a pufferben lév˝o értékeknek) ◦
CALCULATE D ESCRIPTORS O N TARGET : TRUE , FALSE
– a célmolekulákra a
beolvasáskor kiszámolja-e a program a leírókat (lásd 3.4.), vagy csak akkor, ha azokra hivatkozás történik; a paraméter nem különbözteti meg a kis- és nagybet˝uket • # DESCRIPTORS – a leírókra vonatkozó beállítások (lásd még 3.4.) ◦
STARS F INGERPRINT H ASH S IZE : JAVA . LANG .I NTEGER
(0 < x ≤ 4096) – a
csillag ujjlenyomat hossza ◦
REINDEXING S EARCH : DEPTH , BREADTH
– az újraindexelés leíró bejárása
mélységi- vagy szélességi bejárás legyen; a paraméter nem különbözteti meg a kis- és nagybet˝uket ◦
PATHS H ASH S IZE : JAVA . LANG .I NTEGER , (0
< x ≤ 4096) – az út ujjlenyomat
hossza ◦
PATHS L ENGHT : JAVA . LANG .I NTEGER ,
(0 < x ≤ 5) – a vizsgált utak hossza
• # USAGE – milyen el˝osz˝uréseket és algoritmust használjon a program (lásd még 3.3., 3.5., 4.2.2., 4.4., 4.5.) ◦
SCREEN : PLAIN , SUB , D [ ATA ] B [ ASE ]
– milyen el˝osz˝urést használjon a prog-
ram; a paraméter nem különbözteti meg a kis- és nagybet˝uket ◦
ALGORITHM : NAIVE , VF 2, QUICKSI , ULLMANN , ULLMANNB
– milyen
algoritmust használjon a program ; a paraméter nem különbözteti meg a kis- és nagybet˝uket • # SCREENING – az el˝osz˝urésekre vonatkozó beállítások (lásd még 3.5., 4.2.2., 4.4.) ◦
SCREENATOM C OUNT : TRUE , FALSE
– atomok száma alapján sz˝urjön-e a
program; a paraméter nem különbözteti meg a kis- és nagybet˝uket 73
◦
SCREEN B OND C OUNT : TRUE , FALSE
– kötések száma alapján sz˝urjön-e a
program; a paraméter nem különbözteti meg a kis- és nagybet˝uket ◦
SCREENATOM S TATISTICS : TRUE , FALSE
– atomstatisztika leírók alapján
sz˝urjön-e a program; a paraméter nem különbözteti meg a kis- és nagybet˝uket ◦
SCREEN S TARS : TRUE , FALSE
– csillag ujjlenyomat alapján sz˝urjön-e a prog-
ram; a paraméter nem különbözteti meg a kis- és nagybet˝uket ◦
SCREEN PATHS : TRUE , FALSE
– út ujjlenyomat alapján sz˝urjön-e a program;
a paraméter nem különbözteti meg a kis- és nagybet˝uket • # HEURISTICS – az algoritmusokra vonatkozó beállítások (lásd még 3.6., 4.2.2., 4.5.) ◦
REINDEX O N TARGET : TRUE , FALSE
– használjon-e a program újrarendezést
a célmolekula atomjainak sorrendjében; a paraméter nem különbözteti meg a kis- és nagybet˝uket ◦
REINDEX O N Q UERY : TRUE , FALSE
– használjon-e a program újrarendezést a
lekérdez˝o molekula atomjainak sorrendjében ; a paraméter nem különbözteti meg a kis- és nagybet˝uket ◦
MATCH B OND C OUNT : TRUE , FALSE
– illesztéskor vizsgálja-e a program a
kötések számosságát ; a paraméter nem különbözteti meg a kis- és nagybet˝uket ◦
MATCH B OND T YPES : TRUE , FALSE
– illesztéskor vizsgálja-e a program a
még nem illesztett kötések típusát; a paraméter nem különbözteti meg a kis- és nagybet˝uket ◦
MATCH S TARS : TRUE , FALSE
– illesztéskor vizsgálja-e a program a csillago-
kat; a paraméter nem különbözteti meg a kis- és nagybet˝uket ◦
CHECK AVAILABILITY : TRUE , FALSE
– „naiv” algoritmus esetén a program
külön tárolja-e a még lehetséges illesztések halmazát; a paraméter nem különbözteti meg a kis- és nagybet˝uket
74
7.1.2.
Parancssori paraméterezés
A config.properties fájl megléte kötelez˝o, ugyanakkor szükségünk lehet arra, hogy néhány paraméter dinamikusan, az egyes futások között változtatható legyen. Ezt a tulajdonságot használtuk ki például a teljesítmény méréseknél, ahol változtattuk a bemenetek/kimenetek nevét és az el˝osz˝urésekre/algoritmusokra vonatkozó beállításokat, de nem akartuk mindig átírni a konfigurációs állományt. Ha az adott futtatásnál felül akarunk írni egy konfigurációs paramétert, akkor azt a szokásos módon, parancssori argumentumokként kell átadnunk a programnak. Két lehet˝oségünk van : a) pontosan két paramétert adunk meg, els˝o a lekérdez˝o- és célmolekulákat tartalmazó állomány neve (QUERY NAME és TARGET NAME paraméterek), a második az eredményfájl neve (OUTPUT NAME paraméter); b) tetsz˝oleges számú paramétert adunk meg a < PARAMÉTER NEVE >=< ÉRTÉK > minta szerint. Ekkor az adott paramétereknél nem a konfigurációs állományban beállított, hanem az itt megadott érték az irányadó. Példa az a) esetre: JAVA - JAR SSS. JAR INPUTS / TEST 01. SMILES OUTPUTS / TEST
01. OUT
Példa a b) esetre: JAVA - JAR SSS. JAR SCREEN = SUB DB F ETCH S IZE =10000 TARGET E MPTY P ERCENT =50
7.2.
Licencelt programkönyvtár
A mellékletre nem kerültek rá a programban használt programkönyvtárak és a licenc állomány. Ennek oka például, hogy a programkönyvtár használata felhasználói feltételekhez kötött. Azonban ezek publikusak, letölthet˝oek a http://chemaxon.com/ weboldalról. A mellékleten lév˝o program mellé ezeket a JAR-okat kell bemásolnunk egy lib nev˝u könyvtárba. Akadémiai licenc igényelhet˝o, az ELTE IK Algoritmusok és Alkalmazásaik Tanszékének van ilyen licence, azt használtuk a diplomamunka során. 75
7.3.
Példa nem rendezett SMILES-ra
Vegyünk egy viszonylag egyszer˝u molekulát: egy szén- illetve oxigénatomokból váltakozva felépül˝o nagy gy˝ur˝ut.
23. ábra. Példa nem rendezett SMILES-hoz Ennek egyszer˝u (kanonizált) SMILES leírása a várakozásoknak megfelel˝oen egyszer˝u :
C1OCOCOCOCOCOCOCOCOCOCOCOCOCOCO1
Hiszen megsorszámozzuk az els˝o szénatomot, leírjuk a gy˝ur˝ut, majd visszakötjük az utolsó oxigén atomot a megsorszámozott els˝ohöz. Amennyiben a hivatalos SMILES el˝oírások szerint járunk el, akkor valami a fentihez hasonló stringet fogunk kapni, hiszen valamilyen gráfbejárást végzünk a gy˝ur˝un. Azonban ha eltekintünk a bejárás kényszerét˝ol, akkor „összekeverhetjük” a stringet, például mondhatjuk azt, hogy el˝oször leírjuk a gy˝ur˝uben lév˝o oxigénatomokat, majd utána a szén atomokat, minden egyes atomot külön komponensként. Persze ekkor gondoskodnunk kell arról, hogy a szomszédok mégis össze legyenek kötve, valahogy így:
O12.O34.O56.O78.O9%10.O%11%12.O%13%14.O%15%16.O%17%18.O%19 %20.O%21%22.O%23%24.O%25%26.O%27%28.O%29%30.C%25%30.C3%26. C4%15.C%16%23.C9%24.C%10%13.C1%14.C2%21.C%11%22.C7%12.C8%1 9.C%20%27.C5%28.C6%17.C%18%29
Vagy gondolkozhatunk úgy, hogy felváltva írunk szén és oxigén atomokat, csak a sorrendjük nem egy megszokott bejárás által meghatározott, hanem például ilyen: 76
C%20%27.O12.C%25%30.O34.C3%26.O56.C4%15.O78.C1%14.O9%10.C% 16%23.O%11%12.C9%24.O%13%14.C%10%13.C%18%29.O%15%16.O%17%1 8.C7%12.O%19%20.C6%17.O%21%22.C5%28.O%23%24.C8%19.O%25%26. C%11%22.O%27%28.C2%21.O%29%30
Ez a két bonyolult példa megfelel a SMILES szabályainak, teljes mértékben értelmezhet˝o stringek, és ugyanúgy a 23-as ábrán látható molekulát írják le, mint az els˝o, szemmel is olvasható SMILES. Azonban az ilyen bonyolultabb megadási módok rendkívül alkalmasak például tesztelési célokra, hiszen itt az atomok sorrendje nem egy (mélységi) bejárásból adódik. Ennek következtében nem a szomszédos atomok vannak egymás mellett a reprezentációban, ezzel elkerülve egy „implicit” heurisztikát.
7.4.
A naplóállomány váza
Ebben az alfejezetben megadjuk a naplóállományok vázát, a könnyebb áttekinthet˝oség kedvéért (lásd 5.1.).
quicksi ... 1 9185436 <process> 180 3181976537139 77
1 2757403508 <search> 1 4319157338191 1 4340718243652
78
Hivatkozások [1] Renzo Angles – Claudio Gutierrez: Survey of graph database models. ACM Computing Surveys, 40. évf. (2008) 1. sz., 1–39. p. [2] Járai Antal: Bevezetés a matematikába (második, javított kiadás). 2006, Eötvös kiadó. ISBN 9634637299. [3] Joshua Bloch: Effective Java (2nd Edition) (The Java Series). 2. kiad. 2008, Prentice Hall PTR. ISBN 0321356683, 9780321356680. [4] John M. Boyer – Wendy J. Myrvold: On the cutting edge: Simplified O(n) planarity by edge addition. Journal of Graph Algorithms and Applications, 8. évf. (2004) 3. sz., 241–273. p. [5] Lucille J. Brown: The Markush challenge. Journal of Chemical Information and Computer Sciences, 31. évf. (1991) 1. sz., 2–4. p. [6] Nathan Brown : Chemoinformatics – an introduction for computer scientists. ACM Computing Surveys, 41. évf. (2009) 2. sz., 8–38. p. [7] Luigi P. Cordella – Pasquale Foggia – Carlo Sansone – Mario Vento: An improved algorithm for matching large graphs. In Proceeding of the 3rd IAPR TC-15 Workshop on Graphbased Representations in Pattern Recognition (konferenciaanyag). 2001, 149–159. p. [8] Thomas H. Cormen – Clifford Stein – Ronald L. Rivest – Charles E. Leiserson: Introduction to Algorithms. 2. kiad. 2001, McGraw-Hill Higher Education. ISBN 0070131511. [9] Oracle Corporation: The Java Tutorials – Properties. http://docs.oracle. com/javase/tutorial/essential/environment/properties. html. Utolsó elérés dátuma: 2012. 05. 10. [10] Bin Cui – Heng Tao Shen – Jialie Shen – Kian-Lee Tan: Exploring bit-difference for approximate KNN search in high-dimensional databases. In Proceedings of the 16th 79
Australasian database conference - Volume 39, ADC ’05 konferenciasorozat. 2005, 165–174. p. ISBN 192068221X. [11] Thomas Engel: Basic Overview of Chemoinformatics. Journal of Chemical Information and Modeling, 46. évf. (2006) 6. sz., 2267–2277. p. [12] David Eppstein: Subgraph isomorphism in planar graphs and related problems. In Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, SODA ’95 konferenciasorozat. 1995, Society for Industrial and Applied Mathematics, 632–640. p. [13] Erich Gamma – Richard Helm – Ralph Johnson – John Vlissides: Design patterns: elements of reusable object-oriented software. 1995, Addison-Wesley Longman Publishing Co., Inc. ISBN 0201633612. [14] Michael R. Garey – David S. Johnson: Computers and Intractability; A Guide to the Theory of NP-Completeness. 1990, W. H. Freeman & Co. ISBN 0716710455. [15] Valerie J. Gillet – Peter Willett : Chemoinformatics Techniques for Processing Chemical Structure Databases. 2006, John Wiley & Sons, Inc., 187–208. p. ISBN 9780470037232. [16] Brian
Goetz:
To
mutate
or
not
to
mutate?
http://www.ibm.
com/developerworks/java/library/j−jtp02183/index.html, 2003. Utolsó elérés dátuma: 2012. 05. 10. [17] James Gosling – Bill Joy – Guy Steele – Gilad Bracha – Alex Buckley: The Java Language Specification, Java SE 7 Edition. 2012, Prentice Hall. [18] Mark Grand: Patterns in Java, volume 1: a catalog of reusable design patterns illustrated with UML. 1. köt. 2002, Wiley. ISBN 0471258393. [19] John Hopcroft – Robert Tarjan: Efficient Planarity Testing. Journal of the ACM, 21. évf. (1974) 4. sz., 549–568. p.
80
[20] Tamás Horváth – Thomas Gärtner – Stefan Wrobel: Cyclic pattern kernels for predictive graph mining. In Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, KDD ’04 konferenciasorozat. 2004, 158–167. p. ISBN 1581138881. [21] Tamás Horváth – Jan Ramon – Stefan Wrobel: Frequent subgraph mining in outerplanar graphs. In Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, KDD ’06 konferenciasorozat. 2006, 197– 206. p. ISBN 1595933395. [22] Wolf D. Ihlenfeldt – Johann Gasteiger : Hash codes for the identification and classification of molecular structure elements. Journal of Computational Chemistry, 15. évf. (1994) 8. sz., 793–813. p. [23] Daylight Chemical Information Systems Incorporation: Daylight Theory: SMILES. http://www.daylight.com/dayhtml/doc/theory/theory. smiles.html, 2008. Utolsó elérés dátuma: 2012. 05. 10. [24] National Cancer Institute: Downloadable Structure Files of NCI Open Database Compounds. http://cactus.nci.nih.gov/download/nci/, 2000. Utolsó elérés dátuma: 2012. 05. 10. [25] Fóthi Ákos – Horváth Zoltán: Bevezetés a programozásba. 2005, Eötvös kiadó (az Oktatási Minisztérium támogatásával). ISBN 9789634638339. [26] Zhen Hua Liu – Muralidhar Krishnaprasad – James W. Warner – Rohan Angrish – Vikas Arora: Effective and efficient update of XML in RDBMS. In Proceedings of the 2007 ACM SIGMOD international conference on Management of data, SIGMOD ’07 konferenciasorozat. 2007, 925–936. p. ISBN 9781595936868. [27] Steven C. McConnell: Code Complete, Second Edition. 2004, Microsoft Press. ISBN 0735619670, 9780735619678. [28] Vigula Mónika: A részgráf-izomorfizmus probléma adatbázisokban. Alkalmazott matematikus BSc szakdolgozat. Eötvös Loránd Tudományegyetem, Természettudományi Kar, 2012. 81
[29] Ramzi Nasr – Rares Vernica – Chen Li – Pierre Baldi : Speeding Up Chemical Searches Using the Inverted Index: The Convergence of Chemoinformatics and Text Search Methods. Journal of Chemical Information and Modeling, 52. évf. (2012) 4. sz., 891–900. p. [30] US Department of Health – Human Services National Institutes of Health : National Cancer Institute. http://www.cancer.gov. Utolsó elérés dátuma: 2012. 05. 10. [31] Haichuan Shang – Ying Zhang – Xuemin Lin – Jeffrey Xu Yu: Taming verification hardness: an efficient algorithm for testing subgraph isomorphism. Proceedings of the VLDB Endowment, 1. évf. (2008) 1. sz., 364–375. p. [32] Taffee T. Tanimoto: An Internal Report. Jelentés, IBM. 1957. November 17. [33] Wikipedia the free encyclopedia: Amino acid. http://en.wikipedia. org/wiki/Amino_acid. Utolsó elérés dátuma: 2012. 05. 10. [34] Wikipedia the free encyclopedia: Ascorbid acid. http://en.wikipedia. org/wiki/Ascorbic_acid. Utolsó elérés dátuma: 2012. 05. 10. [35] Julian R. Ullmann : An Algorithm for Subgraph Isomorphism. Journal of the ACM, 23. évf. (1976) 1. sz., 31–42. p. [36] Julian R. Ullmann: Bit-vector algorithms for binary constraint satisfaction and subgraph isomorphism. Journal of Experimental Algorithmics, 15. évf. (2011) 6. sz., 1–64. p. [37] W3C:
XSL
Transformations
(XSLT)
Version
2.0.
http://www.w3.
org/TR/xslt20/, 2007. Utolsó elérés dátuma: 2012. 05. 10. [38] W3C: Extensible Markup Language (XML) 1.0 (Fifth Edition). http://www.w3. org/TR/REC−xml/, 2008. Utolsó elérés dátuma: 2012. 05. 10. [39] David Weininger : SMILES, a chemical language and information system. Journal of Chemical Information and Computer Sciences, 28. évf. (1988) 1. sz., 31–36. p. [40] Steve Wilson – Jeff Kesselman : Java Platform Performance: Strategies and Tactics. 2000, Addison-Wesley. ISBN 9780201709698. 82
[41] W. Todd Wipke – Srinivas Krishnan – Glenn I. Ouchi: Hash Functions for Rapid Storage and Retrieval of Chemical Structures. Journal of Chemical Information and Computer Sciences, 18. évf. (1978) 1. sz., 32–37. p. [42] Peixiang Zhao – Jeffrey Xu Yu – Philip S. Yu: Graph indexing: tree + delta >= graph. In Proceedings of the 33rd international conference on Very large data bases, VLDB ’07 konferenciasorozat. 2007, 938–949. p. ISBN 9781595936493.
83
A diplomamunka AMS-LATEX 2ε és BIBTEX segítségével, MiKTEX környezetben, a TEXnicCenter IDE-t használva készült. A program a JDK 1.6-os kiadásával, a NetBeans IDE 7.0.1-es verziójában készült. Az ábrák MS Visio 2010 és az OpenOffice irodai programcsomag segítségével készültek. A molekula ábrázolások a MarvinSketch 5.5.1.0-ás verziójával készültek. A programban használtuk a ChemAxon Kft. Marvin Beans és JChem Base könyvtárainak 5.9.2-es verzióját, amelyhez akadémiai licencet biztosítottak számunkra.
