Rechnen mit DNA

Thomas Hinze schloss 1997 das Studium der Informatik ab. Nach einer Industrietätigkeit als Software-Entwickler promovierte er 2002 über "Universelle Modelle und ausgewählte Algorithmen des DNA-Computing", gefördert durch ein Stipendium der Studienstiftung des Deutschen Volkes. Derzeit ist er als wissenschaftlicher Mitarbeiter an der Friedrich-Schiller-Universität Jena tätig. Monika Sturm studierte Informatik an der Technischen Universität Dresden, Diplom 1977, Promotion 1989, während dieser Zeit Forschungs- und Entwicklungstätigkeit bei Robotron Elektronik Dresden, seit 1989 wissenschaftliche Mitarbeiterin an der Technischen Universität Dresden, Fakultät Informatik, Institut für Theoretische Informatik.

1;Vorwort;6
2;Inhaltsverzeichnis;8
3;1 Einführung;12
4;2 DNA-Computing Entwicklung des interdisziplinären Wissensgebietes;16
5;3 Mathematische Grundlagen des DNA- Computing;28
5.1;3.1 Grundbegriffe;33
5.1.1;3.1.1 Mengen;33
5.1.2;3.1.2 Funktionen;36
5.1.3;3.1.3 Multimengen;38
5.1.4;3.1.4 Graphen;40
5.1.5;3.1.5 Algebraische Strukturen;41
5.1.6;3.1.6 Formale Sprachen;42
5.1.7;3.1.7 Endliche Automaten;45
5.2;3.2 Ausgewählte konventionelle universelle Berechnungsmodelle;47
5.2.1;3.2.1 Deterministische und nichtdeterministische Turingmaschine;47
5.2.2;3.2.2 Klasse der µ-rekursiven Funktionen;53
5.2.3;3.2.3 Klasse der WHILE-Programme;58
5.2.4;3.2.4 Chomsky-Grammatiken zur Beschreibung rekursiv aufzählbarer Sprachen;62
5.2.5;3.2.5 Ungetypter .-Kalkül;68
5.3;3.3 Zusammenhänge zwischen konventionellen universellen Berechnungsmodellen;76
5.3.1;3.3.1 Transformation von Turingmaschinen in Chomsky- Grammatiken vom Typ 0;76
5.3.2;3.3.2 Transformation von Chomsky-Grammatiken vom Typ 0 in Turingmaschinen;77
5.3.3;3.3.3 Transformation von Turingmaschinen in WHILE- Programme;79
5.3.4;3.3.4 Transformation von WHILE-Programmen in Turingmaschinen;83
5.3.5;3.3.5 Transformation von µ-rekursiven Funktionen in WHILE-Programme;85
5.3.6;3.3.6 Transformation von WHILE-Programmen in µ-rekursive Funktionen;87
5.3.7;3.3.7 Transformation von µ-rekursiven Funktionen in .-Terme;90
5.3.8;3.3.8 Transformation von .-Termen in µ-rekursive Funktionen;95
5.4;3.4 Algorithmus- und Berechenbarkeitsbegriff;97
5.5;3.5 Ausgewählte komplexitätstheoretische Grundlagen;101
5.5.1;3.5.1 Komplexitätsmafle für Algorithmen;101
5.5.2;3.5.2 Komplexitätsklassen P und NP;103
5.5.3;3.5.3 Ausgewählte NP-vollständige Probleme;105
6;4 Molekularbiologische Grundlagen des DNA-Computing;108
6.1;4.1 DNA als Datenträger-Struktur und Eigenschaften;110
6.1.1;4.1.1 DNA-Einzelstr ange und ihre Prim arstruktur;110
6.1.2;4.1.2 DNA-Doppelstr ange und ihre Sekund arstruktur;113
6.1.3;4.1.3 DNA-Konformationen und Terti arstruktur;116
6.1.4;4.1.4 Eigenschaften von DNA-Str angen;118
6.2;4.2 Allgemeine Grundsätze zum laborpraktischen Umgang mit DNA;119
6.3;4.3 Gewinnen von DNA;121
6.3.1;4.3.1 DNA-Einzelstrangsynthese;122
6.3.2;4.3.2 DNA-Isolation aus Organismen;124
6.4;4.4 Mischen und Aufteilen von DNA in wässriger Lösung;125
6.4.1;4.4.1 Vereinigung;125
6.4.2;4.4.2 Aliquotierung;126
6.5;4.5 Knüpfen und Aufbrechen von Wasserstoffbrückenbindungen;127
6.5.1;4.5.1 Hybridisierung;128
6.5.2;4.5.2 Denaturierung;129
6.6;4.6 Enzymatische Reaktionen;130
6.6.1;4.6.1 Ligation;133
6.6.2;4.6.2 Restriktionsspaltung;135
6.6.3;4.6.3 Strangendenmodifikation;137
6.6.4;4.6.4 Polymerisation;139
6.6.5;4.6.5 Polymerase-Kettenreaktion;140
6.7;4.7 Separieren und Analysieren von DNA-Strängen;143
6.7.1;4.7.1 Avidin-Biotin-Separation;143
6.7.2;4.7.2 Gel-Elektrophorese;145
6.7.3;4.7.3 Sequenzierung;148
6.8;4.8 Systematisierung von DNA-Operationen und ihrer Seiteneffekte;150
7;5 Labornahe Simulation molekularbiologischer Prozesse auf DNA;154
7.1;5.1 Von realen Vorgängen aus Physik und Chemie zum mathematischen Modell Ideen und Ansätze;156
7.1.1;5.1.1 Grundlagen der Modellierung molekülbasierter Vorgänge;156
7.1.2;5.1.2 Parametrisierung molekülbasierter Vorgänge;160
7.1.3;5.1.3 Belegung der Parameter mit Anfangswerten;163
7.1.4;5.1.4 Dynamische Anpassung der Parameter;164
7.1.5;5.1.5 Behandlung von Kollisionen;166
7.1.6;5.1.6 Reaktionskinetik;168
7.2;5.2 Allgemeine Simulationsmethoden für molekülbasierte Vorgänge;172
7.2.1;5.2.1 Simulationsmethoden Klassifikation und Eigenschaften;172
7.2.2;5.2.2 Erzeugung von Zufallszahlen für stochastische Simulationen;175
7.2.3;5.2.3 Ausgewählte Kombinationen von Simulationsmethoden im Detail;180
7.3;5.3 Parametrisierung der Primär- und Sekundärstruktur von DNA;190
7.3.1;5.3.1 Erfassung der Primärstruktur durch Zeichenketten;190
7.3.2;5.3.2 Erfassung der Sekundärstruktur durch Bindungsma

