5. fejezet - DNS-dominók

Tartalom

5.1. A ragasztó számítási modell (sticker-based computation)
5.2. Nyelvek generálása

Az Adleman-féle problémamegoldás ötletét felhasználó, továbbfejlesztő számítási modellt, amit angolul sticker systems néven szoktak emlegetni ismertetjük ezekben a fejezetekben.

Ezekben a rendszerekben viszonylag kisméretű DNS-dominókból jönnek létre nagy(obb) méretű dupla DNS láncok. A DNS-dominók egyik vagy mindkét végükön ragadós véggel rendelkező kétszálú DNS láncok, illetve egyszálú DNS láncok. A felhasznált műveletek leginkább a ragadós végekkel történő összeragasztás (sticking), illetve a ligáz enzim segítségével történő „összehegesztés" (ligation). Ezeknek a rendszereknek az alapja a Watson-Crick komplementaritás.

Először viszont a hagyományos számítógépek algoritmusaihoz egy nagyon hasonlóan használható modellt mutatunk be, amivel a párhuzamosságot is felhasználva oldhatunk meg különböző problémákat.

5.1. A ragasztó számítási modell (sticker-based computation)

Ebben a fejezetben a DNS-dominókat egy fix méretű memóriában adattárolásra, mint memóriaegységeket használjuk, hasonlóan a hagyományos számítógépeink RAM-jához. Először is nézzük tehát, hogy hogyan tárolhatjuk az információt ilyen DNS dominókkal.

Legyen adott egy egyszálú hosszú DNS lánc, ez lesz a memória-lánc (memory strand). Legyen ez oly módon felépítve, hogy n darab nem átfedő m hosszúságú láncból álljon, oly módon, hogy ezen láncok mindegyike csak pontosan egyszer forduljon elő részláncként a memória-láncban. Ekkor Egy kis példát mutat a 5.1. ábra, ahol n = 5 és m = 6.

5.1. ábra - Memória DNS-dominókkal.

Memória DNS-dominókkal.

A rendszer az adott memórialáncot rengeteg példányban tartalmazhatja. Minden egyes ilyen memória-lánc m hosszúságú egységekre osztható, és minden ilyen egység esetén vagy oda van tapadva az adott rész komplementer dominója, vagy nem. Ez pont annak felel meg, hogy az adott n-hosszú bitlánc aktuális bitje IGEN vagy NEM, az adott memóriaegység 'be'- vagy 'ki' van kapcsolva. Ennek megfelelően a rendszert tekinthetjük úgy, mint adott hosszúságú {0,1}*-beli szavak multihalmaza, vagy bináris kódban tekintett egészek multihalmaza. Tehát a memóriaegységeink általában tartalmaznak egyszeres és kétszeres láncrészeket. Az információ sűrűsége tehát egy ilyen rendszerben vehető m bázis/1 bit értéknek. (Ez ugyan messze áll az elméleti határértéktől, mely szerint akár 2 bitnyi információt is tárolhatunk egyetlen bázis/bázispár DNS molekulában, viszont kísérleti megvalósítás szintén sokkal megbízhatóbb.)

A memória megfelelő láncszakaszai tehát logikai ítéletváltozók lehetséges értékeit, vagy biteket kódolnak. Ily módon a DNS számítógéppel a digitális eszközökben megszokott kódolással tárolhatunk információt. Nézzük, most, hogy hogyan férhetünk hozzá, illetve módosíthatjuk; hogyan használhatjuk fel a memóriában tárolt információt.

A DNS memória multihalmazokkal a következő műveleteket végezhetjük:

  • egyesít(T1, ..., Tn): két vagy több multihalmaz uniója, vagyis a lombikok Tn-be való összeöntésével létrejövő elegy (eredetileg a Tn üres is lehetett) (n ∈ ℕ).

  • szétválaszt(T,T1,T0,i): a T lombik tartalmának kettéválasztása a T1 és a T0 lombikokba, az alapján, hogy az i. bit bekapcsolt (1), vagy kikapcsolt (0) állapotban van. (Mintegy mellékhatásként, ilyenkor az eredeti T lombik tartalma kiürül.)

  • bekapcsol(T,i): a T lombik minden memóriaegységében az i. bit bekapcsolása (1-re állítása).

  • kikapcsol(T,i): a T lombik minden memóriaegységében az i. bit kikapcsolása (0-ra állítása).

  • kiönt(T): a T lombik felszabadítása: tartalmának kiöntése.

