DNA Computing Models

Cover -- TOC$Contents -- CH$1 Introduction -- References -- CH$2 Theoretical Computer Science -- 2.1 Graphs -- 2.1.1 Basic Notions -- 2.1.2 Paths and Cycles -- 2.1.3 Closures and Paths -- 2.1.4 Trees -- 2.1.5 Bipartite Graphs -- 2.2 Finite State Automata -- 2.2.1 Strings and Languages -- 2.2.2 Deterministic Finite State Automata -- 2.2.3 Non-Deterministic Finite State Automata -- 2.2.4 Regular Expressions -- 2.2.5 Stochastic Finite State Automata -- 2.3 Computability -- 2.3.1 Turing Machines -- 2.3.2 Universal Turing Machines -- 2.3.3 Churchs Thesis -- 2.3.4 Register Machines -- 2.3.5 Cellular Automata -- 2.4 Formal Grammars -- 2.4.1 Grammars and Languages -- 2.4.2 Chomskys Hierarchy -- 2.4.3 Grammars and Machines -- 2.4.4 Undecidability -- 2.5 Combinatorial Logic -- 2.5.1 Boolean Circuits -- 2.5.2 Compound Circuits -- 2.5.3 Minterms and Maxterms -- 2.5.4 Canonical Circuits -- 2.5.5 Adder Circuits -- 2.6 Computational Complexity -- 2.6.1 Time Complexity -- 2.6.2 Infinite Asymptotics -- 2.6.3 Decision Problems -- 2.6.4 Optimization Problems -- References -- CH$3 Molecular Biology -- 3.1 DNA -- 3.1.1 Molecular Structure -- 3.1.2 Manipulation of DNA -- 3.2 Physical Chemistry -- 3.2.1 Thermodynamics -- 3.2.2 Chemical Kinetics -- 3.2.3 DNA Annealing Kinetics -- 3.2.4 Strand Displacement Kinetics -- 3.2.5 Stochastic Chemical Kinetics -- 3.3 Genes -- 3.3.1 Structure and Biosynthesis -- 3.3.2 DNA Recombination -- 3.3.3 Genomes -- 3.4 Gene Expression -- 3.4.1 Protein Biosynthesis -- 3.4.2 Proteins Molecular Structure -- 3.4.3 Enzymes -- 3.5 Cells and Organisms -- 3.5.1 Eukaryotes and Prokaryotes -- 3.6 Viruses -- 3.6.1 General Structure and Classification -- 3.6.2 Applications -- References -- 4 Word Design for DNA Computing -- 4.1 Constraints -- 4.1.1 Free Energy and Mel ting Temperature -- 4.1.2 Distance -- 4.1.3 Similarity -- 4.2 DNA Languages -- 4.2.1 Bond-Free Languages -- 4.2.2 Hybridization Properties -- 4.2.3 Small DNA Languages -- 4.3 DNA Code Constructions and Bounds -- 4.3.1 Reverse and Reverse-Complement Codes -- 4.3.2 Constant GC-Content Codes -- 4.3.3 Similarity-Based Codes -- 4.4 In Vitro Random Selection -- 4.4.1 General Selection Model -- 4.4.2 Selective Word Design -- Concluding Remarks -- References -- CH$5 Non-Autonomous DNA Models -- 5.1 Seminal Work -- 5.1.1 Adlemans First Experiment -- 5.1.2 Liptons First Paper -- 5.2 Filtering Models -- 5.2.1 Memory-Less Filtering -- 5.2.2 Memory-Based Filtering -- 5.2.3 Mark-and-Destroy Filtering -- 5.2.4 Split-and-Merge Filtering -- 5.2.5 Filtering by Blocking -- 5.2.6 Surface-Based Filtering -- 5.3 Sticker Systems -- 5.3.1 Sticker Machines -- 5.3.2 Combinatorial Libraries -- 5.3.3 Useful Subroutines -- 5.3.4 NP-Complete Problems -- 5.4 Splicing Systems -- 5.4.1 Basic Splicing Systems -- 5.4.2 Recursively Enumerable Splicing Systems -- 5.4.3 Universal Splicing Systems -- 5.4.4 Recombinant Systems -- Concluding Remarks -- References -- CH$6 Autonomous DNA Models -- 6.1 Algorithmic Self-Assembly -- 6.1.1 Self-Assembly -- 6.1.2 DNA Graphs -- 6.1.3 Linear Self-Assembly -- T$14917