Search for: All records

Polynomial time dynamic programming algorithms play a crucial role in the design, analysis and engineering of nucleic acid systems including DNA computers and DNA/RNA nanostructures. However, in complex multistranded or pseudoknotted systems, computing the minimum free energy (MFE), and partition function of nucleic acid systems is NP-hard. Despite this, multistranded and/or pseudoknotted systems represent some of the most utilised and successful systems in the field. This leaves open the tempting possibility that many of the kinds of multistranded and/or pseudoknotted systems we wish to engineer actually fall into restricted classes, that do in fact have polynomial time algorithms, but we've just not found them yet. Here, we give polynomial time algorithms for MFE and partition function calculation for a restricted kind of multistranded system called the 1D scaffolded DNA computer. This model of computation thermodynamically favours correct outputs over erroneous states, simulates finite state machines in 1D and Boolean circuits in 2D, and is amenable to DNA storage applications. In an effort to begin to ask the question of whether we can naturally compare the expressivity of nucleic acid systems based on the computational complexity of prediction of their preferred energetic states, we show our MFE problem is in logspace (the complexity class L), making it perhaps one of the simplest known, natural, nucleic acid MFE problems. Finally, we provide a stochastic kinetic simulator for the 1D scaffolded DNA computer and evaluate strategies for efficiently speeding up this thermodynamically favourable system in a constant-temperature kinetic regime. 

Rationally designed molecular circuits describable by well-mixed chemical reaction kinetics can realize arbitrary Boolean function computation yet differ significantly from their electronic counterparts. The design, preparation, and purification of new molecular components poses significant barriers. Consequently, it is desirable to synthesize circuits from an existing “fridge” inventory of distinguishable parts, while satisfying constraints such as component compatibility. Heuristic synthesis techniques intended for large electronic circuits often result in non-optimal molecular circuits, invalid circuits that violate domain-specific constraints, or circuits that cannot be built with the current inventory. Existing “exact” synthesis techniques are able to find minimal feedforward Boolean circuits with complex constraints, but do not map to distinguishable inventory components. We present the Fridge Compiler, an SMT-based approach to find optimal Boolean circuits within a given molecular inventory. Empirical results demonstrate the Fridge Compiler’s versatility in synthesizing arbitrary Boolean functions using three different molecular architectures, while satisfying user-specified constraints. We showcase the successful synthesis of all 256 three-bit and 65,536 four-bit predicate functions using a large custom inventory, with worst-case completion times of only seconds on a modern laptop. In addition, we introduce a unique class of cyclic molecular circuits that cover a larger number of Boolean functions than their conventional counterparts over a common inventory, often with significantly smaller implementations. Importantly, and absent in previous approaches specific to molecular circuits, the Fridge Compiler is logically sound, complete, and optimal for the user-specified cost function and component inventory. 

A barrier to wider adoption of molecular computation is the difficulty of implementing arbitrary chemical reaction networks (CRNs) that are robust and replicate the kinetics of designed behavior. DNA Strand Displacement (DSD) cascades have been a favored technology for this purpose due to their potential to emulate arbitrary CRNs and known principles to tune their reaction rates. Progress on leakless cascades has demonstrated that DSDs can be arbitrarily robust to spurious "leak" reactions when incorporating systematic domain level redundancy. These improvements in robustness result in slower kinetics of designed reactions. Existing work has demonstrated the kinetic and thermodynamic effects of sequence mismatch introduction and elimination during displacement. We present a systematic, sequence modification strategy for optimizing the kinetics of leakless cascades without practical cost to their robustness. An in-depth case study explores the effects of this optimization when applied to a typical leakless translator cascade. Thermodynamic analysis of energy barriers and kinetic experimental data support that DSD cascades can be fast and robust. 

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. 

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.