[DKTT13] Frits Dannenberg, Marta Kwiatkowska, Chris Thachuk and Andrew J. Turberfield. DNA walker circuits: computational potential, design, and verification. In Proc. 19th International Conference on DNA Computing and Molecular Programming (DNA 19), volume 8141 of LNCS, pages 31-45, Springer. September 2013. [pdf] [bib] [Investigates the reliability, performance and correctness of DNA walker circuits using probabilistic model checking and PRISM.]
Downloads:  pdf pdf (1.41 MB)  bib bib
Notes: The original publication is available at www.springerlink.com.
Abstract. Unlike their traditional, silicon counterparts, DNA computers have natural interfaces with both chemical and biological systems. These can be used for a number of applications including the precise arrangement of matter at the nanoscale and the creation of smart biosensors. Like silicon circuits, DNA strand displacement systems (DSD) can evaluate non-trivial functions. However, these systems can be slow and are susceptible to errors. It has been suggested that localised hybridization reactions could overcome some of these challenges. Localised reactions occur in DNA ‘walker’ systems which were recently shown to be capable of navigating a programmable track tethered to an origami tile. We investigate the computational potential of these systems for evaluating Boolean functions. DNA walkers, like DSDs, are also susceptible to errors. We develop a discrete stochastic model of DNA walker ‘circuits’ based on experimental data, and demonstrate the merit of using probabilistic model checking techniques to analyse their reliability, performance and correctness.