DNS számítógépek és formális modelljeik

Benedek, Nagy


Tartalom

0. ELŐSZÓ
Előszó
A könyv használata
I. BEVEZETÉS
1. Kémiai és biológiai bevezetés
1.1. Kémiai bevezetés
1.1.1. Az atomok periódusos rendszere és elektronszerkezete
1.1.2. A hidrogén
1.1.3. A szén
1.1.4. A nitrogén
1.1.5. Az oxigén
1.1.6. A foszfor
1.1.7. Kémiai kötések
1.1.8. Molekulák
1.1.9. Kémiai reakciók
1.2. Biológiai alapok
1.2.1. A nukleotidok felépítése
1.2.2. Az egyszálú DNS
1.2.3. A kétszálú DNS: Watson-Crick komplementaritás és kettős spirál
II. SZÁMÍTÁSI PROBLÉMÁK MEGOLDÁSA A DNS MOLEKULÁKKAL - KEZDETI LÉPÉSEK
2. Műveletek a DNS molekulákkal - a DNS számítógépek „utasításai"
2.1. Denaturálás - a kétszálú DNS szálainak szétválasztása
2.2. Renaturálás vagy hibridizáció - kétszálú DNS lánc létrehozása
2.3. Szintetizálás - egyszálú DNS lánc mesterséges előállítása
2.4. Kétszálúvá kiegészítés - a polimeráz enzim
2.5. Sokszorosítás
2.6. Pecázás és szűrés - kiválasztás mintaillesztéssel
2.7. Hosszmérés - a gélelektroforézis
2.8. Szekvenálás - a bázissorrend meghatározása
2.9. Enzimek
2.9.1. A DNS szétvágása
2.9.2. A DNS összelinkelése, összeforrasztása - a ligáz enzim
3. Az első nagyhatású kísérletek
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
III. SZÁMÍTÁSI MODELLEK A DNS MOLEKULÁK, ILLETVE A VELÜK VÉGEZHETŐ MŰVELETEK ALAPJÁN
4. Szűrő modell
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
5. DNS-dominók
5.1. A ragasztó számítási modell (sticker-based computation)
5.2. Nyelvek generálása
6. Watson-Crick automaták
6.1. Hagyományos WK-automaták
6.1.1. Speciális változatok - hierarchia eredmények
6.2. 5'→3' WK-automaták
6.2.1. Biológiai motiváció
6.2.2. Formális leírás
6.2.3. 5'→3' WK-automata nyelvosztályok
6.2.4. 2detLIN nyelvek
6.2.5. Végigolvasó és többször végigolvasó (nem érzékeny) 5'→3' WK-automaták
7. Szétvágó-összeillesztő rendszerek
7.1. DNS-ek vágása és összeillesztése
7.1.1. DNS-ek vágása -- vágóenzimek újra
7.1.1 Ragadós végű DNS molekulák összeragadása
7.2. Elméleti leírás
7.2.1. Szétvágó-összeillesztő művelet nyelvekre
7.2.2. Iterált H-rendszerek
7.2.3. Kiterjesztett H-rendszerek
7.2.4. Multiplicitásos H-rendszerek
7.2.5. További H-rendszer modellek
8. Beszúró-törlő rendszerek
8.1. Beszúrás és törlés a DNS molekulákba
8.2. Beszúró-törlő rendszerek formális leírása
8.3. INSDEL nyelvosztályok
9. Konstruktív modellek
9.1. DNS kirakók és nanotechnológia
9.2. Logikai áramkörök szimulációja
9.3. DNS origami a gyakorlatban
IV. SZÁMÍTÁSOK - IN VIVO: MI TÖRTÉNIK AZ ÉLŐ SEJTBEN
10. Számítási folyamatok az élő sejtben
10.1. A csillós egysejtűek
10.2. A génképzési feladat
10.2.1. A mutatók szerepe a modellben
10.3. Génképzési modell több molekulával
10.4. Génképzés egy molekulán belül
10.4.1. A génképzés műveletei
10.4.2. A génképzés modellezése irreverzibilis műveletekkel
10.4.3. A génképzés sztring modellje
10.4.4. Átfedési gráf modell
10.4.5. Alkalmazási ötlet - elméletben
10.5. Sablonnal irányított rekombináció
11. Bioinformatika - a DNS számítások „komplementere"
11.1. A bioinformatika alapjai
11.2. Biológiai rendszerek modellezése
11.2.1. Tiltó-kötelező rendszerek
11.2.2. Reakciós rendszerek
11.2.3. Membrán rendszerek
11.3. A DNS számítások biológiai alkalmazásai
V. ZÁRÁSKÉNT: AMIRŐL SZÓ VOLT ÉS AMIRŐL NEM
12. Egyéb kutatási irányok
12.1. Számítás hajtű alakú DNS molekulákkal
12.2. DNS tervezés
12.3. Parciális szavak
12.4. DNS adatbázisok
12.5. DNS-Prolog
12.6. Számítások megfigyeléssel
13. Összefoglalás - a párhuzamosság és a Watson-Crick komplementaritás szerepe
13.1. A párhuzamosság formái
14. Ajánlott irodalom (tematikusan)
VI. FÜGGELÉK
15. Számítástudományi alapok
15.1. Formális nyelvek és generatív nyelvtanok
15.1.1. Ábécé, szavak és nyelv
15.1.2. Nyelvműveletek
15.1.3. Átíró és generatív rendszerek
15.1.4. A Chomsky hierarchia
15.1.5. Nyelvtanok normálformái
15.1.6. Nyelvosztályok tulajdonságai
15.2. Automaták
15.2.1. A véges automaták
15.2.2. A veremautomaták
15.2.3. A Turing-gép
15.3. Bonyolultságelméleti alapfogalmak

