Design of a biomolecular device that executes process algebra

Process algebras are widely used for defining the formal semantics of concurrent communicating processes. This paper considers stochastic π-calculus which is a particularly expressive kind of process algebra providing a specification of probabilities of process behavior such as stochastic delays, communication and branching, as well as rates of execution. In this paper, we implement stochastic π-calculus at the molecular scale, providing a design for a DNA-based biomolecular device that executes the stochastic π-calculus. Designing this device is challenging due to the requirement that a specific pair of processes must be able to communicate repeatedly; this appears to rule out the use of many of the usual classes of DNA computation (e.g., tiling self-assembly or hybridization chain reactions) that allow computational rule molecules to float freely in solution within a test tube. Our design of the molecular stochastic π-calculus system makes use of a modified form of Whiplash-PCR (WPCR) machines. In our machine which we call π-WPCR machine, we connect (via a tethering DNA nanostructure) a number of DNA strands, each of which corresponds to a π-WPCR machines. This collection of π-WPCR machines is used to execute distinct concurrent processes, each with its own distinct program. To implement process communication protocols, our modifications to the original design of WPCR machines include the incorporation of additional secondary structure in the single strand (stem-loop) as well as multiple-temperature thermal cycling. The enforced locality of the collection of π-WPCR machines insures that the same pair (or any subset of the entire collection) of processes be able to repeatedly communicate with each other. Additionally, our design of the devices include implementation of sequential execution of multiple process and limited process branching through use of restriction enzymes. © 2011 Springer Science+Business Media B.V. (outside the USA).

Duke Scholars

Author John H. Reif Computer Science