Search for: All records

Understanding the algorithmic behaviors that are in principle realizable in a chemical system is necessary for a rigorous understanding of the design principles of biological regulatory networks. Further, advances in synthetic biology herald the time when we will be able to rationally engineer complex chemical systems and when idealized formal models will become blueprints for engineering. Coupled chemical interactions in a well-mixed solution are commonly formalized as chemical reaction networks (CRNs). However, despite the widespread use of CRNs in the natural sciences, the range of computational behaviors exhibited by CRNs is not well understood. Here, we study the following problem: What functions f : ℝ k → ℝ can be computed by a CRN, in which the CRN eventually produces the correct amount of the “output” molecule, no matter the rate at which reactions proceed? This captures a previously unexplored but very natural class of computations: For example, the reaction X 1 + X 2 → Y can be thought to compute the function y = min ( x 1 , x 2 ). Such a CRN is robust in the sense that it is correct whether its evolution is governed by the standard model of mass-action kinetics, alternatives such as Hill-function or Michaelis-Menten kinetics, or other arbitrary models of chemistry that respect the (fundamentally digital) stoichiometric constraints (what are the reactants and products?). We develop a reachability relation based on a broad notion of “what could happen” if reaction rates can vary arbitrarily over time. Using reachability, we define stable computation analogously to probability 1 computation in distributed computing and connect it with a seemingly stronger notion of rate-independent computation based on convergence in the limit t → ∞ under a wide class of generalized rate laws. Besides the direct mapping of a concentration to a nonnegative analog value, we also consider the “dual-rail representation” that can represent negative values as the difference of two concentrations and allows the composition of CRN modules. We prove that a function is rate-independently computable if and only if it is piecewise linear (with rational coefficients) and continuous (dual-rail representation), or non-negative with discontinuities occurring only when some inputs switch from zero to positive (direct representation). The many contexts where continuous piecewise linear functions are powerful targets for implementation, combined with the systematic construction we develop for computing these functions, demonstrate the potential of rate-independent chemical computation. 

Typical DNA storage schemes do not allow in-memory computation, and instead transformation of the stored data requires DNA sequencing, electronic computation of the transformation, followed by synthesizing new DNA. In contrast we propose a model of in-memory computation that avoids the time consuming and expensive sequencing and synthesis steps, with computation carried out by DNA strand displacement. We demonstrate the flexibility of our approach by developing schemes for massively parallel binary counting and elementary cellular automaton Rule 110 computation. 

Artificially designed molecular systems with programmable behaviors have become a valuable tool in chemistry, biology, material science, and medicine. Although information processing in biological regulatory pathways is remarkably robust to error, it remains a challenge to design molecular systems that are similarly robust. With functionality determined entirely by secondary structure of DNA, strand displacement has emerged as a uniquely versatile building block for cell-free biochemical networks. Here, we experimentally investigate a design principle to reduce undesired triggering in the absence of input (leak), a side reaction that critically reduces sensitivity and disrupts the behavior of strand displacement cascades. Inspired by error correction methods exploiting redundancy in electrical engineering, we ensure a higher-energy penalty to leak via logical redundancy. Our design strategy is, in principle, capable of reducing leak to arbitrarily low levels, and we experimentally test two levels of leak reduction for a core “translator” component that converts a signal of one sequence into that of another. We show that the leak was not measurable in the high-redundancy scheme, even for concentrations that are up to 100 times larger than typical. Beyond a single translator, we constructed a fast and low-leak translator cascade of nine strand displacement steps and a logic OR gate circuit consisting of 10 translators, showing that our design principle can be used to effectively reduce leak in more complex chemical systems. 

Synthetic biology is a rapidly emerging research area, with expected wide-ranging impact in biology, nanofabrication, and medicine. A key technical challenge lies in embedding computation in molecular contexts where electronic micro-controllers cannot be inserted. This necessitates effective representation of computation using molecular components. While previous work established the Turing-completeness of chemical reactions, defining representations that are faithful, efficient, and practical remains challenging. This paper introduces CRN++, a new language for programming deterministic (mass-action) chemical kinetics to perform computation. We present its syntax and semantics, and build a compiler translating CRN++ programs into chemical reactions, thereby laying the foundation of a comprehensive framework for molecular programming. Our language addresses the key challenge of embedding familiar imperative constructs into a set of chemical reactions happening simultaneously and manipulating real-valued concentrations. Although some deviation from ideal output value cannot be avoided, we develop methods to minimize the error, and implement error analysis tools. We demonstrate the feasibility of using CRN++ on a suite of well-known algorithms for discrete and real-valued computation. CRN++ can be easily extended to support new commands or chemical reaction implementations, and thus provides a foundation for developing more robust and practical molecular programs. 

Biological regulatory networks depend upon chemical interactions to process information. Engineering such molecular computing systems is a major challenge for synthetic biology and related fields. The chemical reaction network (CRN) model idealizes chemical interactions, abstracting away specifics of the molecular implementation, and allowing rigorous reasoning about the computational power of chemical kinetics. Here we focus on function computation with CRNs, where we think of the initial concentrations of some species as the input and the eventual steady-state concentration of another species as the output. Specifically, we are concerned with CRNs that are rate-independent (the computation must be correct independent of the reaction rate law) and composable (𝑓∘𝑔 can be computed by concatenating the CRNs computing f and g). Rate independence and composability are important engineering desiderata, permitting implementations that violate mass-action kinetics, or even “well-mixedness”, and allowing the systematic construction of complex computation via modular design. We show that to construct composable rate-independent CRNs, it is necessary and sufficient to ensure that the output species of a module is not a reactant in any reaction within the module. We then exactly characterize the functions computable by such CRNs as superadditive, positive-continuous, and piecewise rational linear. Our results show that composability severely limits rate-independent computation unless more sophisticated input/output encodings are used. 

DNA strand displacement cascades have proven to be a uniquely flexible and programmable primitive for constructing molecular logic circuits, smart structures and devices, and for systems with complex autonomously generated dynamics. Limiting their utility, however, strand displacement systems are susceptible to the spurious release of output even in the absence of the proper combination of inputs—so-called leak. A common mechanism for reducing leak involves clamping the ends of helices to prevent fraying, and thereby kinetically blocking the initiation of undesired displacement. Since a clamp must act as the incumbent toehold for toehold exchange, clamps cannot be stronger than a toehold. In this paper we systematize the properties of the simplest of strand displacement cascades (a translator) with toehold-size clamps. Surprisingly, depending on a few basic parameters, we find a rich and diverse landscape for desired and undesired properties and trade-offs between them. Initial experiments demonstrate a significant reduction of leak.