Tree (set theory)

Combinatorics

Graph

Nanotechnology

Topology (electrical circuits)

Nanorobotics

Mathematics

Algorithm

DNA origami

Statistics

Tree traversal

Artificial intelligence

Exploit

Set (abstract data type)

Chemistry

Materials science

Programming language

Path (computing)

Sequence (biology)

Computer science

Realization (probability)

Theoretical computer science

Vertex (graph theory)

Computer security

Biochemistry

Nature Materials

Molecular devices with information-processing capabilities hold great promise for developing intelligent nanorobotics. Here we demonstrate a DNA navigator system that can perform single-molecule parallel depth-first search on a ten-vertex rooted tree defined on a two-dimensional DNA origami platform. Pathfinding by the DNA navigators exploits a localized strand exchange cascade, which is initiated at a unique trigger site on the origami with subsequent automatic progression along paths defined by DNA hairpins containing a universal traversal sequence. Each single-molecule navigator autonomously explores one of the possible paths through the tree. A specific solution path connecting a given pair of start and end vertices can then be easily extracted from the set of all paths taken by the navigators collectively. The solution path laid out on origami is illustrated with single-molecule imaging. Our approach points towards the realization of molecular materials with embedded computational functions operating at the single-molecule level. DNA-based nanodevices with decision-making and information-processing capabilities have been developed. Here, a DNA-based molecular navigation system that explores a DNA origami maze for all possible solutions is reported.

Solving mazes with single-molecule DNA navigators