DNA Computing and Molecular Programming

We have recently introduced an experimental method for the design and production of RNA-origami nanostructures that fold up from a single strand while the RNA is being enzymatically produced, commonly referred to as cotranscriptional folding. To realize a general and scalable architecture we have developed a theoretical framework for determining RNA crossover geometries, long-distance interactions, and strand paths that are topologically compatible with cotranscriptional folding. Here, we introduce a simple parameterized model for the A-form helix and use it to determine the geometry and base-pair spacing for the five types of RNA double-crossover molecules and the curvature resulting from crossovers between multiple helices. We further define a set of paranemic loop-loop and end-to-end interactions compatible with the design of folding paths for RNA structures with arbitrary shape and programmable curvature. Finally, we take inspiration from space-filling curves in mathematics to design strand paths that have high-locality, programmed folding kinetics to avoid topological traps, and structural repeat units that might be used to create infinite RNA ribbons and squares by rolling circle transcription.

We study the power of uncontrolled random molecular movement in a model of self-assembly called the nubots model. The nubots model is an asynchronous nondeterministic cellular automaton augmented with rigid-body movement rules (push/pull, deterministically and programmatically applied to specific monomers) and random agitations (nondeterministically applied to every monomer and direction with equal probability all of the time). Previous work on nubots showed how to build simple shapes such as lines and squares quickly—in expected time that is merely logarithmic of their size. These results crucially make use of the programmable rigid-body movement rule: the ability for a single monomer to push or pull large objects quickly, and only at a time and place of the programmers’ choosing. However, in engineered molecular systems, molecular motion is largely uncontrolled and fundamentally random. This raises the question of whether similar results can be achieved in a more restrictive, and perhaps easier to justify, model where uncontrolled random movements, or agitations, are happening throughout the self-assembly process and are the only form of rigid-body movement. We show that this is indeed the case: we give a polylogarithmic expected time construction for squares using agitation, and a sublinear expected time construction to build a line. Such results are impossible in an agitation-free (and movement-free) setting and thus show the benefits of exploiting uncontrolled random movement.

The computational power of stochastic chemical reaction networks (CRNs) varies significantly with the output convention and whether or not error is permitted. Focusing on probability 1 computation, we demonstrate a striking difference between stable computation that converges to a state where the output cannot change, and the notion of limit-stable computation where the output eventually stops changing with probability 1. While stable computation is known to be restricted to semilinear predicates (essentially piecewise linear), we show that limitstable computation encompasses the set of predicates in \(\Delta^0_2\) in the arithmetical hierarchy (a superset of Turing-computable). In finite time, our construction achieves an error-correction scheme for Turing universal computation. This work refines our understanding of the tradeoffs between error and computational power in CRNs.

We show that CRAs in maximally parallel manner are computationally equivalent to Turing machines, while the computational power of CRAs in sequential manner coincides with that of the class of Petri nets, which is in marked contrast to the result that RAs (in both maximally parallel and sequential manners) have the computing power of Turing universality ([7-9]). Intuitively, CRAs are defined as RAs without inhibitor functioning in each reaction, providing an offline model of computing by chemical reaction networks (CRNs).

Thus, the main results in this paper not only strengthen the previous result on Turing computability of RAs but also clarify the computing powers of inhibitors in RA computation.

Chemical reactions and diffusion can produce a wide variety of static or transient spatial patterns in the concentrations of chemical species. Little is known, however, about what dynamical patterns of concentrations can be reliably programmed into such reaction-diffusion systems. Here we show that given simple, periodic inputs, chemical reactions and diffusion can reliably emulate the dynamics of a deterministic cellular automaton, and can therefore be programmed to produce a wide range of complex, discrete dynamics. We describe a modular reaction-diffusion program that orchestrates each of the fundamental operations of a cellular automaton: storage of cell state, communication between neighboring cells, and calculation of cells’ subsequent states. Starting from a pattern that encodes an automaton’s initial state, the concentration of a “state” species evolves in space and time according to the automaton’s specified rules. To show that the reaction-diffusion program we describe produces the target dynamics, we simulate the reaction-diffusion network for two simple 1-dimensional cellular automata using coupled partial differential equations. Reaction-diffusion based cellular automata could potentially be built in vitro using networks of DNA molecules that interact via branch migration processes and could in principle perform universal computation, storing their state as a pattern of molecular concentrations, or deliver spatiotemporal instructions encoded in concentrations to direct the behavior of intelligent materials.

DNA self-assembly is a powerful technology for controlling matter at the nanometre to micron scale, with potential applications in high-precision organisation and positioning of molecular components. However, the ability to program DNA-only self-organisation beyond the microscopic scale is currently lacking. In this paper we propose a computational method for programming spatial organisation of DNA at the centimetre scale, by means of DNA strand displacement reaction diffusion systems. We use this method to analyse the spatiotemporal dynamics of an autocatalytic system, a predator-prey oscillator and a two-species consensus network. We find that both autocatalytic and oscillating systems can support travelling waves across centimetre distances, and that consensus in a spatial context results in the spontaneous formation of distinct spatial domains, in which one species is completely eliminated. Together, our results suggest that programmed spatial self-organisation of DNA, through a reaction diffusion mechanism, is achievable with current DNA strand displacement technology.

We study the set of output stable configurations of chemical reaction deciders (CRDs). It turns out that CRDs with only bimolecular reactions (which are almost equivalent to population protocols) have a special structure that allows for an algorithm to efficiently calculate the (finite) set of minimal output stable configurations. As a consequence, a relatively large sequence of configurations may be efficiently checked for output stability.

We also provide a number of observations regarding the semilinearity result of Angluin et al. [Distrib. Comput., 2007] from the context of population protocols (which is a central result for output stable CRDs). In particular, we observe that the computation-friendly class of totally stable CRDs has equal expressive power as the larger class of output stable CRDs.

We propose a theoretical framework that uses a novel DNA strand displacement mechanism to implement abstract chemical reaction networks (CRNs) on the surface of a DNA nanostructure, and show that surface CRNs can perform efficient algorithmic computation and create complex spatial dynamics. We argue that programming molecular behaviors with surface CRNs is systematic, parallel and scalable.

Sequence-specific DNA interactions are a powerful means of programming nanoscale locomotion. These systems typically use a DNA track that is tethered to a surface, and molecular interactions enable a signal or cargo to traverse this track. Such low copy number systems are highly amenable to mechanized analyses such as probabilistic model checking, which requires a formal encoding. In this paper we present the first general encoding of tethered DNA species into a formal language, which allows the interactions between tethered species to be derived automatically using standard reaction rules. We apply this encoding to a previously published tethered DNA circuit architecture based on hairpin assembly reactions. This work enables automated analysis of large-scale tethered DNA circuits and, potentially, synthesis of optimized track layouts to implement specific logic functions.

We present general results that are useful in showing closure and decidable properties of large classes of languages with respect to biologically-inspired operations. We use these results to prove new decidability results and closure properties of some classes of languages under hairpin-inversion, pseudo-inversion, and other bio-operations. We also provide a new approach for proving the undecidability of problems involving bio-operations for which the usual method of reduction to the undecidability of the Post Correspondence Problem (PCP) may not be easy to apply. Our closure and decidability results strengthen or generalize previous results.