The Formal Language and Design Principles of Autonomous DNA Walker Circuits.
Simple computation can be performed using the interactions between single-stranded molecules of DNA. These interactions are typically toehold-mediated strand displacement reactions in a well-mixed solution. We demonstrate that a DNA circuit with tethered reactants is a distributed system and show how it can be described as a stochastic Petri net. The system can be verified by mapping the Petri net onto a continuous-time Markov chain, which can also be used to find an optimal design for the circuit. This theoretical machinery can be applied to create software that automatically designs a DNA circuit, linking an abstract propositional formula to a physical DNA computation system that is capable of evaluating it. We conclude by introducing example mechanisms that can implement such circuits experimentally and discuss their individual strengths and weaknesses.
Department of Physics, University of Oxford , Oxford OX1 2JD, U.K.
Michael A
MA
Boemo
Department of Physics, University of Oxford , Oxford OX1 2JD, U.K.
Alexandra E
AE
Lucas
Department of Physics, University of Oxford , Oxford OX1 2JD, U.K.
Andrew J
AJ
Turberfield
Department of Computer Science, University of Oxford , Oxford OX1 2JD, U.K.|Microsoft Research Cambridge , Cambridge CB1 2FB, U.K.
Luca
L
Cardelli
D039301:Computers, Molecular; D004247:DNA / Q000235:genetics*; D012984:Software
D004247:DNA
DNA computation; DNA walkers; Petri nets; distributed systems; logic gates