9. fejezet - Konstruktív modellek

Tartalom

9.1. DNS kirakók és nanotechnológia
9.2. Logikai áramkörök szimulációja
9.3. DNS origami a gyakorlatban

A DNS számítások újabb generációja molekuláris méretű, autonóm, parciálisan programozható modelleket takar. A számítási folyamat a DNS molekulák önépítésével (self-assembly) zajlik, amit különböző enzimek segítségével irányíthatunk.

9.1. DNS kirakók és nanotechnológia

Az első önépítő DNS számítási modell E. Winfree nevéhez kötődik. Három alapvető műveletet használ: a DNS molekulák hidrogénkötéssel való összeragadása, a ligázzal való összekapcsolás (a foszfodiészter-kötés létrehozása adott láncon) és a denaturáció. Fizikai megvalósítás szintjén a következő műveletek használatosak:

  • különböző DNS molekulák szintetizálása,

  • DNS molekulák összekeverése az oldatban,

  • az oldat felmelegítése és lassú hűtése (ezáltal megfelelően összeragadt DNS molekulák előállítása),

  • ligáz enzim használata,

  • denaturálás megint,

  • a létrejött egyszálú DNS molekulák megvizsgálása, meghatározása.

A DNS csempéket használhatjuk pl. reguláris nyelvtanok kódolására.

36. Példa. Legyen G = ({S, A}, {a,b}, S, {S → λ, Sa, SaS, SbA, AaA, AbS}) reguláris nyelvtan. Használjuk az AGT-t az a kódjára, és az ACA-t a b kódolására (az 5'-től kezdődő felső láncon). Ekkor a 9.1. ábrán látható molekulákkal reprezentálható a nyelvtan (az S-nek megfelelő részt pirossal, az A-nak megfelelő részt kékkel, míg az a terminálisnak megfelelő részt zölddel, a b-nek megfelelő részt pedig narancssárgával jelöltük). A 9.2. ábra pedig az aa és a bb szavak levezetésének felel meg (az ábrán a terminálisoknak megfelelő színes DNS lánc részeket összeolva kapjuk a levezetett szót). A befejezett levezetést az jelzi, hogy teljes kétszálú molekula jött létre. Minden levezetést jelentő DNS molekula az S jelnek megfelelő (fekete színű) három bázispárral kezdődik.

9.1. ábra - Reguláris nyelvtan reprezentációja DNS molekulákkal.

Reguláris nyelvtan reprezentációja DNS molekulákkal.

9.2. ábra - Példa levezetések a reguláris nyelvtanban DNS molekulák önépítésével (a levezetett szót a zöld, illetve narancssárgával jelölt DNS kódrészek adják).

Példa levezetések a reguláris nyelvtanban DNS molekulák önépítésével (a levezetett szót a zöld, illetve narancssárgával jelölt DNS kódrészek adják).

43. Feladat. Adjunk meg DNS molekulákat a G = ({S, A, B}, {a,b}, S, {Sa, SaS, SbA, AbA, AbB, B →λ, BaS}) nyelvtanhoz, és adjunk meg legalább három termináló levezetéshez tartozó felépített DNS molekulát.

A szokásos kétdimenziós puzzle-okhoz hasonlóan DNS molekulák segítségével is lehet kirakósat játszani (vagyis maguktól kirakódnak a lehetséges alakzatok). Speciális dupla-kereszt molekulákat hozhatunk létre (lásd 9.3. ábra). A csempéhez a következő öt 5'-tól 3' irányban felírt egyszálú molekulára van szükség:

  • xyz,

  • uvw.

9.3. ábra - DNS csempék létrehozása 5 megfelelően összekapcsolt láncból.

DNS csempék létrehozása 5 megfelelően összekapcsolt láncból.

A kész csempét pedig tekinthetjük egy olyan négyzetnek, aminek oldalai a c, d, és ragadós végek (sematikusan ezt mutatja a 9.4. ábra), ezzel tud a csempe más csempékhez kapcsolódni.

9.4. ábra - DNS csempe sematikus rajza.

DNS csempe sematikus rajza.

Ilyen csempék segítségével pl. kétdimenziós fraktálokat is készíthetünk.

Sierpinski háromszög létrehozásához 7 különböző csempére van szükség. Ezeket mutatja sematikusan a 9.5. ábra. Itt nem jelöltük külön a komplementereket, a 9.4. ábrának megfelelően a felső oldalakat tekintjük normál oldalaknak, az alsó oldalait pedig a négyzeteknek a megadott kóddal jelölt oldal komplementerének. A megadott oldal nevek azt is jelzik, hogy milyen erősen tud összetapadni az adott oldal (a komplenterével): a k-vel jelölt oldalak tapadási ereje 2 (kettő), míg a másik két típusú oldalak (e0 és e1) esetén a tapadási erősség 1 (egy). Azt pl. a gyakorlatban a hőmérséklettel lehet szabályozni, hogy csak akkor maradjon ott egy csempe, ha legalább kettő összerősségű tapadása van.

9.5. ábra - DNS csempék a Sierpinski háromszög felépítéséhez.

DNS csempék a Sierpinski háromszög felépítéséhez.

Ilyen csempékből felépíthető a háromszögalak két oldala, mindenhol a 2-erősségű tapadást kihasználva az adott oldalon. Ezután a belső csempék két-két egy-egy tapadási erejű oldallal illeszthetőek be felépítve a háromszöget (lásd 9.6. ábra).

9.6. ábra - A Sierpinski háromszög felépítése a csempékkel.

A Sierpinski háromszög felépítése a csempékkel.

Valójában úgy lesz ebből a Sierpinski háromszögként ismert fraktál, vagyis annak egy véges része, ha az első és negyedik csempék – amelyek e0 felső oldalakkal rendelkeznek – megfelelnek egy adott színnek, a második és harmadik csempék – amelyek e1 felső oldalakkal rendelkeznek – pedig megfelelnek egy másik színnek. Folytassuk a csempézést, és fedezzük fel a Sierpinski háromszög szabályosságát!

Csemperendszerekkel készíthetünk bináris számlálókat: ekkor pl. alul és jobboldalon felépítünk egy keretet (ahogy az előbb is tettük, ott a derékszögű háromszög két befogójának megfelelő oldallal). A keretbe pedig olyan téglákat építünk, amik éppen az egész számok bináris kódjait jelentik (segítségül, lásd a 9.7. ábrát). A feladatnak az a lényege, hogy csak olyan alakzat épülhessen meg, ahol tényleg az egymást követő számok következnek.

9.7. ábra - Számláló vázlata csempékkel.

Számláló vázlata csempékkel.

Általánosabban is számlálónak nevezünk egy csemperendszert, ha téglalap alakban azzal, hogy eggyel növeljük a téglalap egyik oldalának (aljának) hosszát, pontosan megduplázzuk a ráépíthető téglalap másik oldalát (magasságát), ahogy a bináris kódolást használva, eggyel több számjegyet felhasználva kétszer annyiig tudunk elszámolni. Ezzel kapcsolatban érdekes kutatások folynak, hogy hogyan lehet minimális számú különféle csempe használatával ilyen számlálókat létrehozni.

Elméleti szempontból a csempemodell univerzális, vagyis képes pl. a Turing-gép szimulálására.