Recently, a range of information-processing circuits have been implemented in DNA by using strand displacement as their main computational mechanism. Examples include digital logic circuits and catalytic signal amplification circuits that function as efficient molecular detectors. As new paradigms for DNA computation emerge, the development of corresponding languages and tools for these paradigms will help to facilitate the design of DNA circuits and their compilation to nucleotide sequences.
We present a programming language for designing and simulating DNA circuits in which strand displacement is the main computational mechanism. The language includes basic elements of sequence domains, toeholds and branch migration, and assumes that strands do not possess any secondary structure. The language is used to model and simulate a variety of circuits, including an entropy-driven catalytic gate, a simple gate motif for synthesizing large-scale circuits and a scheme for implementing an arbitrary system of chemical reactions. The language is a first step towards the design of modelling and simulation tools for DNA strand displacement, which complements the emergence of novel implementation strategies for DNA computing.
DNA Strand Displacement Simulator (2014-0219)
- Web Simulator (requires Silverlight 4.0 for Windows or Mac).
- Documentation: Tutorial, User Manual and Release Notes.
- Command-line simulator: Windows, OS X and OCaml Bytecode.
- Contact: Andrew Phillips (email@example.com).
- Previous versions: 2013-0214; 2012-0920; 2011-0721
- DSD was developed by Matthew Lakin, Filippo Polo, Simon Youssef, Kathryn Gray, Rasmus Petersen and Andrew Phillips at Microsoft Research.
- Luca Cardelli assisted with extensive testing of DSD together with the design of the DSD language.
- Neil Dalchau assisted with the development of an ODE solver for DSD.
- Erik Winfree and his group have provided valuable feedback on DSD, together with Georg Seelig and his group.
- The core DSD language was developed in F#.
- DSD uses Dynamic Data Display for visualising simulation plots.
- DSD uses Microsoft Automatic Graph Layout for visualising networks.
- Yuan-Jyue Chen, Neil Dalchau, Niranjan Srnivas, Andrew Phillips, Luca Cardelli, David Soloveichik, and Georg Seelig, Programmable chemical controllers made from DNA, in Nature Nanotechnology, Nature Publishing Group, 29 September 2013
- Matthew R. Lakin, Andrew Phillips, and Darko Stefanovic, Modular verification of DNA strand displacement networks via serializability analysis, in International Conference on DNA Computing and Molecular Programming, Springer Verlag, September 2013
- Boyan Yordanov, Christoph Wintersteiger, Youssef Hamadi, Andrew Phillips, and Hillel Kugler, Functional Analysis of Large-scale DNA Strand Displacement Circuits, in International Conference on DNA Computing and Molecular Programming, Springer, September 2013
- Matthew Lakin, David Parker, Luca Cardelli, Marta Kwiatkowska, and Andrew Phillips, Design and Analysis of DNA Strand Displacement Devices using Probabilistic Model Checking, in Journal of the Royal Society Interface, vol. 9, no. 72, pp. 1470-1485 , The Royal Society, July 2012
- Matthew Lakin, Loïc Paulevé, and Andrew Phillips, Stochastic Simulation of Multiple Process Calculi for Biology, in Theoretical Computer Science, vol. 431, pp. 181-206, Elsevier, May 2012
- Matthew Lakin, Simon Youssef, Luca Cardelli, and Andrew Phillips, Abstractions for DNA circuit design, in Journal of the Royal Society Interface, vol. 9, no. 68, pp. 470-486, The Royal Society, March 2012
- Matthew Lakin, Simon Youssef, Filippo Polo, Stephen Emmott, and Andrew Phillips, Visual DSD: a design and analysis tool for DNA strand displacement systems, in Bioinformatics, vol. 27, no. 22, pp. 3211–3213, Oxford University Press, November 2011
- Harish Chandran, Nikhil Gopalkrishnan, Andrew Phillips, and John Reif, Localized Hybridization Circuits, in International Conference on DNA Computing and Molecular Programming, vol. 6937, pp. 64-83, Springer Verlag, September 2011
- Matthew Lakin and Andrew Phillips, Modelling, simulating and verifying Turing-powerful strand displacement systems, in International Conference on DNA Computing and Molecular Programming , vol. 6937, pp. 130-144, Springer Verlag, September 2011
- Andrew Phillips and Luca Cardelli, A programming language for composable DNA circuits, in Journal of the Royal Society Interface, 17 June 2009
Publications using DSD
- Lulu Qian, Erik Winfree & Jehoshua Bruck. Neural network computation with DNA strand displacement cascades. Nature 475: 368–372. July 2011.
- Lulu Qian and Erik Winfree. Scaling Up Digital Circuit Computation with DNA Strand Displacement Cascades. Science 332: 1196-1201. June 2011.
Publications citing DSD
- David Zhang and Georg Seelig. Dynamic DNA nanotechnology using strand displacement reactions. Nature Chemistry 3: 103-113. February 2011.