Solution of a 20-Variable 3-SAT Problem on a DNA Computer

No abstract is available for this paper.

• Publication year

  2002

• Venue

  Science

• Publication date

  2002-03-14

• Fields of study

  Biology, Medicine, Chemistry, Computer Science

• Identifiers
  DOI 10.1126/SCIENCE.1069528PMID 11896237
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar, PubMed

• No claims are published for this paper.

• No concepts are published for this paper.

• Programmable and autonomous computing machine made of biomolecules

  2001cited by this paper
• DNA Based Computers V

  2000cited by this paper
• Logical computation using algorithmic self-assembly of DNA triple-crossover molecules

  2000cited by this paper
• DNA computing on surfaces

  2000cited by this paper
• Molecular computation: RNA solutions to chess problems

  2000cited by this paper
• Molecular computation by DNA hairpin formation.

  2000cited by this paper
• A DNA-fuelled molecular machine made of DNA

  2000cited by this paper
• The evolution of cellular computing: nature's solution to a computational problem.

  1999cited by this paper
• Mutation typing using electrophoresis and gel-immobilized Acrydite probes.

  1998cited by this paper
• A Sticker-Based Model for DNA Computation

  1998cited by this paper
• Design and self-assembly of two-dimensional DNA crystals

  1998cited by this paper
• DNA solution of the maximal clique problem.

  1997cited by this paper
• Introduction to algorithms

  1996cited by this paper
• Maya Blue Paint: An Ancient Nanostructured Material

  1996cited by this paper
• Dimacs series in discrete mathematics and theoretical computer science

  1996cited by this paper
• Building an associative memory vastly larger than the brain.

  1995cited by this paper
• DNA solution of hard computational problems.

  1995cited by this paper
• Single-step assembly of a gene and entire plasmid from large numbers of oligodeoxyribonucleotides.

  1995cited by this paper
• Molecular computation of solutions to combinatorial problems.

  1994cited by this paper
• Formal language theory and DNA: an analysis of the generative capacity of specific recombinant behaviors.

  1987cited by this paper

• Self-assembling nanocomposites for smart drug delivery: towards personalized and stimuli-responsive therapeutics

  2026cites this paper
• Biocomputing systems based on carbon materials and DNA.

  2025cites this paper
• Demonstration of a Scalable DNA Computing Platform: Writing and Selection

  2025cites this paper
• High-speed 3D DNA PAINT and unsupervised clustering for unlocking 3D DNA origami cryptography

  2025cites this paper
• A fully-programmable integrated photonic processor for both domain-specific and general-purpose computing

  2025cites this paper
• Femtojoule-per-operation photonic computer for the subset sum problem

  2025cites this paper
• DNA Probe Computing System for Solving NP-Complete Problems

  2025cites this paper
• Practically Error-Free Junctions Enable Solving Large Instances of Exact Cover Problems Using Network-Based Biocomputation

  2025cites this paper
• Dna coding theory and algorithms

  2025cites this paper
• A DNA Strand Displacement-Based Computing Model for Solving Intractable Graph Problems

  2025cites this paper
• High-speed 3D DNA PAINT and unsupervised clustering for unlocking 3D DNA origami cryptography

  2025cites this paper
• Why cellular computations challenge our design principles.

  2025cites this paper
• A Localized Scalable DNA Logic Circuit System Based on the DNA Origami Surface

  2025cites this paper
• Brownian DNA Computing

  2025cites this paper
• DNA-based biocomputing circuits and their biomedical applications

  2025cites this paper
• Molecular approach to semiconductors: a shift towards ecofriendly manufacturing and neuroinspired interfaces

  2024cites this paper
• Redução de 3-SAT para Subconjunto Independente em Grafos: Implicações e Perspectivas

  2024cites this paper
• Reconfigurable integrated photonic processor for NP-complete problems

  2024cites this paper
• A biological-like synthesis framework for software engineering environments

  2024cites this paper
• Modeling One-Electron Oxidation Potentials and Hole Delocalization in Double-Stranded DNA by Multilayer and Dynamic Approaches

  2024cites this paper
