4. fejezet - Szűrő modell

Tartalom

4.1. Szűrés Blokkolással
4.2. Szűrés Felületen
4.3. Párhuzamos Szűrés
4.4. Szűrés Memóriával

A Lipton-féle SAT probléma megoldási módszer alapján kifejlesztett általános módszert szűrő modellnek nevezzük. Számos NP-teljes probléma megoldható e módszer segítségével (természetesen gyakorlatban csak egy adott méretig). Ebben a fejezetben néhány ilyen problémának a DNS-ekkel való megoldását mutatjuk be, illetve kitekintünk a modell különböző variációira is.

A szűrő jellegű DNS számításokban a sztringek, mint DNS molekulák véges multihalmazain hajtjuk végre műveletek (operátorok) sorozatát. A multihalmaz jelen esetben azt jelenti, hogy egyes sztringekből általában egynél több példány is jelen van. Általában a számítás egy kiindulási halmazból indul és végül egy megoldás halmazt állít elő. Mielőtt rátérünk a különböző műveletek ismertetésére, nézzük milyen jellegű kiindulási halmazokat használhatunk.

A kiindulási halmaz általában n-nel arányos hosszú sztringeket tartalmaz, ahol n a megoldandó input probléma mérete. A halmaznak a megoldandó probléma minden lehetséges megoldását tartalmaznia kell (sztring formába kódoltan). Másrészt olyan halmaz lehet kiindulási halmaz, ami könnyen előállítható.

Ilyen kiindulási halmaz lehet pl. körmentes irányított gráfban levő összes utat tartalmazó multihalmaz. Például a Lipton-féle problémamegoldáshoz is használt gráf egy általánosabb formája: ahol

Egy ilyen gráfban levő maximális hosszúságú utak (k+2 csúcsot tartalmazó utak) a végükön levő fix csúcsokkal. Ha feltételezzük, hogy egy adott problémában k változó szerepel, és mindegyik éppen n különböző értéket vehet fel, akkor ezek az utak éppen az összes lehetséges „értékelést" jelentik. A SAT probléma megoldásához a éppen a gráfot használtuk Lipton algoritmusához.

14. Feladat. Rajzoljuk fel a gráfot, és adjuk meg a maximális utakat benne.

Szokás a gráf olyan verziójának a használata is, amelyben minden csúcshalmaz után egy pi pozíciót jelző csúcs van beszúrva, és az s = p0, valamint a t = pk+1. Ennek megfelelően a maximális utak a alakúak, megfelelő j1,...,jk értékek mellett. Így ugyan több csúcsból áll a gráf (nk + k + 1), viszont az élek száma 2kn-re módosul. A pozíciójelek pedig egyes algoritmusok esetén további jelentőséggel bírnak. Ezeket a fix, minden maximális úton előforduló pozíciócsúcsokat is tartalmazó gráfokat -val jelöljük.

15. Feladat. Rajzoljuk fel a gráfot, és adjuk meg a maximális utakat benne.

Maga a számítás a kiindulási halmaz el(ő)készítése után abból áll, hogy kiszűrjük azokat a sztringeket, amelyek nem lehetnek megoldások (biztosan nem azt reprezentálnak). Általában a modell számítási ereje abban rejlik, hogy a (multi)halmaz elemeinek száma exponenciális a probléma méretét jelző n-hez képest. Ebben a részben ilyen számításokra mutatunk példákat.

Az alapmodelleben a következő három műveletet fogjuk használni a multihalmazokra:

Ezt a szűrő modellt egyébként szokás memóriátlannak is nevezni, mivel a sztringek maguk nem változnak meg a számítás során.

Vizsgáljuk meg most a gráfelméleti 3-színezés problémát, amin Adleman 1996-ban ezt a módszert szemléltette.

11. Példa. Adott egy G = (V,E) gráf, ahol V = {a1,..., am}. A kérdés, hogy kiszínezhetőek a csúcsai három színnel (legyenek ezek a piros, kék és a zöld), oly módon, hogy minden csúcshoz pontosan egy színt rendelünk, és nincs olyan éle a gráfnak, amely azonos színű csúcsokat köt össze. Annak meghatározása, hogy egy input gráf a fenti módon 3-színezhető-e, NP-teljes probléma.

