Abstract
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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Single instruction, multiple data (SIMD) is one of the four classifications in Flynn’s taxonomy [7]. The taxonomy captures computer architecture designs and their parallelism. The four classifications are the four choices of combining single instruction (SI) or multiple instruction (MI) with single data (SD) or multiple data (MD). SI versus MI captures the number of processors/instructions modifying the data at a given time. SD versus MD captures the number of data registers being modified at a given time, each of which can store different information. Our scheme falls under SIMD, since many registers, each with different data, are affected by the same instruction.
- 2.
In [24] an enumeration of all possible rules for elementary CA is given. Rule 110 refers to that enumeration.
- 3.
In a sense, we realize an extension of the sticker model envisioned by [4]: “Recent research suggests that DNA ‘strand invasion’ might provide a means for the specific removal of stickers from library strands. This could give rise to library strands that act as very powerful read-write memories. Further investigation of this possibility seems worthwhile.”.
- 4.
Given these properties, in practice one could choose the domain length to be from 5 to 7 nucleotides at room temperature.
- 5.
Although other more complicated strand displacement mechanisms (e.g. 4-way, remote toehold, associative toehold strand displacement) could provide extra power in this architecture, they usually sacrifice the speed and increase the design complexity, so we do not include them in this work.
- 6.
For example, Cas9 nickase or restriction enzyme PfAgo, uses an RNA or DNA strand as a guide and can nick at a desired location.
References
Adleman, L.M.: Molecular computation of solutions to combinatorial problems. Science 266(5187), 1021–1024 (1994)
Beaver, D.: A universal molecular computer. DNA Based Comput. 27, 29–36 (1995)
Boneh, D., Dunworth, C., Lipton, R.J., Sgall, J.: On the computational power of DNA. Discret. Appl. Math. 71(1–3), 79–94 (1996)
Braich, R.S., Chelyapov, N., Johnson, C., Rothemund, P.W.K., Adleman, L.: Solution of a 20-variable 3-SAT problem on a DNA computer. Science 296(5567), 499–502 (2002)
Church, G.M., Gao, Y., Kosuri, S.: Next-generation digital information storage in DNA. Science 337(6102), 1628 (2012)
Cook, M.: Universality in elementary cellular automata. Complex Syst. 15(1), 1–40 (2004)
Flynn, M.J.: Some computer organizations and their effectiveness. IEEE Trans. Comput. 21(9), 948–960 (1972)
Freund, R., Kari, L., Păun, G.: DNA computing based on splicing: the existence of universal computers. Theory of Comput. Syst. 32(1), 69–112 (1999)
Liu, K., et al.: Detecting topological variations of DNA at single-molecule level. Nat. Commun. 10(1), 3 (2019)
Neary, T., Woods, D.: P-completeness of cellular automaton rule 110. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006. LNCS, vol. 4051, pp. 132–143. Springer, Heidelberg (2006). https://doi.org/10.1007/11786986_13
Organick, L., et al.: Random access in large-scale DNA data storage. Nat. Biotechnol. 36(3), 242–248 (2018)
Qian, L., Soloveichik, D., Winfree, E.: Efficient turing-universal computation with DNA polymers. In: Sakakibara, Y., Mi, Y. (eds.) DNA 2010. LNCS, vol. 6518, pp. 123–140. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-18305-8_12
Qian, L., Winfree, E.: Scaling up digital circuit computation with DNA strand displacement cascades. Science 332(6034), 1196–1201 (2011)
Qian, L., Winfree, E.: Parallel and scalable computation and spatial dynamics with DNA-based chemical reaction networks on a surface. In: Murata, S., Kobayashi, S. (eds.) DNA 2014. LNCS, vol. 8727, pp. 114–131. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-11295-4_8
Rothemund, P.W.K.: A DNA and restriction enzyme implementation of turing machines. DNA Based Comput. 27, 75–119 (1995)
Roweis, S., et al.: A sticker-based model for DNA computation. J. Comput. Biol. 5(4), 615–629 (1998)
Scalise, D., Schulman, R.: Emulating cellular automata in chemical reaction-diffusion networks. Nat. Comput. 15(2), 197–214 (2016)
Seelig, G., Soloveichik, D., Zhang, Y., Winfree, E.: Enzyme-free nucleic acid logic circuits. Science 314(5805), 1585–1588 (2006)
Smith III, A.R.: Simple computation-universal cellular spaces. J. ACM 18(3), 339–353 (1971)
Tabatabaei, S.K., et al.: DNA punch cards: encoding data on native DNA sequences via topological modifications. bioRxiv, 10.1101/672394
Thachuk, C., Winfree, E., Soloveichik, D.: Leakless DNA strand displacement systems. In: Phillips, A., Yin, P. (eds.) DNA 2015. LNCS, vol. 9211, pp. 133–153. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-21999-8_9
Wang, B., Thachuk, C., Ellington, A.D., Soloveichik, D.: The design space of strand displacement cascades with toehold-size clamps. In: Brijder, R., Qian, L. (eds.) DNA 2017. LNCS, vol. 10467, pp. 64–81. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-66799-7_5
Wang, B., Thachuk, C., Ellington, A.D., Winfree, E., Soloveichik, D.: Effective design principles for leakless strand displacement systems. Proc. Nat. Acad. Sci. 115(52), E12182–E12191 (2018)
Wolfram, S.: Statistical mechanics of cellular automata. Rev. Mod. Phys. 55, 601–644 (1983)
Zhang, D.Y., Seelig, G.: Dynamic DNA nanotechnology using strand-displacement reactions. Nat. Chem. 3(2), 103 (2011)
Acknowledgements
The authors were supported by NSF grants CCF-1618895 and CCF-1652824, and DARPA grant W911NF-18-2-0032. We thank Marc Riedel for suggesting the analogy to Single Instruction, Multiple Data Computers. We thank Marc Riedel and Olgica Milenkovic for discussions.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Wang, B., Chalk, C., Soloveichik, D. (2019). SIMD||DNA: Single Instruction, Multiple Data Computation with DNA Strand Displacement Cascades. In: Thachuk, C., Liu, Y. (eds) DNA Computing and Molecular Programming. DNA 2019. Lecture Notes in Computer Science(), vol 11648. Springer, Cham. https://doi.org/10.1007/978-3-030-26807-7_12
Download citation
DOI: https://doi.org/10.1007/978-3-030-26807-7_12
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-26806-0
Online ISBN: 978-3-030-26807-7
eBook Packages: Computer ScienceComputer Science (R0)