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.
more »
« less
Parallel molecular computation on digital data stored in DNA
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
- Award ID(s):
- 2200290
- PAR ID:
- 10549835
- Publisher / Repository:
- National Academy of Sciences
- Date Published:
- Journal Name:
- Proceedings of the National Academy of Sciences
- Volume:
- 120
- Issue:
- 37
- ISSN:
- 0027-8424
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
James Aspnes and Othon Michail (Ed.)SIMD||DNA [Wang et al., 2019] is a model of DNA strand displacement allowing parallel in-memory computation on DNA storage. We show how to simulate an arbitrary 3-symbol space-bounded Turing machine with a SIMD||DNA program, giving a more direct and efficient route to general-purpose information manipulation on DNA storage than the Rule 110 simulation of Wang, Chalk, and Soloveichik [Wang et al., 2019]. We also develop software (https://github.com/UC-Davis-molecular-computing/simd-dna) that can simulate SIMD||DNA programs and produce SVG figures.more » « less
-
null (Ed.)Living systems require a sustained supply of energy and nutrients to survive. These nutrients are ingested, transformed into low-energy waste products, and excreted. In contrast, synthetic DNA strand-displacement reactions typically run within closed systems provided with a finite initial supply of reactants. Once the reactants are consumed, all net reactions halt and the system ceases to function. Here we run DNA strand-displacement reactions in a continuous flow reactor, infusing fresh reactants and withdrawing waste, enabling the system to dynamically update its outputs in response to changing inputs. Running DNA strand-displacement reactions inside of continuous flow reactors allows the system to be re-used for multiple rounds of computation, which could enable the execution of more elaborate information processing tasks, including single-rail negation and sequential logic circuitsmore » « less
-
more » « less
Abstract The ability to create stimuli-responsive DNA nanostructures has played a prominent role in dynamic DNA nanotechnology. Primary among these is the process of toehold-based strand displacement, where a nucleic acid molecule can act as a trigger to cause conformational changes in custom-designed DNA nanostructures. Here, we add another layer of control to strand displacement reactions through a 'toehold clipping' process. By designing DNA complexes with a photocleavable linker-containing toehold or an RNA toehold, we show that we can use light (UV) or enzyme (ribonuclease) to eliminate the toehold, thus preventing strand displacement reactions. We use molecular dynamics simulations to analyze the structural effects of incorporating a photocleavable linker in DNA complexes. Beyond simple DNA duplexes, we also demonstrate the toehold clipping process in a model DNA nanostructure, by designing a toehold containing double-bundle DNA tetrahedron that disassembles when an invading strand is added, but stays intact after the toehold clipping process even in the presence of the invading strand. This work is an example of combining multiple physical or molecular stimuli to provide additional remote control over DNA nanostructure reconfiguration, advances that hold potential use in biosensing, drug delivery or molecular computation.
-
more » « less
Abstract DNA has emerged as a powerful substrate for programming information processing machines at the nanoscale. Among the DNA computing primitives used today, DNA strand displacement (DSD) is arguably the most popular, with DSD-based circuit applications ranging from disease diagnostics to molecular artificial neural networks. The outputs of DSD circuits are generally read using fluorescence spectroscopy. However, due to the spectral overlap of typical small-molecule fluorescent reporters, the number of unique outputs that can be detected in parallel is limited, requiring complex optical setups or spatial isolation of reactions to make output bandwidths scalable. Here, we present a multiplexable sequencing-free readout method that enables real-time, kinetic measurement of DSD circuit activity through highly parallel, direct detection of barcoded output strands using nanopore sensor array technology (Oxford Nanopore Technologies’ MinION device). These results increase DSD output bandwidth by an order of magnitude over what is currently feasible with fluorescence spectroscopy.
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1073/pnas.2217330120