Az egyesítést egyszerű összeöntéssel végezhetjük le. A szétválasztáshoz, a pecázás művelethez hasonlóan, próbát használhatunk az adott részlánc komplementerével, amit a lombik falára ragaszthatunk. Ezekhez hozzátapadva maradnak azok a láncok, ahol a megfelelő láncrész még szabadon volt (0 bit érték, vagyis NEM). Így szétválasztható fizikailag is a tartalom. Másrészt viszont a próbához használt molekuláknak olyanoknak kell lenniük, amik könnyen leválaszthatók a memória láncról, könnyebben mint a dominók, hogy a memória tartalma ne változzon a művelet során. Erre egy egyszerű lehetőség, ha a próbához a dominóknál rövidebb láncot használunk (ami így könnyebben leszakítható), de más lehetséges módszerekkel is megoldható, melyeket itt nem részletezünk (lásd pl. [Roweis et al.] cikkben). A bekapcsolás művelete a lombikba tett megfelelő mennyiségű dominóval történik, amik beillenek a memória lánc megfelelő helyére. Technikailag megoldható a felesleges dominók eltüntetése (a memória láncok végeihez illesztett olyan véggel, amit nem használunk memóriaként tárolásra, és egyik dominó sem tud ehhez tapadni, kipecázhatóak a levesből a memórialáncok). A kikapcsolás technikailag a legnehezebben megvalósítható (részletekért a [Roweis et al.] cikket ajánljuk), de sokszor megkerülhető e művelet, nélküle is megoldható az adott feladat.

Egy számítás a DNS-dominókkal az előzőekben leírt utasítások egy véges sorozata egy kezdeti input(ot tartalmazó) lombikkal. Az outputot pedig egy lombiksorozattal definiáljuk, ezeket a lombikokat végső lombikoknak is hívjuk. Az output elolvasása, értelmezése történhet a végső lombikok tartalmának megnézésével: azok minden egyes memória egységét megvizsgálva (a rajta levő dominók leválasztásával, és azok azonosításával), vagy annak megállapításával, hogy az adott végső lombik nem tartalmaz memóriaegységet. Általában egy számítás során több lombikot is használunk, ezek eredetileg, a már említett input lombik kivételével, üresek.

Egy DNS-dominó gépet úgy képzelhetünk el, mint egy számítógépekkel irányított automata laboratóriumot, amely a megfelelő lombikokkal a megfelelő műveleteket végzi egymás után a számításnak (programnak) megfelelően.

Az input lombik legtöbbször egy előre elkészített memória könyvtár. Ezek az előre elkészített könyvtárak tartalmazhatják pl. n elem minden lehetséges k-kombinációját (ahol pont k bit van bekapcsolva az n bitből, ezek száma ), vagy minden lehetséges kombinációját (ebből 2n van). (Leginkább ahhoz hasonlóan, mint ahogy a Lipton-féle SAT probléma megoldáshoz előállított molekulahalmaz felhasználható más ugyanilyen változószámú formulák kielégíthetőségének kiszámításához...) Rendszerint a számításokhoz használt könyvtárak az első k bit összes lehetséges kombinációja mellett a maradék bitek 0 értékeit tartalmazó molekulák multihalmazát tartalmazzák, ezt (n,k) könyvtárnak hívjuk, és 2k-féle különböző memóriaegységet tartalmaz. Egy teljes (7,3)-könyvtár (sematikusan):

{0000000, 0010000, 0100000, 0110000, 1000000, 1010000, 1100000, 1110000}.

Egy ilyen (n,k) könyvtár memóriaegységeiben az első k elem tetszőleges k bites bináris számot jelenthet, ezek jelenthetik az aktuális inputot, míg a maradék n-k biten a részszámításokat, illetve az outputot tudjuk 'létrehozni'. Ennek megfelelően a dominó modell nehéz (pl. NP-teljes) problémák megoldására ajánl hatékony megoldást: az összes lehetséges 2k inputon egyszerre számolhatunk párhuzamosan, az összes lehetséges megoldásjelöltet egyszerre próbáljuk ki. (Hasonlóan ahhoz, mintha a nemdeterminisztikus algoritmusnál kitalálnánk a jó megoldást, amit NP-be eső probléma esetén polinomiális időben ellenőrizhetünk, csak itt nem kell találgatni sem, párhuzamosan minden jelöltet egyszerre ellenőrizhetünk.)

