Scaling Up Digital Circuit Computation with DNA Strand Displacement Cascades
Abstract
To construct sophisticated biochemical circuits from scratch, one needs to understand how simple the building blocks can be and how robustly such circuits can scale up. Using a simple DNA reaction mechanism based on a reversible strand displacement process, we experimentally demonstrated several digital logic circuits, culminating in a four-bit square-root circuit that comprises 130 DNA strands. These multilayer circuits include thresholding and catalysis within every logical operation to perform digital signal restoration, which enables fast and reliable function in large circuits with roughly constant switching time and linear signal propagation delays. The design naturally incorporates other crucial elements for large-scale circuitry, such as general debugging tools, parallel circuit preparation, and an abstraction hierarchy supported by an automated circuit compiler.
Get full access to this article
View all available purchase options and get full access to this article.
Already a Subscriber?Sign In
Supplementary Material
File (qian.som.pdf)
References and Notes
1
Adleman L. M., Molecular computation of solutions to combinatorial problems. Science 266, 1021 (1994).
2
Stojanovic M. N., Stefanovic D., A deoxyribozyme-based molecular automaton. Nat. Biotechnol. 21, 1069 (2003).
3
Elbaz J., et al., DNA computing circuits using libraries of DNAzyme subunits. Nat. Nanotechnol. 5, 417 (2010).
4
Benenson Y., Gil B., Ben-Dor U., Adar R., Shapiro E., An autonomous molecular computer for logical control of gene expression. Nature 429, 423 (2004).
5
Yurke B., Turberfield A. J., Mills A. P., Simmel F. C., Neumann J. L., A DNA-fuelled molecular machine made of DNA. Nature 406, 605 (2000).
6
Turberfield A. J., et al., DNA fuel for free-running nanomachines. Phys. Rev. Lett. 90, 118102 (2003).
7
Yurke B., Mills A. P., Using DNA to power nanostructures. Genet. Program. Evolvable Mach. 4, 111 (2003).
8
Zhang D. Y., Winfree E., Control of DNA strand displacement kinetics using toehold exchange. J. Am. Chem. Soc. 131, 17303 (2009).
9
Soloveichik D., Seelig G., Winfree E., DNA as a universal substrate for chemical kinetics. Proc. Natl. Acad. Sci. U.S.A. 107, 5393 (2010).
10
Phillips A., Cardelli L., A programming language for composable DNA circuits. J. R. Soc. Interface 6 (suppl. 4), S419 (2009).
11
Seelig G., Soloveichik D., Zhang D. Y., Winfree E., Enzyme-free nucleic acid logic circuits. Science 314, 1585 (2006).
12
Zhang D. Y., Turberfield A. J., Yurke B., Winfree E., Engineering entropy-driven reactions and networks catalyzed by DNA. Science 318, 1121 (2007).
13
Yin P., Choi H. M. T., Calvert C. R., Pierce N. A., Programming biomolecular self-assembly pathways. Nature 451, 318 (2008).
14
Venkataraman S., Dirks R. M., Ueda C. T., Pierce N. A., Selective cell death mediated by small conditional RNAs. Proc. Natl. Acad. Sci. U.S.A. 107, 16777 (2010).
15
Choi H. M. T., et al., Programmable in situ amplification for multiplexed imaging of mRNA expression. Nat. Biotechnol. 28, 1208 (2010).
16
Eckhoff G., Codrea V., Ellington A. D., Chen X., Beyond allostery: Catalytic regulation of a deoxyribozyme through an entropy-driven DNA amplifier. J. Systems Chem. 1, 13 (2010).
17
Qian L., Winfree E., A simple DNA gate motif for synthesizing large-scale circuits. J. R. Soc. Interface 10.1098/rsif.2010.0729 (2011).
18
D. E. Muller, in Symposium on the Application of Switching Theory to Space Technology (Stanford Univ. Press, Stanford, CA, 1963), pp. 289–297.
19
Tian J., Ma K., Saaem I., Advancing high-throughput gene synthesis technology. Mol. Biosyst. 5, 714 (2009).
20
J. S. Bois, thesis, California Institute of Technology (2007).
21
www.dna.caltech.edu/SeesawCompiler.
22
Hucka M., et al.SBML Forum, The systems biology markup language (SBML): A medium for representation and exchange of biochemical network models. Bioinformatics 19, 524 (2003).
23
Rothemund P. W. K., Folding DNA to create nanoscale shapes and patterns. Nature 440, 297 (2006).
24
Gu H., Chao J., Xiao S. J., Seeman N. C., A proximity-based programmable DNA nanoscale assembly line. Nature 465, 202 (2010).
25
Lund K., et al., Molecular robots guided by prescriptive landscapes. Nature 465, 206 (2010).
26
L. Qian, D. Soloveichik, E. Winfree, in DNA Computing and Molecular Programming, Lecture Notes in Computer Science, Vol. 6518, Y. Sakakibara, Y. Mi, Eds. (Springer, New York, 2011), pp. 123–140.
27
E. Chiniforooshan, D. Doty, L. Kari, S. Seki, in DNA Computing and Molecular Programming, Lecture Notes in Computer Science, Vol. 6518, Y. Sakakibara, Y. Mi, Eds. (Springer, New York, 2011), pp. 25–36.
28
A. Goel, M. Ibrahimi, in DNA Computing and Molecular Programming, Lecture Notes in Computer Science, Vol. 5877, R. Deaton, A. Suyama, Eds. (Springer, New York, 2009), pp. 67–77.
29
Baum E. B., Building an associative memory vastly larger than the brain. Science 268, 583 (1995).
30
Dirks R. M., Pierce N. A., Triggered amplification by hybridization chain reaction. Proc. Natl. Acad. Sci. U.S.A. 101, 15275 (2004).
31
Dittmer W. U., Reuter A., Simmel F. C., A DNA-based machine that can cyclically bind and release thrombin. Angew. Chem. Int. Ed. 43, 3550 (2004).
32
Kim V. N., MicroRNA biogenesis: Coordinated cropping and dicing. Nat. Rev. Mol. Cell Biol. 6, 376 (2005).
33
Carthew R. W., Sontheimer E. J., Origins and mechanisms of miRNAs and siRNAs. Cell 136, 642 (2009).
34
Sequences for all DNA molecules used in this work are provided in the supporting online material.
Information & Authors
Information
Published In
Science
Volume 332 | Issue 6034
3 June 2011
3 June 2011
Copyright
Copyright © 2011, American Association for the Advancement of Science.
Submission history
Received: 16 November 2010
Accepted: 15 April 2011
Published in print: 3 June 2011
Acknowledgments
Acknowledgments: We thank D. Y. Zhang for providing useful comments on the manuscript. Supported by NSF grants 0728703 and 0832824 (Molecular Programming Project) and Human Frontier Science Program award RGY0074/2006-C.
Authors
Metrics & Citations
Metrics
Article Usage
Altmetrics
Citations
Export citation
Select the format you want to export the citation of this publication.
Cited by
- Intracellular in situ assembly of palindromic DNA hydrogel for predicting malignant invasion and preventing tumorigenesis, Chemical Engineering Journal, 428, (131150), (2022).https://doi.org/10.1016/j.cej.2021.131150
- DNA Switching Circuits Based on Binary Tree, IEEE Access, 9, (94033-94039), (2021).https://doi.org/10.1109/ACCESS.2021.3091010
- Engineering DNA Switches for DNA Computing Applications , DNA‐ and RNA‐Based Computing Systems, (105-124), (2021).https://doi.org/10.1002/9783527825424
- DNA Walker-Programmed Nanoparticle Superlattice, Acta Chimica Sinica, 79, 2, (192), (2021).https://doi.org/10.6023/A20090426
- Nanopore Decoding for DNA Computing , DNA‐ and RNA‐Based Computing Systems, (327-343), (2021).https://doi.org/10.1002/9783527825424
- Kinetics of heterochiral strand displacement from PNA–DNA heteroduplexes, Nucleic Acids Research, 49, 11, (6114-6127), (2021).https://doi.org/10.1093/nar/gkab499
- Future DNA computing device and accompanied tool stack: Towards high-throughput computation, Future Generation Computer Systems, 117, (111-124), (2021).https://doi.org/10.1016/j.future.2020.10.038
- Diverse Applications of DNAzymes in Computing and Nanotechnology, Ribozymes, (633-660), (2021).https://doi.org/10.1002/9783527814527
- Dynamic Behavior Analysis of DNA Subtraction Gate with Stochastic Disturbance and Time Delay, Advances in Swarm Intelligence, (547-556), (2021).https://doi.org/10.1007/978-3-030-78743-1_49
- Encryption Algorithm Based on DNA Strand Displacement and DNA Sequence Operation, IEEE Transactions on NanoBioscience, 20, 2, (223-234), (2021).https://doi.org/10.1109/TNB.2021.3058399
- See more
Loading...
View Options
Get Access
Log in to view the full text
AAAS login provides access to Science for AAAS Members, and access to other journals in the Science family to users who have purchased individual subscriptions.
- Become a AAAS Member
- Activate your AAAS ID
- Purchase Access to Other Journals in the Science Family
- Account Help
Log in via OpenAthens.
Log in via Shibboleth.
More options
Register for free to read this article
As a service to the community, this article is available for free. Login or register for free to read this article.
Buy a single issue of Science for just $15 USD.
View options
PDF format
Download this article as a PDF file
Download PDF