"Eine sehr schöne Darstellung, die ein aktuelles Gebiet nebst den klassisch benachbarten Gebieten behandelt." Prof. Dr. Dieter Spreen, Universität Siegen "Eine gute Mischung aus theoretischen Grundlagen und praxisrelevanten Ausführungen. Ein ausgezeichneter Einstiegspunkt für alle, die sich mit der faszinierenden Welt des DNA-Computing vertraut machen wollen." Sergei Sawitzki

2 DNA-Computing – Entwicklung des interdisziplinären Wissensgebietes (S. 5-6)

Das DNA-Computing etablierte sich in den letzten Jahren zu einem interdisziplinären Fachgebiet. Es setzt die Entwicklungsgeschichte von Rechnerarchitekturen fort und wird aufbauend auf den Erkenntnissen der Theoretischen Informatik vom wissenschaftlichen Fortschritt auf dem Gebiet der Molekularbiologie getragen.

Zur Entwicklung der Rechentechnik haben maßgeblich Ideen beigetragen, die das Ziel verfolgten, geistige Kraft zu potenzieren und dabei Größenordnungen zu erreichen, die ein Mensch sich zwar noch vorstellen, geistig aber nicht mehr selbst ausf ühren kann. In den Anfängen ihrer Entwicklung wurde Rechentechnik eingesetzt, um Routinearbeiten auszuführen, vordergr ündig, um Menschen von Arbeit zu entlasten. Rechner nahmen jederzeit sowohl Einfluss auf die Entwicklung der gesellschaftlichen wie auch der sozialen Verhältnisse der Menschen. Umgekehrt wurde aber auch der Einsatz der Rechentechnik von diesen Verhältnissen beeinflusst und in ihrer Entwicklung vorwärts getrieben. Die Geschichte der Informatik als wissenschaftliche Disziplin verbindet sich praktisch eng mit rechnenden Systemen und Maschinen und damit einhergehend mit den einzelnen Entwicklungsetappen der Rechentechnik. Den Beginn ihrer Aufzählung entnimmt man den Überlieferungen zum Aufbau einfacher Rechenhilfsmittel. In den der Zeit der Antike zugeordnet wird.