A feladat megoldását részletesen ismertetjük: Vegyük alaphalmaznak a gráf alapján készült maximális utakat tartalmazó multihalmazt. Ezen utakon a csúcs jelentse azt, hogy a G input gráf ai csúcsának színe piros (ha szerepel), kék (ha szerepel), illetve zöld (ha szerepel) az adott sztring által reprezentált színezés mellett (a továbbiakban a példában a színek angol kezdőbetűit tartalmazó imént bevezetett csúcsneveket/betűket használjuk). Tehát minden sztring egy-egy lehetséges gráf(csúcs)színezést kódol, pl. a sr1r2...rmt azt, amiben minden csúcs pirosra van színezve. Tehát a kiindulási halmaz megvan, az algoritmus lépései a következők:


SZŰRŐ MODELL ALGORITMUSA gráf 3-színezéshez
Input:  gráf maximális útjai, mint T multihalmaz, illetve a G=(V,E) input gráf 
1: for each (ai,aj) ∈ E do
2:    szétválaszt(T,Tr,Tbg,ri)
3:    szétválaszt(Tbg,Tb,Tg,bi)
4:    szétválaszt
5:    szétválaszt
6:    szétválaszt
7:    egyesít
8: end for 
9: detektál(T)

Az algoritmus működési elve a következő: A lényegi rész egy for ciklusból áll, amely az input gráf minden egyes élére lefut. A ciklus magjában először (2-3 lépés) megvizsgáljuk az él első csúcsának színét, ez alapján az adott színezést reprezentáló sztring a Tr, Tb, illetve Tg (multi)halmazba kerül. Ezután az adott él második csúcsának megvizsgálásával (4-6 lépések) kiszűrjük azokat a színezéseket, amelyekben az adott él mindkét végpontja azonos színnel van színezve (pl. halmazba kerül a sztring, ha mindkét csúcs piros az adott színezés szerint). A 7. lépésben a T halmazba egyesítjük azokat a sztringeket, amelyek olyan színezést tartalmaznak, amiben a jelenleg vizsgált él csúcspontjai is különböző színűek (azon színezések, amikben már egy korábban vizsgált élre azonos volt a végpontok színe, már korábban ki lettek szűrve). Végül, miután az ellenőrzés minden élre megtörtént, nem marad más, mint megnézni, hogy maradt-e olyan színezés, amit nem szűrtünk ki, vagyis minden élére teljesül G-nek, hogy az adott színezés mellett az él végei különböző színűek.

16. Feladat. Futtassuk le/szimuláljuk az algoritmust a G = ({a1, a2, a3, a4, a5}, {(a1, a2), (a1, a3), (a1, a4), (a2, a4), (a3, a4), (a3, a5), (a4, a5)}) gráfra. Adjuk meg egy helyes 3-színezését a gráfnak.

17. Feladat. Adjunk meg olyan 5 csúcsú gráfot, amely nem színezhető 3 színnel a feladatnak megfelelően (nem 3-színezhető), szimuláljuk az algoritmust erre a gráfra is.

Amint láthatjuk az algoritmus a gráf éleinek számával arányos műveletet igényel (köszönhetően a masszív párhuzamosságnak), amivel szemben hagyományos számítógépen csak a gráf méretével exponenciális időben tudjuk megoldani.

A következő alfejezetekben a szűrő modell további változataiból mutatunk be néhány jelentősebbet.

4.1. Szűrés Blokkolással

Az ilyen típusú algoritmusok ugyancsak egy olyan kiindulási (multi)halmazból indulnak ki, amely a lehetséges megoldások egyszálú DNS kódjait tartalmazza. A megoldás előállításához ezesetben blokkoló láncokat használunk, ezek olyan komplementer DNS láncok, amik azokkal a megoldásjelölt láncokkal amelyek nem bizonyulnak megoldásnak teljes kétszálú molekulát hoznak létre, míg a megoldásokat reprezentáló láncok vagy teljesen egyszálúak maradnak, vagy csak részben lesznek kétszálúak, a megvalósított kísérlettől függően.

