Computation by self-assembly of DNA graphs

Nataša Jonoska; Phiset Sa-Ardyen; Nadrian C. Seeman

doi:10.1023/A:1023980828489

Computation by self-assembly of DNA graphs

Nataša Jonoska, Phiset Sa-Ardyen, Nadrian C. Seeman

Chemistry

Research output: Contribution to journal › Article › peer-review

Abstract

Using three dimensional graph structure and DNA self-assembly we show that theoretically 3-SAT and 3-colorability can be solved in a constant number of laboratory steps. In this assembly, junction molecules and duplex DNA molecules are the basic building blocks. The graphs involved are not necessarily regular, so experimental results of self-assembling non regular graphs using junction molecules as vertices and duplex DNA molecules as edge connections are presented.

Original language	English (US)
Pages (from-to)	123-137
Number of pages	15
Journal	Genetic Programming and Evolvable Machines
Volume	4
Issue number	2
DOIs	https://doi.org/10.1023/A:1023980828489
State	Published - Jun 2003

Keywords

3-SAT
DNA-computing
Graphs
Junction molecules
Ligation
Self-assembly

ASJC Scopus subject areas

Software
Theoretical Computer Science
Hardware and Architecture
Computer Science Applications

Access to Document

10.1023/A:1023980828489

Cite this

@article{29960cc16ce34031aa9a8410d9c9e130,

title = "Computation by self-assembly of DNA graphs",

abstract = "Using three dimensional graph structure and DNA self-assembly we show that theoretically 3-SAT and 3-colorability can be solved in a constant number of laboratory steps. In this assembly, junction molecules and duplex DNA molecules are the basic building blocks. The graphs involved are not necessarily regular, so experimental results of self-assembling non regular graphs using junction molecules as vertices and duplex DNA molecules as edge connections are presented.",

keywords = "3-SAT, DNA-computing, Graphs, Junction molecules, Ligation, Self-assembly",

author = "Nata{\v s}a Jonoska and Phiset Sa-Ardyen and Seeman, {Nadrian C.}",

note = "Funding Information: This work has been supported by grants GM-29554 from NIGMS, N00014-98-1-0093 from ONR, grants DMI-0210844, EIA-0086015, EIA-0074808, DMR-01138790, and CTS-0103002 from NSF, and F30602-01-2-0561 from DARPA/ AFOSR.",

year = "2003",

month = jun,

doi = "10.1023/A:1023980828489",

language = "English (US)",

volume = "4",

pages = "123--137",

journal = "Genetic Programming and Evolvable Machines",

issn = "1389-2576",

publisher = "Springer New York",

number = "2",

}

TY - JOUR

T1 - Computation by self-assembly of DNA graphs

AU - Jonoska, Nataša

AU - Sa-Ardyen, Phiset

AU - Seeman, Nadrian C.

N1 - Funding Information: This work has been supported by grants GM-29554 from NIGMS, N00014-98-1-0093 from ONR, grants DMI-0210844, EIA-0086015, EIA-0074808, DMR-01138790, and CTS-0103002 from NSF, and F30602-01-2-0561 from DARPA/ AFOSR.

PY - 2003/6

Y1 - 2003/6

N2 - Using three dimensional graph structure and DNA self-assembly we show that theoretically 3-SAT and 3-colorability can be solved in a constant number of laboratory steps. In this assembly, junction molecules and duplex DNA molecules are the basic building blocks. The graphs involved are not necessarily regular, so experimental results of self-assembling non regular graphs using junction molecules as vertices and duplex DNA molecules as edge connections are presented.

AB - Using three dimensional graph structure and DNA self-assembly we show that theoretically 3-SAT and 3-colorability can be solved in a constant number of laboratory steps. In this assembly, junction molecules and duplex DNA molecules are the basic building blocks. The graphs involved are not necessarily regular, so experimental results of self-assembling non regular graphs using junction molecules as vertices and duplex DNA molecules as edge connections are presented.

KW - 3-SAT

KW - DNA-computing

KW - Graphs

KW - Junction molecules

KW - Ligation

KW - Self-assembly

UR - http://www.scopus.com/inward/record.url?scp=1342342131&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=1342342131&partnerID=8YFLogxK

U2 - 10.1023/A:1023980828489

DO - 10.1023/A:1023980828489

M3 - Article

AN - SCOPUS:1342342131

SN - 1389-2576

VL - 4

SP - 123

EP - 137

JO - Genetic Programming and Evolvable Machines

JF - Genetic Programming and Evolvable Machines

IS - 2

ER -

Computation by self-assembly of DNA graphs

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this