Computation by self-assembly of DNA graphs

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

Research output: Contribution to journalArticlepeer-review


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
Issue number2
StatePublished - Jun 2003


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

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computer Science Applications


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

Cite this