Graph Computation Using Algorithmic Self-Assembly of DNA Molecules

DNA molecules have been used as novel computing tools, by which Synthetic DNA was designed to execute computing processes with a programmable sequence. Here, we proposed a parallel computing method using DNA origamis as agents to solve the three-color problem, an example of the graph problem. Each agent was fabricated with a DNA origami of ∼50 nm diameter and contained DNA probes with programmable sticky ends that execute preset computing processes. With the interaction of different nanoagents, DNA molecules self-assemble into spatial nanostructures, which embody the computation results of the three-color problem with polynomial numbers of computing nanoagents in a one-pot annealing step. The computing results were confirmed by atomic force microscopy. Our method is completely different from existing DNA computing methods in its computing algorithm, and it has an advantage in terms of computational complexity and results detection for solving graph problems.