DNA computing models / Karl-Heinz Zimmermann, Zoya Ignatova, Israel Martinez-Perez.

Format:

Book

Author/Creator:

Zimmermann, Karl-Heinz.

Contributor:

Ignatova, Zoya.

Martinez-Perez, Israel Marck.

Series:

Advances in information security ; 52.

Advances in information security ; 52

Language:

English

Subjects (All):

Molecular computers.

Natural computation.

Physical Description:

xiii, 288 pages : illustrations ; 25 cm.

Place of Publication:

New York ; London : Springer, 2008.

Summary:

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 computer science, bioengineering and molecular biology as a reference or secondary textbook. This book is also suitable for practitioners in industry.

Contents:

2 Theoretical Computer Science 9

2.1 Graphs 9

2.1.1 Basic Notions 9

2.1.2 Paths and Cycles 11

2.1.3 Closures and Paths 13

2.1.4 Trees 14

2.1.5 Bipartite Graphs 16

2.2 Finite State Automata 16

2.2.1 Strings and Languages 17

2.2.2 Deterministic Finite State Automata 18

2.2.3 Non-Deterministic Finite State Automata 19

2.2.4 Regular Expressions 21

2.2.5 Stochastic Finite State Automata 23

2.3 Computability 25

2.3.1 Turing Machines 25

2.3.2 Universal Turing Machines 27

2.3.3 Church's Thesis 29

2.3.4 Register Machines 31

2.3.5 Cellular Automata 31

2.4 Formal Grammars 33

2.4.1 Grammars and Languages 33

2.4.2 Chomsky's Hierarchy 34

2.4.3 Grammars and Machines 35

2.4.4 Undecidability 36

2.5 Combinatorial Logic 40

2.5.1 Boolean Circuits 40

2.5.2 Compound Circuits 42

2.5.3 Minterms and Maxterms 43

2.5.4 Canonical Circuits 44

2.5.5 Adder Circuits 46

2.6 Computational Complexity 48

2.6.1 Time Complexity 48

2.6.2 Infinite Asymptotics 49

2.6.3 Decision Problems 51

2.6.4 Optimization Problems 54

3 Molecular Biology 57

3.1 DNA 57

3.1.1 Molecular Structure 57

3.1.2 Manipulation of DNA 60

3.2 Physical Chemistry 63

3.2.1 Thermodynamics 63

3.2.2 Chemical Kinetics 65

3.2.3 DNA Annealing Kinetics 68

3.2.4 Strand Displacement Kinetics 68

3.2.5 Stochastic Chemical Kinetics 69

3.3 Genes 76

3.3.1 Structure and Biosynthesis 77

3.3.2 DNA Recombination 80

3.3.3 Genomes 81

3.4 Gene Expression 82

3.4.1 Protein Biosynthesis 82

3.4.2 Proteins - Molecular Structure 85

3.4.3 Enzymes 88

3.5 Cells and Organisms 92

3.5.1 Eukaryotes and Prokaryotes 93

3.6 Viruses 94

3.6.1 General Structure and Classification 94

3.6.2 Applications 95

4 Word Design for DNA Computing 99

4.1 Constraints 99

4.1.1 Free Energy and Melting Temperature 99

4.1.2 Distance 100

4.1.3 Similarity 101

4.2 DNA Languages 104

4.2.1 Bond-Free Languages 104

4.2.2 Hybridization Properties 105

4.2.3 Small DNA Languages 107

4.3 DNA Code Constructions and Bounds 108

4.3.1 Reverse and Reverse-Complement Codes 108

4.3.2 Constant GC-Content Codes 111

4.3.3 Similarity-Based Codes 113

4.4 In Vitro Random Selection 117

4.4.1 General Selection Model 118

4.4.2 Selective Word Design 118

5 Non-Autonomous DNA Models 123

5.1 Seminal Work 123

5.1.1 Adleman's First Experiment 123

5.1.2 Lipton's First Paper 126

5.2 Filtering Models 127

5.2.1 Memory-Less Filtering 127

5.2.2 Memory-Based Filtering 128

5.2.3 Mark-and-Destroy Filtering 129

5.2.4 Split-and-Merge Filtering 131

5.2.5 Filtering by Blocking 133

5.2.6 Surface-Based Filtering 135

5.3 Sticker Systems 138

5.3.1 Sticker Machines 138

5.3.2 Combinatorial Libraries 141

5.3.3 Useful Subroutines 141

5.3.4 NP-Complete Problems 149

5.4 Splicing Systems 169

5.4.1 Basic Splicing Systems 169

5.4.2 Recursively Enumerable Splicing Systems 171

5.4.3 Universal Splicing Systems 173

5.4.4 Recombinant Systems 175

6 Autonomous DNA Models 181

6.1 Algorithmic Self-Assembly 181

6.1.1 Self-Assembly 181

6.1.2 DNA Graphs 182

6.1.3 Linear Self-Assembly 184

6.1.4 Tile Assembly 185

6.2 Finite State Automaton Models 194

6.2.1 Two-State Two-Symbol Automata 194

6.2.2 Length-Encoding Automata 198

6.2.3 Sticker Automata 200

6.2.4 Stochastic Automata 207

6.3 DNA Hairpin Model 207

6.3.1 Whiplash PCR 207

6.3.2 Satisfiability 211

6.3.3 Hamiltonian Paths 213

6.3.4 Maximum Cliques 216

6.3.5 Hairpin Structures 220

6.4 Computational Models 222

6.4.1 Neural Networks 222

6.4.2 Tic-Tac-Toe Networks 226

6.4.3 Logic Circuits 232

6.4.4 Turing Machines 235

7 Cellular DNA Computing 243

7.1 Ciliate Computing 243

7.1.1 Ciliates 243

7.1.2 Models of Gene Assembly 246

7.1.3 Intramolecular String Model 249

7.1.4 Intramolecular Graph Model 252

7.1.5 Intermolecular String Model 256

7.2 Biomolecular Computing 258

7.2.1 Gene Therapy 258

7.2.2 Anti-Sense Technology 259

7.3 Cell-Based Finite State Automata 261

7.4 Anti-Sense Finite State Automata 264

7.4.1 Basic Model 265

7.4.2 Diagnostic Rules 266

7.4.3 Diagnosis and Therapy 266

7.5 Computational Genes 269

7.5.1 Basic Model 269

7.5.2 Diagnostic Rules 271

7.5.3 Diagnosis and Therapy 273.

Notes:

Includes bibliographical references and index.

ISBN:

9780387736358

0387736352

OCLC:

173718697