PubMed Health⌕ Search
Home/Archive/PubMed

PubMed · 11896237

Solution of a 20-variable 3-SAT problem on a DNA computer.

Ravinderjit S Braich·Nickolas Chelyapov·Cliff Johnson·Paul W K Rothemund·Leonard Adleman
View original source ↗Export metadata ↓

Abstract

A 20-variable instance of the NP-complete three-satisfiability (3-SAT) problem was solved on a simple DNA computer. The unique answer was found after an exhaustive search of more than 1 million (2(20)) possibilities. This computational problem may be the largest yet solved by nonelectronic means. Problems of this size appear to be beyond the normal range of unaided human computation.

Explore related subjects

Base PairingBase SequenceComputersComputing MethodologiesDNADNA, Single-StrandedElectrophoresis, Polyacrylamide GelGene LibraryNucleic Acid HybridizationOligonucleotide ProbesPolymerase Chain ReactionJournal ArticleResearch Support, U.S. Gov't, Non-P.H.S.

Keep this discovery

Explore connections, maps & timelines

BibTeXRIS

Ravinderjit S Braich, Nickolas Chelyapov, Cliff Johnson, Paul W K Rothemund, Leonard Adleman. 2002-03-14. Solution of a 20-variable 3-SAT problem on a DNA computer.. https://doi.org/10.1126/science.1069528

Cite the original work for its findings. Save a collection to share your selection of sources.

KEEP EXPLORING

Related citations

PubMed2013

Application of mutated miR-206 target sites enables skeletal muscle-specific silencing of transgene expression of cardiotropic AAV9 vectors.

Insertion of completely complementary microRNA (miR) target sites (miRTS) into a transgene has been shown to be a valuable approach to specifically repress transgene expression in non-targeted tissues. miR-122TS have been successfully used to silence transgene expression in the liver following systemic application of cardiotropic adeno-associated virus (AAV) 9 vectors. For miR-206-mediated skeletal muscle-specific silencing of miR-206TS-bearing AAV9 vectors, however, we found this approach failed due to the expression of another member (miR-1) of the same miR family in heart tissue, the intended target. We introduced single-nucleotide substitutions into the miR-206TS and searched for those which prevented miR-1-mediated cardiac repression. Several mutated miR-206TS (m206TS), in particular m206TS-3G, were resistant to miR-1, but remained fully sensitive to miR-206. All these variants had mismatches in the seed region of the miR/m206TS duplex in common. Furthermore, we found that some m206TS, containing mismatches within the seed region or within the 3' portion of the miR-206, even enhanced the miR-206- mediated transgene repression. In vivo expression of m206TS-3G- and miR-122TS-containing transgene of systemically applied AAV9 vectors was strongly repressed in both skeletal muscle and the liver but remained high in the heart. Thus, site-directed mutagenesis of miRTS provides a new strategy to differentiate transgene de-targeting of related miRs.

Base Pairing↗
PubMed2007

Charge localization in stacked radical cation DNA base pairs and the benzene dimer studied by self-interaction corrected density-functional theory.

The incomplete cancellation of the electron self-interaction can be a serious shortcoming of density-functional theory especially when treating odd-electron systems. In this work, several popular and potentially viable correction schemes are applied in order to characterize the electronic structure of stacked molecular pairs, consisting of a neutral molecule and adjacent radical cation, as a function of separation distance. The unphysical sharing of the positive charge between adjacent molecules separated by 6-7 A is corrected for by applying a new empirical scheme proposed by VandeVondele and Sprik [Phys. Chem. Chem. Phys. 2005, 7, 1363] with a unique choice of parameters. This method is subsequently applied to characterize the electronic structure of two neighboring guanines excised from a canonical Arnott B-DNA structure and will be used in future investigations of certain model DNA fibers.

Base Pairing↗