• Design and fabrication of autonomous electronic lablets for chemical control

  2024cites this paper
• Scalable DNA recognition circuits based on DNA strand displacement

  2024cites this paper
• Design of Multi-Competitors Winner-Take-All Neural Networks Based on DNA Strand Displacement for Molecular Pattern Recognition

  2024cites this paper
• Solving the SAT problem with the string multiset rewriting calculus

  2024cites this paper
• New constructions of DNA codes under multiple constraints and parallel searching algorithms

  2024cites this paper
• A Reconfigurable Photonic Processor for NP-complete Problems

  2023cites this paper
• Construction of DNA Codes From Composite Matrices and a Bio-Inspired Optimization Algorithm

  2023cites this paper
• Fundamentals of DNA Computation in the Domain of Cryptosystems

  2023cites this paper
• A Study of Bio-inspired Computing in Bioinformatics: A State-of-the-art Literature Survey

  2023cites this paper
• A DNA Algorithm for Calculating the Maximum Flow of a Network

  2023cites this paper
• A DNA Coding Design based on Multi-objective Evolutionary Algorithm with Constraint

  2023cites this paper
• Intramolecular and intermolecular hole delocalization rules the reducer character of isolated nucleobases and homogeneous single-stranded DNA.

  2023cites this paper
• One-Electron Oxidation Potentials and Hole Delocalization in Heterogeneous Single-Stranded DNA

  2023cites this paper
• Scalable and programmable three-dimensional photonic processor

  2023cites this paper
• Integrated Photonic Computing beyond the von Neumann Architecture

  2023cites this paper
• Prime factorization via localized tile assembly in a DNA origami framework

  2023cites this paper
• Construction of DNA-based molecular circuits using normally open and normally closed switches driven by lambda exonuclease.

  2023cites this paper
• Optimal design of DNA coding based on multi-strategy JAYA algorithm

  2023cites this paper
• An amplified logic gate driven by in situ synthesis of silver nanoclusters for identification of biomarkers.

  2023cites this paper
• A JAYA algorithm based on normal clouds for DNA sequence optimization

  2023cites this paper
• Simultaneous Recognition of Over- and Under-Expressed MicroRNAs Using Nanopore Decoding

  2023cites this paper
• M-State and N-Color (M–N = 1–1, 2–1, and 1–2) Turing Algorithms Demonstrated via DNA Self-Assembly

  2023cites this paper
• Real-Time Resource Allocation in Passive Optical Network for Energy-Efficient Inference at GPU-Based Network Edge

  2022cites this paper
• An automated DNA computing platform for rapid etiological diagnostics

  2022cites this paper
• Novel Applications of Ant Colony Optimization with the Traveling Salesman Problem in DNA Sequence Optimization

  2022cites this paper
• Solving the 3‐Satisfiability Problem Using Network‐Based Biocomputation

  2022cites this paper
• Logical Analysis of Multiple Single-Nucleotide-Polymorphisms with Programmable DNA Molecular Computation for Clinical Diagnostics.

  2022cites this paper
• Comparative analysis of genome code complexity and manufacturability with engineering benchmarks

  2022cites this paper
• Multirule-Combined Algorithmic Assembly Demonstrated by DNA Tiles

  2022cites this paper
• Watson-Crick conjugates of words and languages

  2022cites this paper
• Roadmap for network-based biocomputation

  2022cites this paper
• Demonstration of Big Bang-like patterns through logic-implemented DNA algorithmic assembly

  2022cites this paper
• Solving the 3-SAT problem using network-based biocomputation

  2022cites this paper
• A universal DNA computing model for solving NP-hard subset problems

  2022cites this paper
• Optimal Codeword Construction for DNA-based Finite Automata

  2022cites this paper
• Graph Computation Using Algorithmic Self-Assembly of DNA Molecules.

  2022cites this paper
• Parallel molecular computation on digital data stored in DNA

  2022cites this paper
