DNA Computing Models

by Zimmermann, Karl-Heinz; Ignatova, Zoya; Martinez-perez, Israel Marck

• ISBN13: 9780387736358
• ISBN10: 0387736352
• Format: Hardcover
• Copyright: 2008-07-18
• Publisher: Springer-Verlag New York Inc

Summary

Sir Francis Crick would undoubtedly be at the front of the line ordering this fascinating book. Being one of the discoverers of DNA, he would be amazed at how his work has been applied to mankind's most important invention, the computer. DNA contains the genetic instructions for the biological development of cellular life forms or viruses. DNA computing uses DNA as a substrate for storing information, while molecular biological operations are used to manipulate this information.DNA Computing Models begins with a comprehensive introduction to the field of DNA computing. This book emphasizes computational methods to tackle central problems of DNA computing, such as controlling living cells, building patterns, and generating nanomachines. DNA Computing Models presents laboratory-scale human-operated models of computation, including a description of the first experiment of DNA computation conducted by Adleman in 1994. It provides molecular-scale autonomous models of computation and addresses the design of computational devices working in living cells. It also addresses the important problem of proper word design for DNA computing.DNA Computing Models is designed for researchers and advanced-level students in computers science, bioengineering and molecular biology as a reference or secondary text book. This book is also suitable for practitioners in industry.

Table of Contents

Introduction	p. 1
References	p. 7
Theoretical Computer Science	p. 9
Graphs	p. 9
Basic Notions	p. 9
Paths and Cycles	p. 11
Closures and Paths	p. 13
Trees	p. 14
Bipartite Graphs	p. 16
Finite State Automata	p. 16
Strings and Languages	p. 17
Deterministic Finite State Automata	p. 18
Non-Deterministic Finite State Automata	p. 19
Regular Expressions	p. 21
Stochastic Finite State Automata	p. 23
Computability	p. 25
Turing Machines	p. 25
Universal Turing Machines	p. 27
Church's Thesis	p. 29
Register Machines	p. 31
Cellular Automata	p. 31
Formal Grammars	p. 33
Grammars and Languages	p. 33
Chomsky's Hierarchy	p. 34
Grammars and Machines	p. 35
Undecidability	p. 36
Combinatorial Logic	p. 40
Boolean Circuits	p. 40
Compound Circuits	p. 42
Minterms and Maxterms	p. 43
Canonical Circuits	p. 44
Adder Circuits	p. 46
Computational Complexity	p. 48
Time Complexity	p. 48
Infinite Asymptotics	p. 49
Decision Problems	p. 51
Optimization Problems	p. 54
References	p. 54
Molecular Biology	p. 57
DNA	p. 57
Molecular Structure	p. 57
Manipulation of DNA	p. 60
Physical Chemistry	p. 63
Thermodynamics	p. 63
Chemical Kinetics	p. 65
DNA Annealing Kinetics	p. 68
Strand Displacement Kinetics	p. 68
Stochastic Chemical Kinetics	p. 69
Genes	p. 76
Structure and Biosynthesis	p. 77
DNA Recombination	p. 80
Genomes	p. 81
Gene Expression	p. 82
Protein Biosynthesis	p. 82
Proteins - Molecular Structure	p. 85
Enzymes	p. 88
Cells and Organisms	p. 92
Eukaryotes and Prokaryotes	p. 93
Viruses	p. 94
General Structure and Classification	p. 94
Applications	p. 95
References	p. 97
Word Design for DNA Computing	p. 99
Constraints	p. 99
Free Energy and Melting Temperature	p. 99
Distance	p. 100
Similarity	p. 101
DNA Languages	p. 104
Bond-Free Languages	p. 104
Hybridization Properties	p. 105
Small DNA Languages	p. 107
DNA Code Constructions and Bounds	p. 108
Reverse and Reverse-Complement Codes	p. 108
Constant GC-Content Codes	p. 111
Similarity-Based Codes	p. 113
In Vitro Random Selection	p. 117
General Selection Model	p. 118
Selective Word Design	p. 118
Concluding Remarks	p. 120
References	p. 120
Non-Autonomous DNA Models	p. 123
Seminal Work	p. 123
Adleman's First Experiment	p. 123
Lipton's First Paper	p. 126
Filtering Models	p. 127
Memory-Less Filtering	p. 127
Memory-Based Filtering	p. 128
Mark-and-Destroy Filtering	p. 129
Split-and-Merge Filtering	p. 131
Filtering by Blocking	p. 133
Surface-Based Filtering	p. 135
Sticker Systems	p. 138
Sticker Machines	p. 138
Combinatorial Libraries	p. 141
Useful Subroutines	p. 141
NP-Complete Problems	p. 149
Splicing Systems	p. 169
Basic Splicing Systems	p. 169
Recursively Enumerable Splicing Systems	p. 171
Universal Splicing Systems	p. 173
Recombinant Systems	p. 175
Concluding Remarks	p. 178
References	p. 178
Autonomous DNA Models	p. 181
Algorithmic Self-Assembly	p. 181
Self-Assembly	p. 181
DNA Graphs	p. 182
Linear Self-Assembly	p. 184
Tile Assembly	p. 185
Finite State Automaton Models	p. 194
Two-State Two-Symbol Automata	p. 194
Length-Encoding Automata	p. 198
Sticker Automata	p. 200
Stochastic Automata	p. 207
DNA Hairpin Model	p. 207
Whiplash PCR	p. 207
Satisfiability	p. 211
Hamiltonian Paths	p. 213
Maximum Cliques	p. 216
Hairpin Structures	p. 220
Computational Models	p. 222
Neural Networks	p. 222
Tic-Tac-Toe Networks	p. 226
Logic Circuits	p. 232
Turing Machines	p. 235
Concluding Remarks	p. 239
References	p. 239
Cellular DNA Computing	p. 243
Ciliate Computing	p. 243
Ciliates	p. 243
Models of Gene Assembly	p. 246
Intramolecular String Model	p. 249
Intramolecular Graph Model	p. 252
Intermolecular String Model	p. 256
Biomolecular Computing	p. 258
Gene Therapy	p. 258
Anti-Sense Technology	p. 259
Cell-Based Finite State Automata	p. 261
Anti-Sense Finite State Automata	p. 264
Basic Model	p. 265
Diagnostic Rules	p. 266
Diagnosis and Therapy	p. 266
Computational Genes	p. 269
Basic Model	p. 269
Diagnostic Rules	p. 271
Diagnosis and Therapy	p. 273
Concluding Remarks	p. 275
References	p. 276
Index	p. 279
Table of Contents provided by Ingram. All Rights Reserved.