3. fejezet - Az első nagyhatású kísérletek

Tartalom

3.1. Adleman kísérlete
3.1.1. Hamilton-út probléma
3.1.2. A gráf kódolása DNS molekulákkal
3.1.3. A probléma megoldása
3.2. Lipton kísérlete
3.2.1. A SAT probléma
3.2.2. A SAT megoldása DNS molekulákkal
3.3. Megjegyzések az in vitro DNS számításokhoz

Most hogy már ismerjük a DNS molekulákat, és a velük végezhető alapvető műveleteket megnézzük, hogyan tudjuk őket felhasználni számítási feladatokhoz. Ebben a fejezetben bemutatjuk Adleman és Lipton nagyhatású kísérleti eredményeit, melyek a tudóstársadalom és a közvélemény számára is egyértelművé tették, hogy a DNS molekulák segítségével számítási (matematikai) problémákat is meg tudunk oldani. Nemcsak a természet, hanem mi magunk is kódolhatunk adatokat a DNS molekulákba, és számolhatunk velük...

3.1. Adleman kísérlete

1994-ben L. Adleman kísérlete jelentett áttörést. Végre a gyakorlatban is sikerült „számításra fogni" a DNS molekulákat: Adleman a Hamilton-út problémát egy konkrét hét csúcsú gráfra oldotta meg egy egy hetes kísérlet során.

3.1.1. Hamilton-út probléma

A Hamilton-út probléma a gráfelmélet egyik legismertebb NP-teljes (lásd pl. Függelék) problémája. Adott egy n csúcsú (irányított) gráf. A feladat, hogy megadjunk egy olyan élsorozatot, utat (vagy azt, hogy van-e ilyen a gráfban), amely a gráf minden csúcsát pontosan egyszer tartalmazza és benne (az első kivételével) minden él onnan indul, ahova az előző él érkezett. Az ilyen típusú utat hívjuk Hamilton-útnak. Semmilyen egyszerű feltétel nem ismert ilyen út létezésének eldöntésére (szemben pl. az Euler-út problémájával, ahol a gráf minden élének pontosan egyszer kell az útban szerepelnie, és ha a gráf összefüggő és legfeljebb két páratlan fokszámú csúcsa van, pontosan akkor van Euler-útja, vagy Euler-köre).

Ez esetben a polinomiálisan ellenőrizhető bizonyíték magának egy Hamilton-útnak a megadása.

Adleman a Hamilton-út problémát oldotta meg a 3.1. ábrán látható hét csúcsú gráfra.

3.1. ábra - Az Adleman által vizsgált gráf.

Az Adleman által vizsgált gráf.

Tehát erről a gráfról szeretnénk megtudni, hogy van-e benne olyan út, amely minden csúcsát pontosan egyszer érinti. Lássuk először, hogyan kódolhatjuk a gráfot DNS molekulák segítségével.

3.1.2. A gráf kódolása DNS molekulákkal

A gráf minden csúcsához hozzárendelünk egy-egy húsz nukleotid hosszúságú egyszeres DNS láncot.

Például a kísérletben a 2.-4. csúcsnak a következő láncok feleltek meg (5'-től 3' irányban):

2. csúcs: TATCGGATCG GTATATCCGA

3. csúcs: GCTATTCGAG CTTAAAGCTA

4. csúcs: GGCTAGGTAC CAGCATGCTT

Ezek a 20 hosszú láncok (angolul erre használhatjuk a 20-mer kifejezést) olyan 10 hosszúságú láncokból épülnek fel, amelyek egyediek, és komplementer láncaik is különböznek mindegyiktől.

Hasonlóan, a gráf éleihez is 20 hosszú egyszeres láncokat rendelünk, ezeket az előzőekben már meghatározott csúcsok láncainak segítségével definiáljuk. Ha egy x csúcsból vezet él az y csúcsba, akkor az y csúcs első tíz nukleotidjának komplementer láncához kapcsoljuk az x csúcs második tíz nukleotidjának megfelelő komplementerláncot.

Az Adleman példájánál maradva (5' → 3' irányban megadva):

a 2. csúcsból a 3.-ba mutató él: CATATAGGCT CGATAAGCTC

a 3. csúcsból a 2.-ba mutató él: GAATTTCGAT ATAGCCTAGC

a 3. csúcsból a 4.-be mutató él: GAATTTCGAT CCGATCCATG

Ennek a molekula tervezésnek köszönhetően, ha két csúcsot él köt össze, akkor a molekuláik a hidrogénkötésekkel össze tudnak kapcsolódni olyan kétszálú molekulákká, amikben az egyik szálon a csúcsok kódjai, míg a másik láncon a megfelelő élek kódjai találhatóak.

Sétának (walk) nevezünk a gráfban egy olyan csúccsal kezdődő és csúccsal végződő sorozatot, melyben csúcsok és élek felváltva következnek, és minden él éppen a között a két csúcs között szerepel a sorozatban, amelyeket összeköt. A kísérletben létrejött kétszálú DNS láncok így sétáknak felelhetnek meg, ha minkét végükön csúcsot kódoló szakasz van, míg az élek kódjaiból létrejött szál a sétának megfelelő utat kódolja. A másik lánc pedig ugyanehhez az úthoz tartozó csúcssorozatot. A továbbiakban az út fogalmat ilyen általánosabb értelemben használjuk, megengedve, hogy séta, vagy csúcssorozat reprezentálja azt.

8. Feladat. Írjon fel azoknak a molekuláknak a bázissorrendjét, amelyek

  • a 2.-tól a 3. csúcsba tartó egy élt tartalmazó utat,

  • a 2. csúcsból a 4. csúcsba vezető és közben a 3. csúcsot egyszer érintő utat,

  • a 3. csúcsból a 2. csúcsba, majd vissza és megint át a 2. csúcsba menő utat