A rendszerrel változatos kombinatorikai és gráfelméleti feladatok oldhatóak meg hatékonyan. Az eredeti modell bemutatása a minimális halmaz lefedés problémájának megoldásával történt, amit a legtöbb ebben a témakörben íródott könyv, és így mi is átvettünk. A probléma a következőképpen írható le: Feltesszük, hogy van q zsák, mindben van néhány dolog. A dolgok p különböző félék lehetnek. A feladat, hogy találjuk meg a legkevesebb számú zsákot úgy, hogy tartalmukban legyen mindenféle dologból legalább egy. Már annak az igen/nem kérdésnek a megválaszolása is NP-teljes probléma, hogy van-e bármilyen n adott számra olyan n darab zsák, amivel 'lefedhetjük' a dolgainkat, vagyis mindenféle megtalálható belőlük a kiválasztott n zsákban. A következőkben formálisan adjuk meg a problémát és ismertetjük megoldását DNS-dominókkal.

13. Példa. Legyen p, q ∈ ℕ, S = {1, ..., p}, CiS (minden 1 ≤ iq esetén) továbbá legyen C = {C1, ..., Cq} ezen halmazok összessége. A feladat megadni egy/a minimális elemszámú I indexhalmazt (I ⊆ {1, ..., q}, hogy Lásd pl. 5.2. ábra.

A megoldás a DNS dominókkal a következőképpen megy:

Elkészítjük az összes lehetséges 2q részhalmaznak megfelelő tartalmat reprezentáló memóriaegységet. A használt memóriaegységek q + p bitnyi hosszúságúak, az utolsó p bit eredetileg minden memóriaegységen ki van kapcsolva. Az első q bit tehát, mint input azt jelenti, hogy mely zsákokkal próbáljuk lefedni a dolgok halmazát, a maradék p bit a különböző dolgok jelenlétét fogja jelenteni. Az első fázisban ennek megfelelően kapcsoljuk be az összes q + j bitet amire jCi (ezek az i. zsák tartalmának felelnek meg), azokban a memóriaegységekben, amikben az i.bit be van kapcsolva (vagyis ez a zsák is kiválasztott). Ezután, a második fázisban, ki kell választanunk azokat a memóriaegységeket, amikben az összes dologbit (q + 1, ..., q + p) bekapcsolt állapotban van (ezek a memóriaegységek reprezentálják azokat a zsákhalmazokat, amelyek lefedik a dolog halmazt). Ezek közül a minimális(ak) kiválasztásával, a harmadik fázisban, adhatjuk meg a megoldást.

Formálisan az algoritmus a következőképpen néz ki:


DNS-DOMINÓ ALGORITMUS minimális halmaz lefedéshez
Input: (q + p, q) könyvtár a T lombikban
**** első fázis: zsáktartalmak beállítása ****
1: for i = 1 to q do
2:    szétválaszt(T,T1,T0,i)
3:    for each jCi do 
4:      bekapcsol(T1,q+j)
5:    end for 
6:    egyesít(T1,T0,T)
7: end for
**** második fázis: lefedések kiválasztása ****
8: for i=q+1 to q+p do
9.    szétválaszt(T,T1,T0,i)
10.   egyesít(T1,T)     ** valójában csak átöntés **
11.   kiönt(T0)
12. end for
**** harmadik fázis: zsákok számának megállapítása ****
13. egyesít(T,T0)     ** átöntés: átnevezés **
14. for i=0 to q-1 do
15.    for j=i down to 0 do
16.      szétválaszt(Tj,T1,T0,i+1)
17.      egyesít(T1,Tj+1)
18.      egyesít(T0,Tj)
19.    end for
20. end for 
**** eredmény megadása **** 
21. a T1 megnézése: ha nem üres, akkor van 1 zsákkal lefedés, KÉSZ.
22. ha T1 üres, akkor T2 megnézése: ha nem üres, akkor van 2 zsákkal lefedés, KÉSZ.
23. ha T2 üres, akkor T3 megnézése: ha nem üres, akkor van 3 zsákkal lefedés, KÉSZ.
⋮
2q. ha Tq-1 üres, akkor Tq megnézése: ha nem üres, akkor az összes zsák lefedés, KÉSZ.
ha Tq is üres, akkor nincs lefedés, van olyan dolog, ami egyik zsákban sincs. 

Az algoritmus első része a q-val lineárisan arányos lépésszámmal, a második része pedig a p-vel lineárisan arányos lépésszámmal hajtható végre. A harmadik rész a legbonyolultabb algoritmuselméleti szempontból, ez a q-val négyzetesen arányos lépésszámmal oldható meg, az eredmény megadása, pedig megint maximum lineárisan arányos a q-val. Mindezek alapján azt mondhatjuk, hogy a feladat megoldásának ideje a paraméterektől négyzetesen függ. Ez kis fokszámú polinóm, tehát az algoritmus hatékony. Hogy hogyan lehet ez, ha NP-teljes problémáról van szó? A megoldás során erősen (masszívan) párhuzamos rendszert használtunk, amiben az algoritmus némelyik lépése a paraméterek függvényében exponenciális számú változást eredményezett. Tehát hagyományos számítási eszközzel, pl. Turing-géppel csak exponenciálisan sok lépésben szimulálható az algoritmus egy-egy lépése. A rendszer számítási ereje, gyorsasága tehát a masszív párhuzamosságban rejlik.

Lássuk hogyan működik az algoritmus egy konkrét példán:

14. Példa. Legyen 6 féle dolog és ezekből 4 zsák, ahogyan a 5.2. ábra is mutatja:

C1 = {1,3,4}, C2 = {5,6}, C3 = {2,3,6}, C4 = {1,2,4,5}.

5.2. ábra - A dolgok és zsákok (p=6 és q=4 ebben a konkrét példában).

A dolgok és zsákok (p=6 és q=4 ebben a konkrét példában).

Ekkor kiindulásként (10,4) könyvtárat használjuk, vagyis olyan 10 bitnyi hosszúságú memóriacellákat, amiken az első 4 bitnek mind a 24 = 16-féle kombinációja megtalálható, míg az utolsó 6 bit mindegyiknél üres (0 értékű).

Az első fázis után az első 4 biten kódolt zsákszámok alapján beállítjuk a további 6 bit értékét is a tartalmazott dolgoknak megfelelően. Az eredményt a 5.1. táblázat mutatja.

5.1. táblázat - A T lombikban levő memóriaegységek az algoritmus első fázisa után:

sorszám C1 C2C3C4123456 lefedett részhalmaz
1 0 0 00 0 00 0 00 {}
2 0 0 01 1 10 1 10 {1,2,4,5}
3 0 0 10 0 11 0 01 {2,3,6}
4 0 0 11 1 11 1 11 {1,2,3,4,5,6}
5 0 1 00 0 00 0 11 {5,6}
6 0 1 01 1 10 1 11 {1,2,4,5,6}
7 0 1 10 0 11 0 11 {2,3,5,6}
8 0 1 11 1 11 1 11 {1,2,3,4,5,6}
9 1 0 00 1 01 1 00 {1,3,4}
10 1 0 01 1 11 1 10 {1,2,3,4,5}
11 1 0 10 1 11 1 01 {1,2,3,4,6}
12 1 0 11 1 11 1 11 {1,2,3,4,5,6}
13 1 1 00 1 01 1 11 {1,3,4,5,6}
14 1 1 01 1 11 1 11 {1,2,3,4,5,6}
15 1 1 10 1 11 1 11 {1,2,3,4,5,6}
16 1 1 11 1 11 1 11 {1,2,3,4,5,6}

Az algoritmus második fázisában ezekből kiválasztjuk azokat, amelyek a teljes halmazt lefedik, vagyis minden dolgot tartalmaznak, ezeket mutatja a 5.2. táblázat.

5.2. táblázat - A T lombikban az algoritmus második fázisa után maradó memóriaegységek:

sorszám C1C2 C3 C4123456 lefedett részhalmaz
4 0 0 11 1 11 1 11 {1,2,3,4,5,6}
8 0 1 11 1 11 1 11 {1,2,3,4,5,6}
12 1 0 11 1 11 1 11 {1,2,3,4,5,6}
14 1 1 01 1 11 1 11 {1,2,3,4,5,6}
15 1 1 10 1 11 1 11 {1,2,3,4,5,6}
16 1 1 11 1 11 1 11 {1,2,3,4,5,6}

Ezután az algoritmus harmadik fázisában azt nézzük meg, hogy melyik memóriaegység hány zsák tartalmának megfelelően adja a lefedést. A 4. animáció mutatja az egymásba ágyazott for ciklusok működését, amíg az 5.3. ábrán azt mutatjuk be, hogy a külső for ciklus egy-egy lefutása után hogyan módosult a különböző indexű T lombikok tartalma. Az alsó index azt jelenti, hogy a már ellenőrzött zsákok közül mennyit használ fel az adott lefedés. A legalsó sor mutatja a végső elrendezést, itt már minden lefedés a helyére került, vagyis pontosan abba a Ti-be melyre teljesül, hogy az adott lefedésben pontosan i zsákot használtunk fel. Az animációban és az ábrán a memóriaegységek bitsorozata helyett azt mutatjuk, hogy melyiken mely zsákok bitjei vannak bekapcsolva, vagyis mely zsákok adják az adott lefedést (a zsákokra a tömörség kedvéért az indexeikkel hivatkozunk az animációban és az ábrán). Az animációban jól megfigyelhető, hogy a Tj lombikból az i+1-t, vagyis a Ci+1 zsákot tartalmazó lefedéseket mozgatjuk át a Tj+1 lombikba.

4. animáció - Az algoritmus harmadik fázisában a lefedések elhelyezése a megfelelő Ti lombikba a két egymásba ágyazott for ciklus segítségével.

5.3. ábra - A Ti lombikok tartalmának változása az algoritmus harmadik fázisában.

A Ti lombikok tartalmának változása az algoritmus harmadik fázisában.

Ez alapján a végeredmény megadása a következő: a példában nincs 1 zsákkal elérhető lefedés, de van 2 zsákkal elérhető lefedés: ilyen az ábrán a (3,4), vagyis a C3C4 két zsák tartalma kiadja a feladatban szereplő dolgok teljes {1,2,3,4,5,6} halmazát.

20. Feladat. Oldja meg a minimális lefedési problémát a {1,2,3,4,5,6,7} halmazra a C1={1,2,3,5}, C2={1,3,4}, C3={3,5,7}, C4={2,4,6,7}, C5={1,5,7} zsákokkal.

Elvileg a DNS-dominó rendszerekkel (megengedve a memória minden határon való túlnövését) Turing-gépek is szimulálhatóak, így számítási szempontból univerzálisnak tekinthető a modell. Sőt a már említett kikapcsolás művelet nélkül is univerzális a modell; e tulajdonságuknak megfelelően az ilyen modelleket 'egyszer írható' bitekkel rendelkező DNS-memória egységeknek nevezzük.

Kísérletileg a modell használatának, több más tényező mellett, határt szab az, hogy a 15 ezer bázispárnál hosszabb mesterséges DNS láncok már könnyen töredeznek, ennek megfelelően az alkalmazhatóság határa, ami még működik: kb. 12 ezer bázis hosszú memória lánc, 20 bázis hosszú dominókkal, ez 600 bitnyi tárhely... Habár ez a méret elég nagy, van egy sokkal erősebb fizikai korlátunk: egy lombikban levő molekulák száma nagyságrendileg nem lehet több (nincs több hely) a ~1024 nagyságrendnél, sőt a molekulák nagy része általában víz molekula szokott lenni, a számunkra értékes molekulák száma nagyságrendekkel ez alatt van. Ez azt mutatja hogy nem életszerű azt feltételeznünk, hogy a valódi életben is előforduló méretű minden nehéz problémát meg tudunk oldani DNS számításokkal...

A fejezet zárásaként, itt jegyezzük meg, hogy a [Ignatova et al.] könyvben számos gráfelméleti és más NP-teljes problémára is található hatékony algoritmus DNS-dominókkal.

21. Feladat. Adjon algoritmust DNS-dominókkal a Hamilton út problémára.

22. Feladat. Adjon algoritmust DNS-dominókkal a minimális csúcshalmaz lefedés problémára, amely a következő: adott gráf csúcspontjai közül adjunk meg egy minimális elemszámú részhalmazt úgy, hogy a gráf minden egyes csúcsa, vagy a kiválasztott részhalmazba essen, vagy legyen olyan csúcs a kiválasztott csúcsok részhalmazában, amellyel az adott csúcs össze van kötve egy éllel.