Der Abakus, auch Soroban oder Suan-pan genannt, besteht aus einem Rahmen mit Kugeln oder Rechensteinen, die auf Drähten aufgefädelt bzw. in Schlitzen gef ührt werden. Die Kugeln oder Rechensteine (lat. calculi) stellen dabei durch ihre Lage eine bestimmte Zahl (entweder als ganze Zahl oder als Dezimalbruch) dar, d.h. die Basis bildet ein Stellenwertsystem. Die Rechenmöglichkeiten reichten von einfacher Addition und Subtraktion überMultiplikation und asiatischen Raum Anwendung.

Vor allem die Griechen und Römer nutzten den Abakus von der Antike – schon vor der allgemeinen Durchsetzung des arabischen Dezimalsystems – bis etwa ins 16. Jahrhundert. Nach dieser Zeit wurde er abgelöst durch die Napierschen Rechenstäbchen und im darauffolgenden Jahrhundert durch die Entwicklung eines mechanischen Rechenhilfsmittels nach Edmund Gunter, das nach dem Prinzip des späteren Rechenschiebers arbeitet. Mit Hilfe dieses Prinzips wurde die Multiplikation auf der Grundlage einer logarithmisch eingeteilten Skala m¨ oglich. In der Zwischenzeit waren durch Adam Ries das Dezimalsystem und die Rechengesetze des Dezimalsystems eingeführt.

Nach den anfänglichen Rechenhilfsmitteln war der Weg frei f ür die ersten mechanischen Rechenmaschinen. Wilhelm Schickard, ein Professor aus Tübingen, stellte 1623 seine zahnradgetriebene Rechenmaschine vor und leitete damit eine neue Entwicklungsetappe ein. Sie ist die älteste mechanische Rechenmaschine und wurde bekannt, da sie über vier Grundrechenarten verf ügte und automatisch einen ¨ Ubertrag in die nächste Zehnerdekade vornehmen konnte. Die Rechenmaschine von Blaise Pascal f ür die sechsstellige Addition mit Zehnerübertrag aus dem Jahr 1642 und ihre Erweiterung zur Rechenmaschine mit Staffelwerk f ür die vier Grundrechenarten aus dem Jahr 1673/74 von Gottfried Wilhelm von Leibniz setzten entscheidende Impulse f ür weitere Entwicklungen. So erkannte Leibniz, dass der komplizierte Mechanismus seiner Rechenmaschine durch die Einführung des Binärcodes anstelle des Dezimalcodes stark vereinfacht werden könnte. Auf dieser Idee aufbauend wurden das duale Zahlensystem und die Gesetze der Dualarithmetik formuliert. Die Rechenmaschine von Leibniz wurde entsprechend weiterentwickelt und in Serie produziert.