Computation by self-assembly of DNA graphs

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

Research output: Contribution to journalArticlepeer-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 languageEnglish (US)
Pages (from-to)123-137
Number of pages15
JournalGenetic Programming and Evolvable Machines
Volume4
Issue number2
DOIs
StatePublished - 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

Fingerprint Dive into the research topics of 'Computation by self-assembly of DNA graphs'. Together they form a unique fingerprint.

Cite this