DNA Computing

✍ Scribed by Natasa Jonoska (editor), Nadriaan C. Seeman (editor)

• Publisher: Springer
• Year: 2002
• Tongue: English
• Leaves: 404
• Category: Library

✦ Synopsis

Biomolecular computing is an interdisciplinary ?eld that draws together mol- ular biology, chemistry, physics, computer science, and mathematics. DNA n- otechnology and molecular biology are key relevant experimental areas, where knowledge increases with each passing year. The annual international meeting on DNA-based computation has been an exciting forum where scientists of d- ferent backgrounds who share a common interest in biomolecular computing meetanddiscusstheirlatestresults. Thecentralgoalofthisconeren f ceisto bring together experimentalists and theoreticians whose insights can calibrate each other’s approaches. DNA7, The Seventh International Meeting on DNA Based Computers,washeldatTheUniversityofSouthFloridainTampa,FL, USA, June 10–13,2001. The organizerssought to attract the most signi?cant - centresearch,withthehighestimpactonthedevelopmentofthediscipline. The meeting had 93 registered participants from 14 countries around the world. The program committee received 44 abstracts, from which 26 papers were presented at the meeting, and included in this volume. In addition to these papers, the Program Committee chose 9 additional papers from the poster presentations, and their revised versions have been added to this volume. As is now a tradition, four tutorials were presented on the ?rst day of the meeting. The morning started with general tutorials by Erik Winfree (Caltech) andJunghueiChen(UniversityofDelaware),designedtobridgebetweentheir respectiveareasofexpertise,computerscienceandmolecularbiology. Mores- cialized tutorials on encoding DNA sequences and on non-standard DNA motifs and interactions were given in the afternoon by Anne Condon (University of British Columbia) and Nadrian C. Seeman (New York University), respectively.

✦ Table of Contents

