skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


Title: A geometric framework for reaction enumeration in computational nucleic acid devices
Cascades of DNA strand displacement reactions enable the design of potentially large circuits with complex behaviour. Computational modelling of such systems is desirable to enable rapid design and analysis. In previous work, the expressive power of graph theory was used to enumerate reactions implementing strand displacement across a wide range of complex structures. However, coping with the rich variety of possible graph-based structures required enumeration rules with complicated side-conditions. This paper presents an alternative approach to tackle the problem of enumerating reactions at domain level involving complex structures by integrating with a geometric constraint solving algorithm. The rule sets from previous work are simplified by replacing side-conditions with a general check on the geometric plausibility of structures generated by the enumeration algorithm. This produces a highly general geometric framework for reaction enumeration. Here, we instantiate this framework to solve geometric constraints by a structure sampling approach in which we randomly generate sets of coordinates and check whether they satisfy all the constraints. We demonstrate this system by applying it to examples from the literature where molecular geometry plays an important role, including DNA hairpin and remote toehold reactions. This work therefore enables integration of reaction enumeration and structural modelling.  more » « less
Award ID(s):
1814906
PAR ID:
10542524
Author(s) / Creator(s):
;
Publisher / Repository:
Royal Society
Date Published:
Journal Name:
Journal of The Royal Society Interface
Volume:
20
Issue:
208
ISSN:
1742-5662
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; (, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)
    Seki, Shinnosuke; Stewart, Jaimie Marie (Ed.)
    Localized molecular devices are a powerful tool for engineering complex information-processing circuits and molecular robots. Their practical advantages include speed and scalability of interactions between components tethered near to each other on an underlying nanostructure, and the ability to restrict interactions between more distant components. The latter is a critical feature that must be factored into computational tools for the design and simulation of localized molecular devices: unlike in solution-phase systems, the geometries of molecular interactions must be accounted for when attempting to determine the network of possible reactions in a tethered molecular system. This work aims to address that challenge by integrating, for the first time, automated approaches to analysis of molecular geometry with reaction enumeration algorithms for DNA strand displacement reaction networks that can be applied to tethered molecular systems. By adapting a simple approach to solving the biophysical constraints inherent in molecular interactions to be applicable to tethered systems, we produce a localized reaction enumeration system that enhances previous approaches to reaction enumeration in tethered system by not requiring users to explicitly specify the subsets of components that are capable of interacting. This greatly simplifies the user’s task and could also be used as the basis of future systems for automated placement or routing of signal-transmission and logical processing in molecular devices. We apply this system to several published example systems from the literature, including both tethered molecular logic systems and molecular robots. 
    more » « less
  2. ; ; ; ; ; (, Journal of The Royal Society Interface)
    Information technologies enable programmers and engineers to design and synthesize systems of startling complexity that nonetheless behave as intended. This mastery of complexity is made possible by a hierarchy of formal abstractions that span from high-level programming languages down to low-level implementation specifications, with rigorous connections between the levels. DNA nanotechnology presents us with a new molecular information technology whose potential has not yet been fully unlocked in this way. Developing an effective hierarchy of abstractions may be critical for increasing the complexity of programmable DNA systems. Here, we build on prior practice to provide a new formalization of ‘domain-level’ representations of DNA strand displacement systems that has a natural connection to nucleic acid biophysics while still being suitable for formal analysis. Enumeration of unimolecular and bimolecular reactions provides a semantics for programmable molecular interactions, with kinetics given by an approximate biophysical model. Reaction condensation provides a tractable simplification of the detailed reactions that respects overall kinetic properties. The applicability and accuracy of the model is evaluated across a wide range of engineered DNA strand displacement systems. Thus, our work can serve as an interface between lower-level DNA models that operate at the nucleotide sequence level, and high-level chemical reaction network models that operate at the level of interactions between abstract species. 
    more » « less
  3. ; ; ; ; (, DNA Computing and Molecular Programming 23)
    In contrast to electronic computation, chemical computation is noisy and susceptible to a variety of sources of error, which has prevented the construction of robust complex systems. To be effective, chemical algorithms must be designed with an appropriate error model in mind. Here we consider the model of chemical reaction networks that preserve molecular count (population protocols), and ask whether computation can be made robust to a natural model of unintended “leak” reactions. Our definition of leak is motivated by both the particular spurious behavior seen when implementing chemical reaction networks with DNA strand displacement cascades, as well as the unavoidable side reactions in any implementation due to the basic laws of chemistry. We develop a new “Robust Detection” algorithm for the problem of fast (logarithmic time) single molecule detection, and prove that it is robust to this general model of leaks. Besides potential applications in single molecule detection, the error-correction ideas developed here might enable a new class of robust-by-design chemical algorithms. Our analysis is based on a non-standard hybrid argument, combining ideas from discrete analysis of population protocols with classic Markov chain techniques. 
    more » « less
  4. ; (, Leibniz international proceedings in informatics)
    In molecular programming, the Chemical Reaction Network model is often used to describe real or hypothetical systems. Often, an interesting computational task can be done with a known hypothetical Chemical Reaction Network, but often such networks have no known physical implementation. One of the important breakthroughs in the field was that any Chemical Reaction Network can be physically implemented, approximately, using DNA strand displacement mechanisms. This allows us to treat the Chemical Reaction Network model as a programming language and the implementation schemes as its compiler. This also suggests that it would be useful to optimize the result of such a compilation, and in general to find effective ways to design better DNA strand displacement systems. We discuss DNA strand displacement systems in terms of "motifs", short sequences of elementary DNA strand displacement reactions. We argue that describing such motifs in terms of their inputs and outputs, then building larger systems out of the abstracted motifs, can be an efficient way of designing DNA strand displacement systems. We discuss four previously studied motifs in this abstracted way, and present a new motif based on cooperative 4-way strand exchange. We then show how Chemical Reaction Network implementations can be built out of abstracted motifs, discussing existing implementations as well as presenting two new implementations based on 4-way strand exchange, one of which uses the new cooperative motif. The new implementations both have two desirable properties not found in existing implementations, namely both use only at most 2-stranded DNA complexes for signal and fuel complexes and both are physically reversible. There are reasons to believe that those properties may make them more robust and energy-efficient, but at the expense of using more fuel complexes than existing implementation schemes. 
    more » « less
  5. ; ; ; ; (, Proceedings of the National Academy of Sciences)
    DNA is an incredibly dense storage medium for digital data. However, computing on the stored information is expensive and slow, requiring rounds of sequencing, in silico computation, and DNA synthesis. Prior work on accessing and modifying data using DNA hybridization or enzymatic reactions had limited computation capabilities. Inspired by the computational power of “DNA strand displacement,” we augment DNA storage with “in-memory” molecular computation using strand displacement reactions to algorithmically modify data in a parallel manner. We show programs for binary counting and Turing universal cellular automaton Rule 110, the latter of which is, in principle, capable of implementing any computer algorithm. Information is stored in the nicks of DNA, and a secondary sequence-level encoding allows high-throughput sequencing-based readout. We conducted multiple rounds of computation on 4-bit data registers, as well as random access of data (selective access and erasure). We demonstrate that large strand displacement cascades with 244 distinct strand exchanges (sequential and in parallel) can use naturally occurring DNA sequence from M13 bacteriophage without stringent sequence design, which has the potential to improve the scale of computation and decrease cost. Our work merges DNA storage and DNA computing, setting the foundation of entirely molecular algorithms for parallel manipulation of digital information preserved in DNA.< 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email