Content deleted Content added
Fixed grammar Tags: Mobile edit Mobile app edit iOS app edit App section source |
m Open access bot: pmc updated in citation with #oabot. |
||
| (7 intermediate revisions by 6 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 9:
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 after almost a decade.
The field of DNA computing can be categorized as a sub-field of the broader [[DNA nanotechnology|DNA nanoscience]] field started by Ned Seeman about a decade before Len Adleman's demonstration.<ref>{{Cite journal|last=Seeman|first=Nadrian C.|date=1982-11-21|title=Nucleic acid junctions and lattices|journal=Journal of Theoretical Biology|language=en|volume=99|issue=2|pages=237–247|doi=10.1016/0022-5193(82)90002-9|pmid=6188926|bibcode=1982JThBi..99..237S|issn=0022-5193}}</ref> Ned's original idea in the 1980s was to build arbitrary structures using bottom-up DNA self-assembly for applications in crystallography. However, it morphed into the field of structural DNA self-assembly<ref>{{Cite journal|last1=Tikhomirov|first1=Grigory|last2=Petersen|first2=Philip|last3=Qian|first3=Lulu|date=December 2017|title=Fractal assembly of micrometre-scale DNA origami arrays with arbitrary patterns|url=https://www.nature.com/articles/nature24655|journal=Nature|language=en|volume=552|issue=7683|pages=67–71|doi=10.1038/nature24655|pmid=29219965|bibcode=2017Natur.552...67T|s2cid=4455780|issn=1476-4687|url-access=subscription}}</ref><ref>{{Cite journal|last1=Wagenbauer|first1=Klaus F.|last2=Sigl|first2=Christian|last3=Dietz|first3=Hendrik|date=December 2017|title=Gigadalton-scale shape-programmable DNA assemblies|url=https://www.nature.com/articles/nature24651|journal=Nature|language=en|volume=552|issue=7683|pages=78–83|doi=10.1038/nature24651|pmid=29219966|bibcode=2017Natur.552...78W|s2cid=205262182|issn=1476-4687|url-access=subscription}}</ref><ref>{{Cite journal|last1=Ong|first1=Luvena L.|last2=Hanikel|first2=Nikita|last3=Yaghi|first3=Omar K.|last4=Grun|first4=Casey|last5=Strauss|first5=Maximilian T.|last6=Bron|first6=Patrick|last7=Lai-Kee-Him|first7=Josephine|last8=Schueder|first8=Florian|last9=Wang|first9=Bei|last10=Wang|first10=Pengfei|last11=Kishi|first11=Jocelyn Y.|date=December 2017|title=Programmable self-assembly of three-dimensional nanostructures from 10,000 unique components|journal=Nature|language=en|volume=552|issue=7683|pages=72–77|doi=10.1038/nature24648|pmid=29219968|pmc=5786436|bibcode=2017Natur.552...72O|issn=1476-4687}}</ref> which as of 2020 is extremely sophisticated. Self-assembled structure from a few nanometers tall all the way up to several tens of micrometers in size have been demonstrated in 2018.
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>
Line 35:
=== Improved speed with Localized (cache-like) Computing ===
One of the challenges of DNA computing is its slow speed. While DNA is a biologically compatible substrate, i.e., it can be used at places where silicon technology cannot, its computational speed is still very slow. For example, the square-root circuit used as a benchmark in the field takes over 100 hours to complete.<ref name=":5">{{Cite journal|last1=Qian|first1=L.|last2=Winfree|first2=E.|s2cid=10053541|date=2011-06-02|title=Scaling Up Digital Circuit Computation with DNA Strand Displacement Cascades|journal=Science|volume=332|issue=6034|pages=1196–1201|doi=10.1126/science.1200520|pmid=21636773|issn=0036-8075|bibcode=2011Sci...332.1196Q}}</ref> While newer ways with external enzyme sources are reporting faster and more compact circuits,<ref name=":6">{{Cite journal|last1=Song|first1=Tianqi|last2=Eshra|first2=Abeer|last3=Shah|first3=Shalin|last4=Bui|first4=Hieu|last5=Fu|first5=Daniel|last6=Yang|first6=Ming|last7=Mokhtar|first7=Reem|last8=Reif|first8=John|date=2019-09-23|title=Fast and compact DNA logic circuits based on single-stranded gates using strand-displacing polymerase|journal=Nature Nanotechnology|volume=14|issue=11|pages=1075–1081|doi=10.1038/s41565-019-0544-5|pmid=31548688|issn=1748-3387|bibcode=2019NatNa..14.1075S|s2cid=202729100}}</ref> Chatterjee et al. demonstrated an interesting idea in the field to speed up computation through localized DNA circuits,<ref name="spacearch">{{Cite journal|last1=Chatterjee|first1=Gourab|last2=Dalchau|first2=Neil|last3=Muscat|first3=Richard A.|last4=Phillips|first4=Andrew|last5=Seelig|first5=Georg|date=2017-07-24|title=A spatially localized architecture for fast and modular DNA computing|journal=Nature Nanotechnology|volume=12|issue=9|pages=920–927|doi=10.1038/nnano.2017.127|pmid=28737747|issn=1748-3387|bibcode=2017NatNa..12..920C}}</ref> a concept being further explored by other groups.<ref name=":9">{{Cite journal|last1=Bui|first1=Hieu|last2=Shah|first2=Shalin|last3=Mokhtar|first3=Reem|last4=Song|first4=Tianqi|last5=Garg|first5=Sudhanshu|last6=Reif|first6=John|date=2018-01-25|title=Localized DNA Hybridization Chain Reactions on DNA Origami|journal=ACS Nano|volume=12|issue=2|pages=1146–1155|doi=10.1021/acsnano.7b06699|pmid=29357217|issn=1936-0851}}</ref> This idea, while originally proposed in the field of computer architecture, has been adopted in this field as well. In computer architecture, it is very well-known that if the instructions are executed in sequence, having them loaded in the cache will inevitably lead to fast performance, also called the principle of localization. This is because with instructions in fast cache memory, there is no need swap them in and out of main memory, which can be slow.<ref name="spacearch"/> Similarly, in localized DNA computing, the DNA strands responsible for computation are fixed on a breadboard-like substrate ensuring physical proximity of the computing gates. Such localized DNA computing techniques have been shown to potentially reduce the computation time by orders of magnitude.<ref name="spacearch"/>
=== Renewable (or reversible) DNA computing ===
Subsequent research on DNA computing has produced reversible DNA computing, bringing the technology one step closer to the silicon-based computing used in (for example) [[Personal computer|PC]]s. In particular, John Reif and his group at Duke University have proposed two different techniques to reuse the computing DNA complexes. The first design uses dsDNA gates,<ref>{{Cite journal|last1= Garg|first1= Sudhanshu|last2= Shah|first2= Shalin|last3= Bui|first3= Hieu|last4= Song|first4= Tianqi|last5= Mokhtar|first5= Reem|last6= Reif|first6= John|date= 2018|title= Renewable Time-Responsive DNA Circuits|journal= Small|language= en|volume= 14|issue= 33|pages= 1801470|doi= 10.1002/smll.201801470|pmid= 30022600|bibcode= 2018Small..1401470G|issn= 1613-6829|doi-access= free}}</ref> while the second design uses DNA hairpin complexes.<ref>
{{Cite journal
|last1= Eshra|first1= A.|last2= Shah|first2= S.
Line 50:
|bibcode= 2019ITNan..18..252E|s2cid= 5616325}}
</ref>
While both
Using strand displacement reactions (SRDs), reversible proposals are presented in the "Synthesis Strategy of Reversible Circuits on DNA Computers" paper for implementing reversible gates and circuits on DNA computers by combining DNA computing and reversible computing techniques. This paper also proposes a universal reversible gate library (URGL) for synthesizing n-bit reversible circuits on DNA computers with an average length and cost of the constructed circuits better than the previous methods.<ref>{{Cite journal|last1=Rofail|first1=Mirna|last2=Younes|first2=Ahmed|date=July 2021|title=Synthesis Strategy of Reversible Circuits on DNA Computers|journal=Symmetry|language=en|volume=13|issue=7|pages=1242|doi=10.3390/sym13071242|bibcode=2021Symm...13.1242R|doi-access=free}}</ref>
Line 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
* Polymerase-based strand displacement (PSD)<ref name=":0" />
Line 84:
</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>
| |||