DNA Computing
Preface
Organization
Table of Contents
An Object Oriented Simulation of Real Occurring Molecular Biological Processes for DNA Computing and Its Experimental Verification
Introduction
Modelling Molecular Biological Processes
A Probabilistic Approach to Model DNA Operations with Side Effects
Basic Ideas of the Simulation Tool
Comparison of Simulation and Reality
Conclusions
References
Towards Optimization of PCR Protocol in DNA Computing
Introduction
PCR
PCR in DNA Computing
Setting Experiment
The Reaction for Analysis
Design of DNA Sequence
The Orthogonal Array
Factors
Values of Other PCR Parameters
Experiments for Detecting Important Factors
Statistical Analysis
Analysis 1
Analysis 2
Discussion
Optimizations
Optimization for Amplifying DNA1
Optimization for Decreasing the Concentration Difference
Discussion
Concluding Remark
References
DNASequenceGenerator: A Program for the Construction of DNA Sequences
Introduction
Theoretical Background
DNA Sequence Generator
Results
In Silico
In Vitro
One Step Further: The DNASequenceCompiler
Conclusion
Acknowledgements
References
DNA Computing in Microreactors
Introduction
Benchmark Problem
Maximum Clique
Selection Procedure
DNA Library
Word Design
Synthesis of the DNA Library
DNA-computer Set-up
Microreactor Structures
Sorting Module
Clique Selection Module
Programmability
Etching Procedure
Set-up Overview
The Next Step: A $20$-node DNA-computer
Conclusion
Acknowledgement
References
Cascadable Hybridisation Transfer of Specific DNA between Microreactor Selection Modules
Introduction
Materials and Methods
Paramagnetic Beads and Oligodeoxynucleotides
DNA Immobilisation to Paramagnetic Beads
Microflow Reactor for Quantifying DNA Selection and Transfer
DNA Selection and Transfer Protocol on Beads in Microflow Reactor and Its Quantification
Fluorescence Quantification of DNA In Situ
Results and Discussion
Efficient Buffers for DNA Selection, Washing, and Release
Demonstration of Transfer of DNA between Two Selection Modules with Reversible Chemistry
Conclusions
References
Coding Properties of DNA Languages *
Introduction
Definitions and Notations
Involution-Freedom and Involution-Compliance
Decidability Issues
Splicing Systems That Preserve Good Encodings
References
Boundary Components of Thickened Graphs
Introduction
Thickning Graphs and Double Strand Numbers
Changes in Graphs and Double Strand Numbers
Some Computations Using Planar Projections
Relations to Genera and Euler Characteristics
References
Population Computation and Majority Inference in Test Tube
Introduction
Evaluation of Boolean Formulae
Probabilistic Interpretation of the Test Tube
Learning by Amplification and the Majority Inference
Mistake Bound for Updating by Amplification
Taking Account of PCR Replication Errors
Application to Intelligent DNA Chip
References
DNA Starts to Learn Poker
Introduction
The Advantages of DNA for Computing
Where Do Game Strategies Come from?
Complexity of Seeking Game Strategies
Simplified Poker via DNA
Strategies Are Learned by Playing Trillions of Simultaneous Hands Using DNA
Encoding Strategies in DNA Strands
The DNA Sequences Used
DNA Hairpin Extension Plays a Hand of Poker
Experimental Results
The Dealer and Player Independently Evolve Their Strategies
Regular Poker Would Use Similar Techniques
Anticipated Directions
References
PNA-mediated Whiplash PCR
Introduction
The Efficiency of Whiplash PCR
The Efficiency per Polymerase-DNA Encounter
The Mean Polymerase/DNA Encounter Rate
Comparison with Experiment
PNA-mediated WPCR
Inhibiting Backhybridization
The Efficiency of PNA Mediated WPCR
The Overall Extension Efficiency
The Parallelization of PWPCR
Conclusion
References
Biomolecular Computation in Virtual Test Tubes
Introduction
Virtual Test Tubes
Edna's Architecture
EdnaCo's Architecture
Experimental Results
Scaling Up Adleman's Experiment
Evaluation of CI Encodings
Evaluation of H-metric Encodings
Conclusions
Acknowledgements
References
Developing Support System for Sequence Design in DNA Computing
Introduction
Support System for Sequence Design
Evaluation Terms
Composition of a System
Experiments
Concluding Remarks
References
The Fidelity of the Tag-Antitag System
Introduction
TAT Fidelity: Equilibrium Model
The Error Probability per Hybridized Tag, $epsilon $
The Temperature Dependence of $epsilon $
The Input Dependence of $epsilon $
Simulations of TAT Fidelity
Estimation of the Equilibrium Constants
Simulation A - The Fidelity of the Small TAT System
Simulation B - The Scaling Behavior of Random Encoding Fidelity
Conclusions and Future Work
References
PUNCH: An Evolutionary Algorithm for Optimizing Bit Set Selection
Introduction
Program Architecture
``Computing on Surfaces" Using PUNCH
Introducing Folding Scores
Comparison to Contiguous Bit Sets
Omitting Base Equality
Rewarding a Three-Base System
Future Directions
References
Solving Knapsack Problems in a Sticker Based Model
Introduction
Sorting by Cardinality
A Filling Subroutine
Subset-Sum Problem
0/1 Bounded Knapsack Problem
0/1 Unbounded Knapsack Problem
Conclusions
References
A Clause String DNA Algorithm for SAT
Introduction
Propositional Satisfiability
The Extract Model
Contact Formulations of SAT
Clause String Formulation of SAT
The DNA Algorithm
Conclusions
References
A Proposal of DNA Computing on Beads with Application to SAT Problems
Introduction
DNA Computing on Beads
Techniques to Realize
Megaclone
MPSS
A Design of DNA Computing on Beads through SAT
Conclusion
References
Aqueous Solutions of Algorithmic Problems: Emphasizing Knights on a 3x3
Introduction
The Concept of Aqueous Computing
The Implementation Scheme Chosen Here
A Uniform Approach to Several Algorithmic Problems
Non-attacking Knights on a $3times 3$ Chessboard
Light in the Future for Aqueous Computing?
References
Solutions of Shortest Path Problems by Concentration Control
Introduction
Concentration Control for Shortest Path Problems
Algorithm
Simulation Experiment
Laboratory Experiments and Discussions
Experiments for a Graph
Result of Gel Analysis
Quantification and Identification of Generated DNA Paths by Specific Primers
Concuding Remarks
References
Another Realization of Aqueous Computing with Peptide Nucleic Acid
Introduction
PNA Writing
Preliminary Experiment
Memory State Copy
Conclusion
References
Experimental Confirmation of the Basic Principles of Length-only Discrimination
Introduction
Hamiltonian Path Algorithm and DNA Implementation
A Path through the Graph Is Formed if All the Edges and Vertices Comprising This Path Are Present in Solution
When Multiple Paths Are Possible, All Paths Are Formed
Conclusions
References
Experimental Construction of Very Large Scale DNA Databases with Associative Search Capability
Introduction
Overview
Prior Work
Current Work
Small Test DNA Library Experiments
Larger DNA Library Experiments
Extremely Large DNA Library Experiments
Associative Search in This Extremely Large DNA Library
Design and Synthesis of DNA Databases
Design of DNA Databases
Word and Block Set Design
Synthesis of Database
Experiments in DNA Search and Readout in the Small Library
Increasing the Number of Database Strands
Experiments in DNA Search and Readout in the Very Large Libraries
Computer Simulations
Conclusion and Future Applications
References
Operation of a Purified DNA Nanoactuator
Introduction
Operation Principle
Dimer Formation
Experiments and Results
Discussion
Conclusion
References
DNA Scissors
Introduction
DNA Scissors
Mechanism for Operation
FRET Observation of Closure and Opening of Scissors
Gel Electrophoresis Data
Control Experiments
Designed Dimer Cannot Form Closed Scissors
There Is a Specific Closing Strand for Each Pair of Scissors
Number of Strands Necessary for Formation of Scissors
Jaws Can Also Be Prised Farther Apart
Conclusions and Possible Application
Methods
Appendix
References
A Realization of Information Gate by Using Enterococcus faecalis Pheromone System
Introduction
Organic Materials in Molecular Computing
Information Carrier with Organic Materials
Pheromone-induced Conjugation of {em Enterococcus faecalis}
Design of {em E. faecalis} Information Gate
Realization Plan of {em E. faecalis} Information Gate
Outlines of Experimental Procedure
Experimental Confirmation of {em E. faecalis} Information Gate
Discussions
Acknowledgement
References
Patterns of Micronuclear Genes in Ciliates
Introduction
Gene Assembly in Ciliates
Formalizing the Gene Assembly in Ciliates
Preliminaries on Strings
Micronuclear Patterns
The String Pointer Reduction System
Successful Patterns for Realistic Strings
Preliminaries
$bf ld$-successful Patterns
${bf ld,bf hi}$-successful Patterns
${bf ld,bf dlad}$-successful Patterns
$bf dlad$-successful Patterns
$bf hi$-successful Patterns
${bf hi,bf dlad}$-successful Patterns
Discussion
References
Peptide Computing - Universality and Complexity
Introduction
Notations and Definitions
Solving Hamilton Path Problem
Solving Exact Cover by 3-Sets Problem
Universality Result
Conclusion
References
Programmed Mutagenesis Is a Universal Model of Computation
Introduction
Programmed Mutagenesis Systems Are Universal
Turing Machines and an Example of a Universal Turing Machine
A Formal Model of Programmed Mutagenesis
Proof Outline
Programmed Mutagenesis and Other DNA Computing Systems
References
Horn Clause Computation by Self-assembly of DNA Molecules
Introduction
Deductive Inference by Self-assembly of DNA
Simple Boolean Horn Clause Model
DNA Implementation
Validity of the Implementation
Substitutions by String Tiling
Extension for First-Order Logic
DNA Implementation
Computational Power
Discussion
3D Conformation of Branching Molecules
Bias and Errors in Hybridization
Analysis of Chemical Reactions
Random Substitutions
Conclusion
References
DNA-based Parallel Computation of Simple Arithmetic
Introduction
The Model
Representing Numbers
Basic Operations
Writing Numbers on the Chip
Bitwise Addition Modulo 2
Computing the Carry Bits
Discussion
References
On P Systems with Global Rules
Introduction
Basic Definitions
The Power of Splicing P Systems
The Power of Rewriting P Systems
Final Remarks
References
Computing with Membranes: Variants with an Enhanced Membrane Handling
Introduction: The Basic Idea
Handling the Membranes
A General Class of P Systems
The Computing Power
Solving SAT in Linear Time
References
Towards an Electronic Implementation of Membrane Computing: A Formal Description of Non-deterministic Evolution in Transition P Systems
Introduction
Static Structure of Transition P Systems
Multisets
Evolution Rules
Regions
Transition P System Static Structure
Transition P System Dymanic Structure
Regional Local Parallelism
Non-deterministic Evolution in a Transition P System
Towards a Software System
Conclusions
References
Insertion-Deletion P Systems
Introduction
Some Language Theory Prerequisites
P Systems with Insertion-Deletion Rules
The Generative Power
Conclusion
References
A Universal Time-Varying Distributed H System of Degree 1
Introduction
Basic Definitions
Main Result
Details
The Last New Result
References
A Note on Graph Splicing Languages
Introduction
Preliminaries
Splicing on Graphs
Self Cross-Over Graph Systems
References
Author Index