A molecular algorithm for path self-assembly in 3 dimensions

A molecular algorithm is a set of molecular interactions that carry out a particular task. We describe a molecular algorithm for self-assembling a path between two stationary points when the locations of these points are not known in advance. While efficient path finding algorithms for electronic robots exist, molecules lack the centralized memory or computing power to implement them. The algorithm takes advantage of the inherent physics at the molecular scale, and unlike other biomimetic algorithms for path finding, is designed to work in an unstructured environment and does not require complex molecular components. Designed molecules self-assemble a DNA nanotube starting from a "seed" molecule attached to the start point. During growth, the DNA nanotube's end diffuses through space, and this diffusion is harnessed as a search process: when the DNA nanotube's end contacts the destination, it attaches to it and stops growing, forming a stable path. We use simulations and analysis to predict that paths of up 10 microns are formed with more than 99% probability if the destination is larger than 500 nanometers in diameter, making it practical. However, the probability of the DNA nanotube missing the destination is highly dependent on destination distance and size. It increases as exp [-1/Ω (r3)], where r is the Euclidean distance from the start point to the destination, and scales approximately as exp [-Ω(d)], where d is the diameter of the destination. A path finding algorithm that could work over longer distances or with small destinations will likely require new molecular components; we describe how new components could be used to solve the molecular path finding problem using a divide and conquer approach.