kódolják.

A gráfot tekintve, például létrejöhet a 3.2. ábrán látható utat megtestesítő kétszálú DNS lánc.

3.2. ábra - A csúcsoknak és az éleknek megfelelő láncok kétszálú, utakat reprezentáló láncokká ragadhatnak össze.

A csúcsoknak és az éleknek megfelelő láncok kétszálú, utakat reprezentáló láncokká ragadhatnak össze.

9. Feladat. Adjon meg különböző hosszúságú utakat (2-9 csúcsot tartalmazókat) az adott gráfban, szemléltesse őket DNS molekulákkal, ahogy a 3.2. ábrán is tettük.

Valóban a molekulákkal ez is acélunk, hogy megfelelően összeragadhassanak... Lássuk hogyan érte ezt el Adleman a kísérletében.

3.1.3. A probléma megoldása

Az összes csúcsnak és élnek megfelelő láncot berakjuk a levesbe. Adleman olyan oldattal dolgozott, amiben 50 pmol töménységben volt jelen minden egyes csúcsnak és élnek megfelelő kódlánc. Ennek megfelelően, nagyságrendileg kb. 3 ˇ 1013 darab volt mindegyikből az oldatban. Ezután hagyjuk, hogy a megfelelő DNS láncok „egymásra találjanak". A folyamat során elméletileg előállhat az összes lehetséges út, gyakorlatilag ez elég nagy méretig így is van köszönhetően az elképzelhetetlenül sok molekulának, ami jelen van a levesben: minden viszonylag(?) rövid út meglesz az oldatban, és mind elég nagy számban.

Az oldathoz adott ligáz enzim biztosítja, hogy az egymás mellé kerülő csúcsokat reprezentáló láncdarabok kovalens kötéssel (foszfodiészter-kötés) is összekapcsolódjanak (illetve hasonlóan az éleket jelképező szálon is).

Denaturálással a létrejött utak szálait szétválasztjuk. Ezután végzünk egy hosszvizsgálatot és az összes megfelelő hosszúságú molekulát kivesszük: azokat amelyek hossza megegyezhet a Hamilton-út hosszával (jelen esetben ez a 7 csúcsszor 20 bázispár, vagyis 140 nukleotid).

Az így nyert csak a megfelelő hosszúságú mintákat tartalmazó oldatot sokszorosítás művelettel dúsítjuk. Ezután pecázás következik, először az első csúcsnak megfelelő komplementer szállal, az így nyert levesben biztos, hogy minden molekula tartalmazza az első csúcsot. Ennek megfelelően ebben a lépésben esnek ki azok a szálak is a vizsgálatból, amelyek 7 egymást követő él kódját tartalmazzák, vagyis a hosszuk megfelelő, de nem a csúcsokat reprezentálják, hanem a másik szál voltak eredetileg. Csak olyan szálak maradnak, amelyek 7 csúccsal reprezentálható utakat kódolnak és tartalmazzák az első csúcsot. A maradék oldatot megint sokszorosítással dúsítjuk, aztán pedig tovább pecázzuk a következő csúcsra, ezzel már csak olyan megfelelő hosszú molekulákat megtartva, amelyek az első mellett a második csúcsot is tartalmazzák. A folyamatot megismételve a maradék csúcsokra, végül ami marad az oldatban molekula, a probléma megoldását jelenti, mivel a keresett hosszúságú, és tartalmaz minden csúcsot.

Tehát végül azt kell eldöntetnünk, hogy maradt-e olyan DNS szálunk ami eleget tesz az összes előző mérésnek, kiválasztásnak.

10. Feladat. Oldja meg a feladatot Adleman gráfjára:

  1. írja fel az összes a 0. csúcsból induló 7 csúcsot tartalmazó utat, alkossák ezek az U0 halmazt. Tegyük fel, hogy itt tartunk a kísérlet során, vagyis megvannak azok a 7 csúcsból álló utakat reprezentáló molekuláink, amelyek tartalmazzák a 0. csúcsot. Pl. 0341213 ∈ U0.

  2. hajtsa végre a egymás után a többi csúcsokra egymás után a pecázási lépéseket (szűréseket), mikor mi szűrődik ki, és mi marad meg? Készítse el az U01, U012, U0123, ... U0123456 halmazokat.

  3. Adja meg a választ a problémára: van-e Hamilton-út a vizsgált gráfban?

Egyébként a példában a csúcsokat növekvő sorrendben végigjárva éppen egy Hamilton-utat kapunk, viszont a 2 → 3 él eltávolításával egy olyan gráfot kapunk, ami már nem tartalmaz Hamilton-utat.

Adleman a kísérletben olyan gráfból indult ki, aminek 0. csúcsából csak induló, utolsó (6.) csúcsában csak érkező élek vannak, ennek megfelelően csak olyan Hamilton-út létezhet, ami a 0. csúccsal kezdődik és a 6. csúccsal végződik. Ezt ki is használta a megoldás során: a megoldás akkor is ugyanez lesz, ha csak ilyen ismert végű utakat keresünk a kísérlet során. Ez a tény jól kihasználható a sokszorosítási fázisokban, ahol primereket kell az oldathoz adnunk.

11. Feladat. Szimulálja az algoritmus működését ennek megfelelően: legyen a kiindulási halmaz U06, amire folytatni kell a munkát olyan, hogy csak azok a 7 csúcsú utak vannak benne, amelyek 2 végpontja a 0., illetve a 6. csúcs.

Készítse el az U016, U0126, ..., U0123456 halmazokat.