Molecular Computation of Solutions to Combinatorial Problems
Abstract
The tools of molecular biology were used to solve an instance of the directed Hamiltonian path problem. A small graph was encoded in molecules of DNA, and the "operations" of the computation were performed with standard protocols and enzymes. This experiment demonstrates the feasibility of carrying out computations at the molecular level.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
The Adleman experiment acted as a proof of concept, but in practice the process was more time- and labor-intensive than a conventional digital approach.
“The Adleman experiment acted as a proof of concept: in practice, the process was more time- and labor-intensive than a conventional digital approach.”
From Emerging Approaches to DNA Data Storage: Challenges and Prospects (2022) · cites this paper as [136]
Adleman developed a working prototype for a DNA computer in 1994, using a separation-based approach to calculate a Hamiltonian path in a graph with seven summits.
“A working prototype for a DNA computer was developed by Adleman in 1994,136 wherein he used a separation-based approach to calculate a Hamiltonian path in a graph with seven summits.”
From Emerging Approaches to DNA Data Storage: Challenges and Prospects (2022) · cites this paper as [136]
More advanced applications, such as random number generation or arithmetic operations, prove the versatility of DNA as an information medium.
“More advanced applications, for example, random number generation or the possibility to perform arithmetic operations, prove the versatility of DNA as an information medium.[11,12]”
From Integrating DNA Encapsulates and Digital Microfluidics for Automated Data Storage in DNA (2022) · cites this paper as [12]
Cites
Theory of Recursive Functions and Effective Computability.
Feferman, S., & Rogers, H. (1969) · American Mathematical Monthly · doi:10.2307/2316720 · Cited by 2,817 · see citing works
Complexity of Computer Computations
Miller, R. E., Thatcher, J. W., & Bohlinger, J. D. (1972) · Springer eBooks · doi:10.1007/978-1-4684-2001-2 · Cited by 2,789 · see citing works
Watson, J. D. (1970) · Cold Spring Harbor Laboratory Institutional Repository (Cold Spring Harbor Laboratory) · Cited by 2,062 · see citing works
Reversible electronic logic using switches
Merkle, R. C. (1993) · Nanotechnology · doi:10.1088/0957-4484/4/1/002 · Cited by 178 · see citing works
Theory of molecular machines. II. Energy dissipation from molecular machines
Schneider, T. D. (1991) · Journal of Theoretical Biology · doi:10.1016/s0022-5193(05)80467-9 · Cited by 108 · see citing works
Engler, M., & Richardson, C. C. (1982) · The Enzymes · doi:10.1016/s1874-6047(08)60273-5 · Cited by 52 · see citing works
(1992) · The MIT Press eBooks · doi:10.7551/mitpress/4838.001.0001 · Cited by 37 · see citing works
Will Future Computers Be All Wet?
Bradley, D. (1993) · Science · doi:10.1126/science.259.5097.890 · Cited by 31 · see citing works
Flagged first, then by citations
Cited by
Sorted by citations
Design and self-assembly of two-dimensional DNA crystals
Winfree, E., Liu, F., Wenzler, L. A., & Seeman, N. C. (1998) · Nature · doi:10.1038/28998 · Cited by 2,857 · see citing works
Seeman, N. C., & Sleiman, H. F. (2017) · Nature Reviews Materials · doi:10.1038/natrevmats.2017.68 · Cited by 1,875 · see citing works
Dynamic DNA nanotechnology using strand-displacement reactions
Zhang, D. Y., & Seelig, G. (2011) · Nature Chemistry · doi:10.1038/nchem.957 · Cited by 1,785 · see citing works
Next-Generation Digital Information Storage in DNA
Church, G. M., Gao, Y., & Kosuri, S. (2012) · Science · doi:10.1126/science.1226355 · Cited by 1,441 · see citing works
Logical computation using algorithmic self-assembly of DNA triple-crossover molecules
Mao, C., LaBean, T. H., Reif, J. H., & Seeman, N. C. (2000) · Nature · doi:10.1038/35035038 · Cited by 779 · see citing works
DNA nanotechnology from the test tube to the cell
Chen, Y.-J., Groves, B., Muscat, R. A., & Seelig, G. (2015) · Nature Nanotechnology · doi:10.1038/nnano.2015.195 · Cited by 594 · see citing works
CRISPR-Cas Encoding of a Digital Movie into the Genomes of a Population of Living Bacteria
Shipman, S. L., Nivala, J., Macklis, J. D., & Church, G. M. (2017) · Nature · doi:10.1038/nature23017 · Cited by 361 · see citing works
Advancement of the emerging field of RNA nanotechnology
Jasinski, D., Haque, F., Binzel, D. W., & Guo, P. (2017) · ACS Nano · doi:10.1021/acsnano.6b05737 · Cited by 352 · see citing works
Chen, J., Zhu, Z.-L., Zhang, L.-B., Zhang, Y., & Yang, B.-Q. (2018) · Signal Processing · doi:10.1016/j.sigpro.2017.07.034 · Cited by 320 · see citing works
Emerging Approaches to DNA Data Storage: Challenges and Prospects
Doricchi, A., Platnich, C. M., Gimpel, A., Horn, F., Earle, M., Lanzavecchia, G., Cortajarena, A. L., Liz-Marzán, L. M., Liu, N., Heckel, R., et al. (2022) · ACS Nano · doi:10.1021/acsnano.2c06748 · Cited by 235 · see citing works
Encoding information into polymers
Rutten, M. G. T. A., Vaandrager, F. W., Elemans, J. A. A. W., & Nolte, R. J. M. (2018) · Nature Reviews Chemistry · doi:10.1038/s41570-018-0051-5 · Cited by 216 · see citing works
Jones, J. A. (2001) · Progress in Nuclear Magnetic Resonance Spectroscopy · doi:10.1016/s0079-6565(00)00033-9 · Cited by 177 · see citing works
DNA Computation: A Photochemically Controlled AND Gate
Prokup, A., Hemphill, J., & Deiters, A. (2012) · Journal of the American Chemical Society · doi:10.1021/ja210050s · Cited by 116 · see citing works
Efficiency of DNA replication in the polymerase chain reaction
Stolovitzky, G., & Cecchi, G. (1996) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.93.23.12947 · Cited by 112 · see citing works
Driving the Scalability of DNA-Based Information Storage Systems
Tomek, K. J., Volkel, K., Simpson, A., Hass, A. G., Indermaur, E. W., Tuck, J. M., & Keung, A. J. (2019) · ACS Synthetic Biology · doi:10.1021/acssynbio.9b00100 · Cited by 100 · see citing works
Su, H., Xu, J., Wang, Q., Wang, F., & Zhou, X. (2019) · Nature Communications · doi:10.1038/s41467-019-13310-2 · Cited by 94 · see citing works
A DNA-Based Archival Storage System
Bornholt, J., Lopez, R., Carmean, D. M., Ceze, L., Seelig, G., & Strauss, K. (2016) · ACM SIGOPS Operating Systems Review · doi:10.1145/2954680.2872397 · Cited by 77 · see citing works
Nucleic Acid Databases and Molecular-Scale Computing
Song, X., & Reif, J. (2019) · ACS Nano · doi:10.1021/acsnano.9b02562 · Cited by 73 · see citing works
DNA Data Storage and Hybrid Molecular–Electronic Computing
Carmean, D., Ceze, L., Seelig, G., Stewart, K., Strauss, K., & Willsey, M. (2019) · Proceedings of the IEEE · doi:10.1109/jproc.2018.2875386 · Cited by 69 · see citing works
Applications and Challenges of Artificial Intelligence in Space Missions
Oche, P. A., Ewa, G. A., & Ibekwe, N. (2024) · IEEE Access · doi:10.1109/access.2021.3132500 · Cited by 68 · see citing works
“DNA Computing Robotic control; Information security; task assignment problem; clustering problem Robotic and Autonomous System (RAS) [102],[103-106],[93]”
BackgroundIntegrating DNA Encapsulates and Digital Microfluidics for Automated Data Storage in DNA
Antkowiak, P. L., Koch, J., Nguyen, B. H., Stark, W. J., Strauss, K., Ceze, L., & Grass, R. N. (2022) · Small · doi:10.1002/smll.202107381 · Cited by 65 · see citing works
A Bijective Image Encryption System Based on Hybrid Chaotic Map Diffusion and DNA Confusion
ElKamchouchi, D. H., Mohamed, H. G., & Moussa, K. H. (2020) · Entropy · doi:10.3390/e22020180 · Cited by 63 · see citing works
Segmenting images with gradient-based edge detection using Membrane Computing
Díaz-Pernil, D., Berciano, A., Peña-Cantillana, F., & Gutiérrez-Naranjo, M. A. (2013) · Pattern Recognition Letters · doi:10.1016/j.patrec.2012.10.014 · Cited by 60 · see citing works
A DNA-based system for selecting and displaying the combined result of two input variables
Liu, H., Wang, J., Song, S., Fan, C., & Gothelf, K. V. (2015) · Nature Communications · doi:10.1038/ncomms10089 · Cited by 57 · see citing works
“T he power of DNA computing derives from its digital programmability and the parallel nature of the process by which vast numbers of interactions between populations of DNA molecules in solution occur in a short time frame 1–3 .”
BackgroundSauri, V., Gobbo, J. P., Serrano-Pérez, J. J., Lundberg, M., Coto, P. B., Serrano-Andrés, L., Borin, A. C., Lindh, R., Merchán, M., & Roca-Sanjuán, D. (2013) · Journal of Chemical Theory and Computation · doi:10.1021/ct3006166 · Cited by 56 · see citing works
A Novel Image Encryption Algorithm Based on a Fractional-Order Hyperchaotic System and DNA Computing
Li, T., Yang, M., Wu, J., & Jing, X. (2017) · Complexity · doi:10.1155/2017/9010251 · Cited by 55 · see citing works
A DNA-Based Archival Storage System
Bornholt, J., Lopez, R., Carmean, D. M., Ceze, L., Seelig, G., & Strauss, K. (2016) · ACM SIGPLAN Notices · doi:10.1145/2954679.2872397 · Cited by 54 · see citing works
Surprising fidelity of template-directed chemical ligation of oligonucleotides
James, K. D., & Ellington, A. D. (1997) · Chemistry & Biology · doi:10.1016/s1074-5521(97)90245-3 · Cited by 50 · see citing works
Binary DNA Nanostructures for Data Encryption
Halvorsen, K., & Wong, W. P. (2012) · PLoS ONE · doi:10.1371/journal.pone.0044212 · Cited by 45 · see citing works
Large-scale DNA memory based on the nested PCR
Yamamoto, M., Kashiwamura, S., Ohuchi, A., & Furukawa, M. (2008) · Natural Computing · doi:10.1007/s11047-008-9076-x · Cited by 33 · see citing works
A DNA Computation-Based Image Encryption Scheme for Cloud CCTV Systems
Wu, T.-Y., Fan, X., Wang, K.-H., Lai, C.-F., Xiong, N., & Wu, J. M.-T. (2019) · IEEE Access · doi:10.1109/access.2019.2946890 · Cited by 23 · see citing works
DNA Memory with 16.8M Addresses
Yamamoto, M., Kashiwamura, S., & Ohuchi, A. (2008) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-77962-9_10 · Cited by 4 · see citing works
Rebimbas, R., Glória, I., Chegão, J., Al-Rawi, M., Mousakhani Ganjeh, A., & Saraiva, J. A. (2026) · Journal of Biotechnology · doi:10.1016/j.jbiotec.2026.03.003
- Authors
- Adleman, L. M.
- Affiliations
- University of Southern California (US)
- Corresponding author
- Adleman, Leonard M.
- Venue
- Science
- Published
- 1994-11-11
- Volume
- 266
- Issue
- 5187
- Pages
- 1021-1024
- ISSN
- 0036-8075 (ISSN-L)
- 1095-9203
- OpenAlex
- W1977312644
- Cited by
- 4,474
- References
- 8
- Citations by year
- 2026: 68 · 2025: 123 · 2024: 124 · 2023: 165 · 2022: 163 · 2021: 194 · 2020: 135 · 2019: 160 · 2018: 164 · 2017: 157 · 2016: 154 · 2015: 174 · 2014: 165 · 2013: 205 · 2012: 194
- FWCI
- 13.12
- Type
- journal article
- Language
- en
- Open access
- closed
- Locations
- Science (publishedVersion)
- PubMed (publishedVersion)
- Topics
- Life Sciences › Biochemistry, Genetics and Molecular Biology › Molecular Biology › DNA and Biological Computing
- Life Sciences › Biochemistry, Genetics and Molecular Biology › Molecular Biology › Advanced biosensing and bioanalysis techniques
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Complexity and Algorithms in Graphs
- Keywords
- DNA computing, molecular computing, combinatorial optimization, molecular tools
- MeSH terms
- Algorithms, Base Sequence, DNA, Mathematical Computing, Molecular Sequence Data, Oligodeoxyribonucleotides, Polymerase Chain Reaction
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