• A Parallel DNA Algorithm for Solving the Quota Traveling Salesman Problem Based on Biocomputing Model

  2022cites this paper
• Infochemistry and the Future of Chemical Information Processing.

  2021cites this paper
• Genetically encoded RNA nanodevices for cellular imaging and regulation.

  2021cites this paper
• Nanopore decoding for a Hamiltonian path problem.

  2021cites this paper
• Alternative Paradigms of Computation

  2021cites this paper
• Concepts and Application of DNA Origami and DNA Self-Assembly: A Systematic Review

  2021cites this paper
• Logic gates in nanoscale based on interaction of thiolated DNA with AuNPs and strand displacement

  2021cites this paper
• A New Conservative Hyperchaotic System-Based Image Symmetric Encryption Scheme with DNA Coding

  2021cites this paper
• DNA Strand Displacement Computing Model for the SAT Problem

  2021cites this paper
• Upconversion Luminescence-Controlled DNA Computation for Spatiotemporally Resolved, Multiplexed Molecular Imaging.

  2021cites this paper
• DNA-computing-based methods for Model Checking Temporal Logics with Actions

  2021cites this paper
• Design and fabrication of networks for bacterial computing

  2021cites this paper
• Fundamental energy cost of finite-time parallelizable computing

  2021cites this paper
• The art of molecular computing: Whence and whither

  2021cites this paper
• Demonstration of elementary functions via DNA algorithmic self-assembly.

  2021cites this paper
• Developing a Mathematics Curriculum for the Biosciences

  2021cites this paper
• Multifunctional Clip Strand for the Regulation of DNA Strand Displacement and Construction of Complex DNA Nanodevices.

  2021cites this paper
• Physical requirements for scaling up network-based biocomputation

  2021cites this paper
• As good as it gets: a scaling comparison of DNA computing, network biocomputing, and electronic computing approaches to an NP-complete problem

  2021cites this paper
• Solving the subset sum problem with a nonideal biological computer

  2021cites this paper
• Strand Displacement in DNA ‐Based Nanodevices and Logic

  2021cites this paper
• Nanopore Decoding for DNA Computing

  2021cites this paper
• DNA Computing: Methodologies and Challenges

  2021cites this paper
• Advances in Soft Materials for Sustainable Electronics

  2021cites this paper
• Future DNA computing device and accompanied tool stack: Towards high-throughput computation

  2021cites this paper
• Toward Smart Information Processing with Synthetic DNA Molecules.

  2021cites this paper
• DNA Switching Circuits Based on Binary Tree

  2021cites this paper
• Morphogenetic systems for resource bounded computation and modeling

  2021cites this paper
• Molecular swarm robots: recent progress and future challenges

  2020cites this paper
• Decoding DNA data storage for investment

  2020cites this paper
• Bio-inspired Computing: Theories and Applications: 14th International Conference, BIC-TA 2019, Zhengzhou, China, November 22–25, 2019, Revised Selected Papers, Part II

  2020cites this paper
• Demonstration of Arithmetic Calculations by DNA Tile-Based Algorithmic Self-Assembly.

  2020cites this paper
• The N-Dimension Computing Machine Postulate

  2020cites this paper
• DNA Nanotechnology-based Biocomputing

  2020cites this paper
• Parallel DNA Algorithms of Generalized Traveling Salesman Problem-Based Bioinspired Computing Model

  2020cites this paper
• In Vitro Identification of Hamiltonian Cycle using Circular Structure Assisted DNA Computer.

  2020cites this paper
• DNA Computing Model for Satisfiability Problem Based on Hybridization Chain Reaction

  2020cites this paper
• Long-Range Ordered Water Correlations between A–T/C–G Nucleotides

  2020cites this paper
• Alternative Modes of Computation

  2020cites this paper
• DNA Computing Based RNA Genetic Algorithm

  2020cites this paper
• Constraining DNA Sequences With a Triplet-Bases Unpaired

  2020cites this paper
• Cancer diagnosis with DNA molecular computation

  2020cites this paper
• Chemical Reaction Networks and Stochastic Local Search

  2019cites this paper