Content deleted Content added
Tags: Reverted references removed Visual edit |
m Open access bot: pmc updated in citation with #oabot. |
||
| (14 intermediate revisions by 8 users not shown) | |||
Line 1:
{{Short description|Computing using molecular biology hardware}}
[[File:DNA orbit animated.gif|thumb|The biocompatible computing device: Deoxyribonucleic acid (DNA)]]
'''DNA computing''' is an emerging branch of [[unconventional computing]] which uses [[DNA]], [[biochemistry]], and [[molecular biology]] hardware, instead of the traditional [[electronic computing]]. Research and development in this area concerns theory, experiments, and applications of DNA computing. Although the field originally started with the demonstration of a computing application by [[Leonard Adleman|Len Adleman]] in 1994, it has now been expanded to several other avenues such as the development of storage technologies,<ref name=":7">{{Cite journal|last1=Church|first1=G. M.|last2=Gao|first2=Y.|last3=Kosuri|first3=S.|date=2012-08-16|title=Next-Generation Digital Information Storage in DNA|journal=Science|volume=337|issue=6102|pages=1628|doi=10.1126/science.1226355|pmid=22903519|bibcode=2012Sci...337.1628C|s2cid=934617|issn=0036-8075|doi-access=free|pmc=3581509}}</ref><ref>{{Cite journal|last1=Erlich|first1=Yaniv|last2=Zielinski|first2=Dina|date=2017-03-02|title=DNA Fountain enables a robust and efficient storage architecture|journal=Science|volume=355|issue=6328|pages=950–954|doi=10.1126/science.aaj2038|pmid=28254941|bibcode=2017Sci...355..950E|s2cid=13470340|issn=0036-8075|url=https://zenodo.org/record/889697}}</ref><ref>{{Cite journal|last1=Organick|first1=Lee|last2=Ang|first2=Siena Dumas|last3=Chen|first3=Yuan-Jyue|last4=Lopez|first4=Randolph|last5=Yekhanin|first5=Sergey|last6=Makarychev|first6=Konstantin|last7=Racz|first7=Miklos Z.|last8=Kamath|first8=Govinda|last9=Gopalan|first9=Parikshit|last10=Nguyen|first10=Bichlien|last11=Takahashi|first11=Christopher N.|date=March 2018|title=Random access in large-scale DNA data storage|url=https://www.nature.com/articles/nbt.4079|journal=Nature Biotechnology|language=en|volume=36|issue=3|pages=242–248|doi=10.1038/nbt.4079|pmid=29457795|s2cid=205285821|issn=1546-1696|url-access=subscription}}</ref> nanoscale imaging modalities,<ref>{{Cite journal|last1=Shah|first1=Shalin|last2=Dubey|first2=Abhishek K.|last3=Reif|first3=John|date=2019-04-10|title=Programming Temporal DNA Barcodes for Single-Molecule Fingerprinting|journal=Nano Letters|volume=19|issue=4|pages=2668–2673|doi=10.1021/acs.nanolett.9b00590|pmid=30896178|bibcode=2019NanoL..19.2668S|s2cid=84841635|issn=1530-6984}}</ref><ref>{{Cite journal|last1=Sharonov|first1=Alexey|last2=Hochstrasser|first2=Robin M.|date=2006-12-12|title=Wide-field subdiffraction imaging by accumulated binding of diffusing probes|journal=Proceedings of the National Academy of Sciences|language=en|volume=103|issue=50|pages=18911–18916|doi=10.1073/pnas.0609643104|issn=0027-8424|pmid=17142314|pmc=1748151|bibcode=2006PNAS..10318911S|doi-access=free}}</ref><ref name=":8">{{Cite journal|last1=Jungmann|first1=Ralf|last2=Avendaño|first2=Maier S.|last3=Dai|first3=Mingjie|last4=Woehrstein|first4=Johannes B.|last5=Agasti|first5=Sarit S.|last6=Feiger|first6=Zachary|last7=Rodal|first7=Avital|last8=Yin|first8=Peng|date=May 2016|title=Quantitative super-resolution imaging with qPAINT|journal=Nature Methods|language=en|volume=13|issue=5|pages=439–442|doi=10.1038/nmeth.3804|pmid=27018580|pmc=4941813|issn=1548-7105}}</ref> synthetic controllers and reaction networks,<ref name=":0">{{Cite journal|last1=Shah|first1=Shalin|last2=Wee|first2=Jasmine|last3=Song|first3=Tianqi|last4=Ceze|first4=Luis|last5=Strauss|first5=Karin|author5-link=Karin Strauss|last6=Chen|first6=Yuan-Jyue|last7=Reif|first7=John|date=2020-05-04|title=Using Strand Displacing Polymerase To Program Chemical Reaction Networks|journal=Journal of the American Chemical Society|volume=142|issue=21|pages=9587–9593|doi=10.1021/jacs.0c02240|pmid=32364723|s2cid=218504535|issn=0002-7863}}</ref><ref name=":1">{{Cite journal|last1=Chen|first1=Yuan-Jyue|last2=Dalchau|first2=Neil|last3=Srinivas|first3=Niranjan|last4=Phillips|first4=Andrew|last5=Cardelli|first5=Luca|last6=Soloveichik|first6=David|last7=Seelig|first7=Georg|date=October 2013|title=Programmable chemical controllers made from DNA|journal=Nature Nanotechnology|language=en|volume=8|issue=10|pages=755–762|doi=10.1038/nnano.2013.189|pmid=24077029|pmc=4150546|bibcode=2013NatNa...8..755C|issn=1748-3395}}</ref><ref name=":2">{{Cite journal|last1=Srinivas|first1=Niranjan|last2=Parkin|first2=James|last3=Seelig|first3=Georg|last4=Winfree|first4=Erik|last5=Soloveichik|first5=David|date=2017-12-15|title=Enzyme-free nucleic acid dynamical systems|journal=Science|language=en|volume=358|issue=6369|pages=eaal2052|doi=10.1126/science.aal2052|issn=0036-8075|pmid=29242317|doi-access=free}}</ref><ref name=":3">{{Cite journal|last1=Soloveichik|first1=David|last2=Seelig|first2=Georg|last3=Winfree|first3=Erik|date=2010-03-23|title=DNA as a universal substrate for chemical kinetics|journal=Proceedings of the National Academy of Sciences|language=en|volume=107|issue=12|pages=5393–5398|doi=10.1073/pnas.0909380107|issn=0027-8424|pmid=20203007|pmc=2851759|bibcode=2010PNAS..107.5393S|doi-access=free}}</ref> etc.
== History ==
Line 7:
</ref><ref>{{cite journal |author1=Lila Kari |author2=Greg Gloor |author3=Sheng Yu |date=January 2000 |title=Using DNA to solve the Bounded Post Correspondence Problem |url=http://citeseer.ist.psu.edu/kari00using.html |journal=Theoretical Computer Science |volume=231 |issue=2 |pages=192–203 |doi=10.1016/s0304-3975(99)00100-0 |doi-access=free}} — Describes a solution for the bounded [[Post correspondence problem]], a hard-on-average NP-complete problem. Also available here: [http://www.csd.uwo.ca/~lila/pdfs/Using%20DNA%20to%20solve%20the%20Bounded%20Post%20Correspondence%20Problem.pdf]</ref>
Since then the field has expanded into several avenues. In 1995, the idea for DNA-based memory was proposed by Eric Baum<ref>{{Cite journal|last=Baum|first=E. B.|date=1995-04-28|title=Building an associative memory vastly larger than the brain|journal=Science|language=en|volume=268|issue=5210|pages=583–585|doi=10.1126/science.7725109|issn=0036-8075|pmid=7725109|bibcode=1995Sci...268..583B|doi-access=free}}</ref> who conjectured that a vast amount of data can be stored in a tiny amount of DNA due to its ultra-high density. This expanded the horizon of DNA computing into the realm of memory technology although the ''in vitro'' demonstrations were made
The field of DNA computing can be categorized as a sub-field of the broader [[DNA nanotechnology|DNA nanoscience]] field started by
In 1994, Prof. Seeman's group demonstrated early DNA lattice structures using a small set of DNA components. While the demonstration by Adleman showed the possibility of DNA-based computers, the DNA design was trivial because as the number of nodes in a graph grows, the number of DNA components required in Adleman's implementation would grow exponentially. Therefore, computer scientists and biochemists started exploring tile-assembly where the goal was to use a small set of DNA strands as tiles to perform arbitrary computations upon growth. Other avenues that were theoretically explored in the late 90's include DNA-based security and cryptography,<ref>{{Cite journal|last1=Leier|first1=André|last2=Richter|first2=Christoph|last3=Banzhaf|first3=Wolfgang|last4=Rauhe|first4=Hilmar|date=2000-06-01|title=Cryptography with DNA binary strands|url=http://www.sciencedirect.com/science/article/pii/S0303264700000836|journal=Biosystems|language=en|volume=57|issue=1|pages=13–22|doi=10.1016/S0303-2647(00)00083-6|pmid=10963862|bibcode=2000BiSys..57...13L |issn=0303-2647|url-access=subscription}}</ref> computational capacity of DNA systems,<ref>{{Cite journal|last1=Guarnieri|first1=Frank|last2=Fliss|first2=Makiko|last3=Bancroft|first3=Carter|date=1996-07-12|title=Making DNA Add|url=https://www.science.org/doi/10.1126/science.273.5272.220|journal=Science|language=en|volume=273|issue=5272|pages=220–223|doi=10.1126/science.273.5272.220|issn=0036-8075|pmid=8662501|bibcode=1996Sci...273..220G|s2cid=6051207|url-access=subscription}}</ref> DNA memories and disks,<ref>{{Cite journal|last1=Bancroft|first1=Carter|last2=Bowler|first2=Timothy|last3=Bloom|first3=Brian|last4=Clelland|first4=Catherine Taylor|date=2001-09-07|title=Long-Term Storage of Information in DNA|url=https://www.science.org/doi/10.1126/science.293.5536.1763c|journal=Science|language=en|volume=293|issue=5536|pages=1763–1765|doi=10.1126/science.293.5536.1763c|pmid=11556362|s2cid=34699434|issn=0036-8075|url-access=subscription}}</ref> and DNA-based robotics.<ref name=":10">{{Cite journal|last1=Yin|first1=Peng|last2=Yan|first2=Hao|last3=Daniell|first3=Xiaoju G.|last4=Turberfield|first4=Andrew J.|last5=Reif|first5=John H.|date=2004|title=A Unidirectional DNA Walker That Moves Autonomously along a Track|journal=Angewandte Chemie International Edition|volume=43|issue=37|pages=4906–4911|doi=10.1002/anie.200460522|pmid=15372637|bibcode=2004ACIE...43.4906Y |issn=1521-3773}}</ref>
Before 2002, [[Lila Kari]] showed that the DNA operations performed by genetic recombination in some organisms are Turing complete.<ref name=bucke>{{citation|url=http://communications.uwo.ca/com/western_news/profiles/biocomputing_researcher_awarded_the_bucke_prize_20020321435998/ |title=Biocomputing researcher awarded the Bucke Prize |journal=Western News |publisher=[[University of Western Ontario]] |date=March 21, 2002}}</ref>
In 2003,
== Applications, examples, and recent developments ==
Line 23:
First results to these problems were obtained by [[Leonard Adleman]].
* In 1994: Solving a [[Hamiltonian path problem|Hamiltonian path]] in a graph with
* In 2002: Solving a [[NP-complete]] problem as well as a [[3-satisfiability|3-SAT]] problem with 20 variables.
Line 30:
By default, the computer is considered to have played first in the central square. The human player starts with eight different types of DNA strands corresponding to the eight remaining boxes that may be played. To play box number i, the human player pours into all bins the strands corresponding to input #i. These strands bind to certain DNA enzymes present in the bins, resulting, in one of these bins, in the deformation of the DNA enzymes which binds to the substrate and cuts it. The corresponding bin becomes fluorescent, indicating which box is being played by the DNA computer. The DNA enzymes are divided among the bins in such a way as to ensure that the best the human player can achieve is a draw, as in real tic-tac-toe.
=== Neural network based computing ===
Kevin Cherry and [[Lulu Qian]] at Caltech developed a DNA-based artificial neural network that can recognize 100-bit hand-written digits. They achieved this by programming on a computer in advance with the appropriate set of weights represented by varying concentrations weight molecules which are later added to the test tube that holds the input DNA strands.<ref>{{Cite journal|last1=Qian|first1=Lulu|last2=Winfree|first2=Erik|last3=Bruck|first3=Jehoshua|date=July 2011|title=Neural network computation with DNA strand displacement cascades|journal=Nature|language=En|volume=475|issue=7356|pages=368–372|doi=10.1038/nature10262|pmid=21776082|s2cid=1735584|issn=0028-0836}}</ref><ref name=":4">{{Cite journal|last1=Cherry|first1=Kevin M.|last2=Qian|first2=Lulu|date=2018-07-04|title=Scaling up molecular pattern recognition with DNA-based winner-take-all neural networks|journal=Nature|language=En|volume=559|issue=7714|pages=370–376|doi=10.1038/s41586-018-0289-6|pmid=29973727|issn=0028-0836|bibcode=2018Natur.559..370C|s2cid=49566504|url=https://authors.library.caltech.edu/84840/}}</ref>
=== Improved speed with Localized (cache-like) Computing ===
One of the challenges of DNA computing is its slow speed. While DNA
=== Renewable (or reversible) DNA computing ===
Subsequent research on DNA computing has produced
{{Cite journal
|last1= Eshra|first1= A.|last2= Shah|first2= S.
Line 47 ⟶ 50:
|bibcode= 2019ITNan..18..252E|s2cid= 5616325}}
</ref>
While both
Using strand displacement reactions (SRDs), reversible proposals are presented in the
==Methods==
Line 57 ⟶ 60:
The most fundamental operation in DNA computing and molecular programming is the strand displacement mechanism. Currently, there are two ways to perform strand displacement:
* [[Toehold mediated strand displacement]] (TMSD)<ref name=":5" />
* Polymerase-based strand displacement (PSD)<ref name=":0" />
=== Toehold exchange ===
Besides simple strand displacement schemes, DNA computers have also been constructed using the concept of toehold exchange.<ref name=":4"
=== Chemical reaction networks (CRNs) ===
The full stack for DNA computing looks very similar to a traditional computer architecture. At the highest level, a C-like general purpose programming language is expressed using a set of [[Chemical reaction networks|chemical reaction networks (CRNs)]]. This intermediate representation gets translated to ___domain-level DNA design and then implemented using a set of DNA strands. In 2010,
===DNAzymes===
Catalytic DNA ([[deoxyribozyme]] or DNAzyme) catalyze a reaction when interacting with the appropriate input, such as a matching [[oligonucleotide]]. These DNAzymes are used to build logic gates analogous to digital logic in silicon; however, DNAzymes are limited to
The DNAzyme logic gate changes its structure when it binds to a matching oligonucleotide and the fluorogenic substrate it is bonded to is cleaved free. While other materials can be used, most models use a fluorescence-based substrate because it is very easy to detect, even at the single molecule limit.<ref name="weiss">
Line 80 ⟶ 83:
{{Cite journal |last1=MacDonald |first1=J. |last2=Li |first2=Y. |last3=Sutovic |first3=M. |last4=Lederman |first4=H. |last5=Pendri |first5=K. |last6=Lu |first6=W. |last7=Andrews |first7=B. L. |last8=Stefanovic |first8=D. |last9=Stojanovic |first9=M. N. |year=2006 |title=Medium Scale Integration of Molecular Logic Gates in an Automaton |journal=Nano Letters |volume=6 |issue=11 |pages=2598–2603 |bibcode=2006NanoL...6.2598M |doi=10.1021/nl0620684 |pmid=17090098}}. Also available here: [http://www.ece.gatech.edu/research/labs/bwn/nanos/papers/Medium_Scale_Integration_of_Molecular.pdf]
</ref> machines, respectively; Stojanovic has also demonstrated logic gates using the 8-17 DNAzyme.<ref>
{{Cite journal |last1=Stojanovic |first1=M. N. |last2=Mitchell |first2=T. E. |last3=Stefanovic |first3=D. |year=2002 |title=Deoxyribozyme-Based Logic Gates |url=https://figshare.com/articles/Deoxyribozyme-Based_Logic_Gates/3638808 |journal=Journal of the American Chemical Society |volume=124 |issue=14 |pages=3555–3561 |doi=10.1021/ja016756v |pmid=11929243|bibcode=2002JAChS.124.3555S }}. Also available at [http://www.dna.caltech.edu/courses/cs191/paperscs191/stojanovic_mitchell_stefanovic2002.pdf]
</ref> While these DNAzymes have been demonstrated to be useful for constructing logic gates, they are limited by the need
{{Cite journal | last1 = Cruz | first1 = R. P. G. | last2 = Withers | first2 = J. B. | last3 = Li | first3 = Y. | title = Dinucleotide Junction Cleavage Versatility of 8-17 Deoxyribozyme | doi = 10.1016/j.chembiol.2003.12.012 | journal = Chemistry & Biology | volume = 11 | issue = 1 | pages = 57–67 | year = 2004 | pmid = 15112995| doi-access = free | hdl = 11375/23673 | hdl-access = free }}
</ref>
Line 100 ⟶ 103:
=== Algorithmic self-assembly ===
[[Image:Rothemund-DNA-SierpinskiGasket.jpg|thumb
{{Main|DNA nanotechnology#Algorithmic self-assembly|l1 = DNA nanotechnology: Algorithmic self-assembly}}
Line 118 ⟶ 121:
== Alternative technologies ==
A partnership between [[IBM]] and [[Caltech]] was established in 2009 aiming at "[[DNA chip]]s" production.<ref>[http://media.caltech.edu/press_releases/13284](Caltech's own article) {{webarchive|url=https://web.archive.org/web/20111014075545/http://media.caltech.edu/press_releases/13284|date=October 14, 2011}}</ref> A Caltech group is working on the manufacturing of these nucleic-acid-based integrated circuits. One of these chips can compute whole square roots.<ref>[https://www.science.org/doi/full/10.1126/science.1200520 Scaling Up Digital Circuit Computation with DNA Strand Displacement Cascades]</ref> A compiler has been written in [[Perl]].<ref>[https://www.science.org/doi/abs/10.1126/science.1200520] Online</ref>
== Pros and cons ==
| |||