DNA computing models

1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 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 vii viii Contents 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 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 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 Contents ix 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 Concluding Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 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 Concluding Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178 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 x Contents 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 Concluding Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239 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 Concluding Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 275 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 276 Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 279