Az ábrák listája

1. A DNS számítások helye a számítástudományban (informatikában).
1.1. A (kémiai) elemek periódusos rendszere (az első 20 elemmel és besorolásukkal).
1.2. A hidrogén, a periódusos rendszer első eleme, és néhány jellemzője.
1.3. A vízmolekula szerkezeti képlete, az oxigénatom külső héjon található nemkötő elektronpárjaival.
1.4. A szén néhány jellemzője.
1.5. A gyémántrács felépítése: minden atom a térben négy másik atommal kapcsolódik (a bal felső sarokban a rács egységkockáját is feltüntettük).
1.6. A grafitrács felépítése: a szénatomok hatszögrácsos síkokat alkotnak.
1.7. A nitrogén néhány jellemzője.
1.8. Az oxigén néhány jellemzője.
1.9. A foszfor néhány jellemzője.
1.10. Az etilén (balra) és az acetilén (jobbra) szerkezeti képlete.
1.11. A benzol szerkezeti képlete, valójában minden atom bead egy elektront a közös kötésbe.
1.12. A glükóz nyílt és zárt formájú szerkezeti képlete.
1.13. Az adenin bázisának szerkezeti felépítése.
1.14. A citozin szerkezeti képlete: bázisa, a cukor (dezoxiribóz, pentóz) és a foszfátcsoport.
1.15. A guanin molekula szerkezete.
1.16. A timin molekula felépítése, a cukor szénatomjainak megjelölésével.
1.17. Az uracil molekula.
1.18. Egy nukleotid ionos formában: a cukor és a foszfát csoport szerkezete, kapcsolódása vizes oldatban.
1.19. Egy DNS lánc sematikus rajza.
1.20. Egy RNS lánc sematikus rajza (a cukrok 2' szénatomján jelölt OH is jelzi, hogy RNS-ről van szó).
1.21. A DNS molekula kettős spirál alakú, a két szálat a bázisok közti hidrogénkötések tartják össze.
1.22. A citozin és a guanin bázisai közt háromszoros hidrogénkötés alakulhat ki.
1.23. Az adenin és a timin molekulákat kétszeres hidrogénkötés tarja össze.
1.24. Az RNS-ben az adenin és az uracil molekulákat kétszeres hidrogénkötés tarja össze.
1.25. A két szálú DNS sematikusan.
1.26. Két RNS szál összekapcsódása sematikusan.
2.1. A polimeráz enzim kiegészíti a DNS láncot teljes duplalánccá.
2.2. Ismert végű kétszálú DNS-lánc előkészítése a polimeráz enzim számára a primerek segítségével.
2.3. DNS láncok szétválasztása hossz alapján gélelektroforézissel.
2.4. Egy lehetséges vágás „ragadós végek" létrehozásával.
2.5. Az EcoRI vágóenzim működése.
2.6. Az XmaI vágóenzim felismerési mintája és általa létrehozott ragadós végek.
2.7. Az SmaI vágóenzim működése.
2.8. A PstI vágóenzim működése.
2.9. A ligáz enzim működése.
3.1. Az Adleman által vizsgált gráf.
3.2. A csúcsoknak és az éleknek megfelelő láncok kétszálú, utakat reprezentáló láncokká ragadhatnak össze.
3.3. A három változóval rendelkező formulákhoz használható kiindulási gráf SAT problémához.
3.4. A példában megadott klózok literáljai szerint szűrünk.
5.1. Memória DNS-dominókkal.
5.2. A dolgok és zsákok (p=6 és q=4 ebben a konkrét példában).
5.3. A Ti lombikok tartalmának változása az algoritmus harmadik fázisában.
5.4. A DNS-dominók lehetséges alakja nyelvgeneráláshoz.
5.5. A DNS-dominók lehetséges összeragasztása molekula képzéshez: molekulaépítés jobb oldali irányban.
6.1. Egy Watson-Crick automata.
6.2. A {wcw ∣ w∈{a,b}*} nyelvet elfogadó WK-automata.
6.3. Az {anbncnn > 0} nyelvet elfogadó WK-automata.
6.4. Az {anbmcndmn,m > 0} nyelvet elfogadó WK-automata.
6.5. Egy nem szemilineáris nyelvet elfogadó WK-automata.
6.6. A jelölt másolat nyelvet elfogadó F1WK-automata.
6.7. Watson-Crick véges automata nyelvosztályok hierarchiája (a nyíl a tartalmazó osztály felé mutat).
6.8. Érzékeny 5'→3' Watson-Crick véges automata nyelvosztályok hierarchiája és viszonyuk a Chomsky-féle nyelvosztályokhoz.
6.9. Végigolvasó 5'→3' Watson-Crick véges automata amely a többszörös megfelelés nyelvét fogadja el.
6.10. Végigolvasó 5'→3' Watson-Crick véges automata amely a keresztfüggőségek nyelvét fogadja el.
6.11. Végigolvasó 5'→3' Watson-Crick véges automata nyelvosztályok hierarchiája és viszonyuk a Chomsky-féle nyelvosztályokhoz.
8.1. A beszúrás művelete sematikusan: adott környezetek közé adott szakasz beszúrása.
8.2. A törlés művelete sematikusan: adott környezet esetén a szál közbeeső része törlődik.
9.1. Reguláris nyelvtan reprezentációja DNS molekulákkal.
9.2. 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).
9.3. DNS csempék létrehozása 5 megfelelően összekapcsolt láncból.
9.4. DNS csempe sematikus rajza.
9.5. DNS csempék a Sierpinski háromszög felépítéséhez.
9.6. A Sierpinski háromszög felépítése a csempékkel.
9.7. Számláló vázlata csempékkel.
9.8. NAND kapuk csempékkel.
9.9. Számítás (kiértékelés) NAND csempékkel.
9.10. A smiley :) molekula „tervrajza".
9.11. A smiley molekulák létrejöttek.
9.12. Két DNS háromszög.
9.13. DNS hatszög a háromszögekből.
9.14. DNS szőnyeg hópihe mintákkal.
9.15. DNS szőnyeg térképpel (az Amerikát formázó minta háromszor fordul elő a szőnyegen).
10.1. Az MDS-ek egy lehetséges elhelyezkedése a mikronukleuszban.
10.2. A makronukleusz felépítése, az összerakott génsorozat.
10.3. A génképzés művelete DNS láncokkal.
10.4. Az ld operátor: IES rész eltávolítása.
10.5. A hi operátor: egy rész invertálása.
10.6. A dlad operátor: két rész felcserélése.
10.7. Az MDS-ek elhelyezkedése a 46. feladatban.
10.8. A mutatópárok elhelyezkedése a 41. példában.
10.9. Példa átfedési gráfra előjeles csúcsokkal.
10.10. Pozitívcsúcs szabály alkalmazása a 2-es csúcsra (a 10.9. ábra gráfjára).
10.11. Duplacsúcs szabály alkalmazása a 4-es 5-ös csúcspárra (a 10.9. ábra gráfjára).
12.1. Hajtű alakot formázó DNS lánc.
15.1. A fontosabb bonyolultsági osztályok hierarchiája (nem tudjuk, hogy mely tartalmazások valódiak).

A táblázatok listája

5.1. A T lombikban levő memóriaegységek az algoritmus első fázisa után:
5.2. A T lombikban az algoritmus második fázisa után maradó memóriaegységek:
7.1. Vágóenzimek, és működésük, valamint tömör leírásuk
11.1. A három betűs genetikai kódok, a kodonok 5'-től 3' irányban olvasva, és jelentésük: a megfelelő aminosavak és szokásos 3 betűs rövidítésük.
15.1. A Chomsky-féle nyelvosztályok zártsági tulajdonságai.