Amos Theoretical and Experimental DNA Computation

1. Auflage 2005
ISBN: 978-3-540-28131-3
Verlag: Springer Berlin Heidelberg
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, 173 Seiten

Reihe: Natural Computing Series

This book provides a broad overview of the entire field of DNA computation, tracing its history and development. It contains detailed descriptions of all major theoretical models and experimental results to date and discusses potential future developments. It concludes by outlining the challenges currently faced by researchers in the field. This book will be a useful reference for researchers and students, as well as an accessible introduction for those new to the field.

Autoren/Hrsg.

Amos, Martyn

Inhaltsverzeichnis

1;Preface;6
2;Contents;9
3;Introduction;12
4;1 DNA: The Molecule of Life;16
4.1;1.1 Introduction;16
4.2;1.2 The Structure and Manipulation of DNA;17
4.3;1.3 DNA as the Carrier of Genetic Information;18
4.4;1.4 Operations on DNA;21
4.5;1.5 Summary;32
4.6;1.6 Bibliographical Notes;32
5;2 Theoretical Computer Science: A Primer;33
5.1;2.1 Introduction;33
5.2;2.2 Algorithms and Automata;35
5.3;2.3 The Turing Machine;37
5.4;2.4 The Random Access Machine;39
5.5;2.5 Data Structures;43
5.6;2.6 Computational Complexity;49
5.7;2.7 P and NP;53
5.8;2.8 Summary;53
5.9;2.9 Bibliographical Notes;54
6;3 Models of Molecular Computation;55
6.1;3.1 Introduction;55
6.2;3.2 Filtering Models;56
6.3;3.3 Splicing Models;70
6.4;3.4 Constructive Models;71
6.5;3.5 Membrane Models;73
6.6;3.6 Summary;79
6.7;3.7 Bibliographical Notes;80
7;4 Complexity Issues;81
7.1;4.1 Introduction;81
7.2;4.2 An Existing Model of DNA Computation;83
7.3;4.3 A Strong Model of DNA Computation;86
7.4;4.4 Ogihara and Ray’s Boolean Circuit Model;87
7.5;4.5 An Alternative Boolean Circuit Simulation;92
7.6;4.6 Proposed Physical Implementation;94
7.7;4.7 Analysis;97
7.8;4.8 Example Application: Transitive Closure;98
7.9;4.9 P-RAM Simulation;100
7.10;4.10 The Translation Process;104
7.11;4.11 Assessment;110
7.12;4.12 A Worked Example: The List Ranking Problem;112
7.13;4.13 Summary;116
7.14;4.14 Bibliographical Notes;117
8;5 Physical Implementations;118
8.1;5.1 Introduction;118
8.2;5.2 Implementation of Basic Logical Elements;118
8.3;5.3 Initial Set Construction Within Filtering Models;119
8.4;5.4 Adleman’s Implementation;121
8.5;5.5 Evaluation of Adleman’s Implementation;124
8.6;5.6 Implementation of the Parallel Filtering Model;126
8.7;5.7 Advantages of Our Implementation;127
8.8;5.8 Experimental Investigations;128
8.9;5.9 Other Laboratory Implementations;144
8.10;5.10 Summary;154
8.11;5.11 Bibliographical Notes;154
9;6 Cellular Computing;155
9.1;6.1 Introduction;155
9.2;6.2 Successful Implementations;158
9.3;6.3 Gene Unscrambling in Ciliates;158
9.4;6.4 Biological Background;159
9.5;6.5 Models of Gene Construction;161
9.6;6.6 Summary;163
9.7;6.7 Bibliographical Notes;164
10;References;165
11;Index;174