Parallel computation with molecular-motor-propelled agents in nanofabricated networks

Dan V. Nicolau Jr., Mercy Lard, Till Korten, Falco C. M. J. M. van Delft, Malin Persson, Elina Bengtsson, Alf Månsson, Stefan Diez, Heiner Linke and Dan V. Nicolau

Freely available online through the PNAS open access option


The combinatorial nature of many important mathematical problems, including nondeterministic-polynomial-time (NP)-complete problems, places a severe limitation on the problem size that can be solved with conventional, sequentially operating electronic computers. There have been significant efforts in conceiving parallel-computation approaches in the past, for example: DNA computation, quantum computation, and microfluidics-based computation. However, these approaches have not proven, so far, to be scalable and practical from a fabrication and operational perspective. Here, we report the foundations of an alternative parallel-computation system in which a given combinatorial problem is encoded into a graphical, modular network that is embedded in a nanofabricated planar device. Exploring the network in a parallel fashion using a large number of independent, molecular-motor-propelled agents then solves the mathematical problem. This approach uses orders of magnitude less energy than conventional computers, thus addressing issues related to power consumption and heat dissipation. We provide a proof-of-concept demonstration of such a device by solving, in a parallel fashion, the small instance {2, 5, 9} of the subset sum problem, which is a benchmark NP-complete problem. Finally, we discuss the technical advances necessary to make our system scalable with presently available technology.

Actin filaments exploring the {2, 5, 9} device. The movie shows a time lapse of 200 typical fluorescence micrographs of actin filaments (shown in white) moving through a network (shown in blue) encoding the SSP with the set {2, 5, 9}. Exits labeled with green numbers represent correct results, and magenta numbers represent incorrect results. Below each exit, the number of actin that has arrived there is shown in white. The image of the network was obtained from an optical micrograph of the device and cropped to fit to the fluorescence image. Blurred objects passing over the network are actin filaments floating by in the solution. A background subtraction and contrast enhancement was performed evenly across the images with the use of ImageJ (imagej.nih.gov/ij/).