A kiindulási halmaz el(ő)készítése után itt is különböző műveleteket használhatunk. A blokkoló halmazokat is hasonlóan kell el(ő)készíteni, tehát ezekre is feltétel, hogy egyszerűen elkészíthetőek legyenek.

A modell főbb műveletei, amikből az algoritmusok felépülnek, a következők:

  • sokszorosít(T): a T multihalmaz azon szavainak „erősítése", vagyis számuk sokszorosára emelése, amelyek nem blokkoltak;

  • az egyesítés és a

  • detektálás művelete az előző modellel azonos módon működik;

  • szekvenál(T): ez a művelet a T multihalmaz (lombik) egy nem blokkolt sztringjét adja (szükség lehet rá, ha nem csak egy igen-nem kérdésre keressük a választ).

A sokszorosítás művelete szorul egy kis magyarázatra, hiszen elsőre nem tűnik világosnak, hogy hogyan lehet a gyakorlatban a nem blokkolt elemek számát megsokszorozni anélkül, hogy a blokkolt láncokkal történne valami. Erre kínálhat megoldást a következő javaslat: a blokkoló molekulák nem DNS molekulák lesznek, hanem peptid nukleinsavak (PNS), ami kémiailag nagyon hasonlít a DNS-re és az RNS-re, de a természetben nem fordul elő egyetlen élőlényben sem. A PNS gerincét N-(2-aminóetil)-glicin egységek építik fel, amik egymáshoz peptidkötéssel kapcsolódnak. A szokásos purin és pirimidin bázisok pedig metilén-karbonil kötéssel kapcsolódnak a gerinchez. A PNS/DNS komplexek magasabb hőmérsékleten esnek szét, mint a DNS/DNS kettős spirál, ami lehetőséget ad arra, hogy ezen komplexek megbontása nélkül lehessen elvégezni a DNS láncok polimeráz láncreakcióját.

Tehát a szűrés nem a nem kívánt láncok eltávolításával történik, hanem éppen a rajtuk alkalmazott művelettel, a blokkolással. Ez a blokkolás végleges, vagyis az egyszer blokkolt szálak már nem befolyásolják a további számítást, így elvileg akár eltávolítottnak is tekinthetjük őket.

Ezeket alkalmazhatjuk pl. a SAT probléma megoldására a következő módon:

  1. Legyen adott egy konjunktív normálformájú propozícionális logikai formula n változóval ({x1, ..., xn}).

  2. Az összes lehetséges értékelést tekinthetjük n hosszúságú a {0,1} ábécé feletti sztringnek: z = a1 ... an, ahol a1, ..., an ∈ {0,1}, ai éppen az xi változó értéke a z által reprezentált kiértékelésben.

    Egy konjunktív normál formájú formulát egy értékelés akkor nem elégít ki, ha van olyan klóz (elemi diszjunkció) a formulában, ami az adott értékelés esetén hamis.

  3. Ennek megfelelően készítsük el a blokkoló(multi)halmazokat, minden klózhoz egyet: pl. az elemi diszjunkciónak megfelelő blokkolóhalmaz tartalmazza az összes olyan z = a1 a2 a3 a4 ... an lánc komplementerét, amelyben az a1 = 0, az a3 = 1, és az a4 = 0; vagyis a blokkolóhalmaz az összes olyan megoldásjelölt lánc blokkolására képes, amelyben ez a klóz nincs kielégítve.

  4. A formula összes elemi diszjunkciójára ismételjük meg az eljárást (a maradékot mindig sokszorosítva).

  5. Ezután már csak annak detektálása van hátra, hogy maradt-e megoldásként kiértékelés, ha magát a kielégítő kiértékelést is szeretnénk tudni, a szekvenálás műveletével tehetjük meg.

18. Feladat. Alkalmazza az előzőekben leírt blokkolással történő szűrő módszert a formulára. Melyik lépésben megy kiértékelések lesznek blokkolva? Kielégíthető-e a megadott formula?