## New Research In

### Physical Sciences

### Social Sciences

#### Featured Portals

#### Articles by Topic

### Biological Sciences

#### Featured Portals

#### Articles by Topic

- Agricultural Sciences
- Anthropology
- Applied Biological Sciences
- Biochemistry
- Biophysics and Computational Biology
- Cell Biology
- Developmental Biology
- Ecology
- Environmental Sciences
- Evolution
- Genetics
- Immunology and Inflammation
- Medical Sciences
- Microbiology
- Neuroscience
- Pharmacology
- Physiology
- Plant Biology
- Population Biology
- Psychological and Cognitive Sciences
- Sustainability Science
- Systems Biology

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

Edited by Hillel Kugler, Microsoft Research, Cambridge, United Kingdom, and accepted by the Editorial Board January 18, 2016 (received for review June 5, 2015)

### This article has a reply. Please see:

## Significance

Electronic computers are extremely powerful at performing a high number of operations at very high speeds, sequentially. However, they struggle with combinatorial tasks that can be solved faster if many operations are performed in parallel. Here, we present proof-of-concept of a parallel computer by solving the specific instance {2, 5, 9} of a classical nondeterministic-polynomial-time complete (“NP-complete”) problem, the subset sum problem. The computer consists of a specifically designed, nanostructured network explored by a large number of molecular-motor-driven, protein filaments. This system is highly energy efficient, thus avoiding the heating issues limiting electronic computers. We discuss the technical advances necessary to solve larger combinatorial problems than existing computation devices, potentially leading to a new way to tackle difficult mathematical problems.

## Abstract

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.

Many combinatorial problems of practical importance, such as the design and verification of circuits (1), the folding (2) and design (3) of proteins, and optimal network routing (4), require that a large number of possible candidate solutions are explored in a brute-force manner to discover the actual solution. Because the time required for solving these problems grows exponentially with their size, they are intractable for conventional electronic computers, which operate sequentially, leading to impractical computing times even for medium-sized problems. Solving such problems therefore requires efficient parallel-computation approaches (5). However, the approaches proposed so far suffer from drawbacks that have prevented their implementation. For example, DNA computation, which generates mathematical solutions by recombining DNA strands (6, 7), or DNA static (8) or dynamic (9) nanostructures, is limited by the need for impractically large amounts of DNA (10⇓⇓–13). Quantum computation is limited in scale by decoherence and by the small number of qubits that can be integrated (14). Microfluidics-based parallel computation (15) is difficult to scale up in practice due to rapidly diverging physical size and complexity of the computation devices with the size of the problem, as well as the need for impractically large external pressure.

Here, we propose a parallel-computation approach, which is based on encoding combinatorial problems into the geometry of a physical network of lithographically defined channels, followed by exploration of the network in a parallel fashion using a large number of independent agents, with very high energy efficiency. To demonstrate operational functionality, we applied it to a small instance of a benchmark classical nondeterministic-polynomial-time complete (NP-complete) problem (16), the subset sum problem (SSP) (Fig. 1). This problem asks whether, given a set *S* = {s_{1}, s_{2}, ..., s_{N}} of *N* integers, there exists a subset of *S* whose elements sum to a target sum, *T*. More formally, the question is whether there is a solution *w*_{i} *T* from 0 to ^{N} different combinations, which––even for modest values of *N*––is impractical on electronic computers because of exponentially increasing time requirements (*SI Appendix*, section S1). Although more sophisticated algorithms exist (17⇓–19), none of these avoids the exponentially growing exploration time, a property that is harnessed in some cryptography systems to generate encoded messages (20).

Our approach replaces the requirement for exponentially growing time needed by traditional, electronic computers to solve NP-complete problems, with the requirement for an exponentially growing number of independent computing agents. We use a proof-of-concept device to successfully solve the specific three-variable instance {2, 5, 9} of the SSP. Key technical advancements necessary to scale up our approach to be of practical relevance include the need to reduce error rates and to supply sufficiently many computing agents. We identify several possible approaches to address these requirements.

## Results

In our network encoding of the SSP, the channel-guided unidirectional motions of agents are equivalent to elementary operations of addition, and their spatial positions in the network are equivalent to “running sums.” Starting from an entrance point at one corner of the network (Fig. 1, *Top Left*), agents are guided unidirectionally downward by the channels in vertical or diagonal directions. Two types of junctions were designed to regulate the motion of agents in the network: (*i*) “split junctions,” where agents are randomly distributed between two forward paths, and (*ii*) “pass junctions,” where agents are guided onward to the next junction along the initial direction. The vertical distance (measured as the number of junctions) between two subsequent rows of split junctions represents an integer from the set *S*. The process of an agent moving straight downward from a given split junction is equivalent to excluding the corresponding *s*_{i} from the summation, whereas traveling diagonally downward is equivalent to including that *s*_{i} in the subset sum. A solution Σ*w*_{i} *s*_{i} = *T*_{J} to the SSP is represented by an agent choosing a path to one of the exit nodes in the network (bottom row in Fig. 1). If a sufficiently large number of agents is used, all possible paths are explored, and therefore all possible subset sums of *S* are generated, simultaneously.

We implemented the proposed computational approach with biological agents that satisfy the following requirements: The agents (*i*) are available in large numbers at negligible cost; *(ii*) are self-propelled and thus do not require a global, external driving force; (*iii*) operate independently of each other to ensure parallel exploration; (*iv*) have small dimensions to enable use in high-density networks with high computing power per unit area; (*v*) move rapidly to maximize computational speed; and (*vi*) move in a predominantly forward direction (to ensure low error rates). In particular, we used cytoskeletal filaments (actin filaments and microtubules), which are propelled by molecular motors (myosin II and kinesin-1, respectively) along a surface in gliding motility assays (21, 22). Both kinds of cytoskeletal filaments have small diameters (∼10 nm for actin filaments and ∼25 nm for microtubules) and move at high speeds (5–10 µm s^{−1} for actin filaments driven by fast myosin II from skeletal muscle, and ∼0.5–1 µm s^{−1} for microtubules driven by kinesin-1). The filaments are guided unidirectionally (23, 24) along lithographically defined channels, which are functionalized with molecular motors, and whose roofs are open to supply the motors with biochemical fuel (adenosine 5′-triphosphate, ATP) by diffusion from the surrounding buffer fluid (25, 26), allowing for a distributed energy supply. The width of the channels was set to below 200 nm and 250 nm, for actin filaments and microtubules, respectively, which were observed to reliably guide cytoskeletal filaments (27⇓–29).

The general layouts of the networks used in our devices for microtubule–kinesin- and actin–myosin–based computations are shown in Fig. 2 and *SI Appendix*, Fig. S2.1, respectively. To start the computation, the filaments are collected from the bulk solution and guided to enter the network through loading zones (large tear-shaped areas in Fig. 2 and *SI Appendix*, Fig. S2.1). The computational networks comprise a set of standardized rectangular lattices, each containing two isomorphic unit cells representing the split junctions and pass junctions (Fig. 2, *Inset* and *SI Appendix*, Fig. S2.1). This standardized structure facilitates the future encoding of problems of any size and the scalability of fabrication, e.g., through step-and-repeat deep-UV lithography, for which the fabrication of channels with widths of 200 nm (as reported here), or below, is readily achievable.

To account for different stiffness and size of actin filaments compared with microtubules, we optimized the device design and the junction geometries individually for each filament system with the assistance of numerical modeling and simulation (*SI Appendix*, section S4). After traversing the network, the filaments emerge at exits corresponding to the target sums and are either recycled back to the entrance point (actin–myosin device; *SI Appendix*, section S2) or collected (microtubule–kinesin device; Fig. 2). The networks were fabricated by electron-beam lithography on SiO_{2} substrates to obtain the required resolution and fidelity (see *Materials and Methods Summary* for fabrication details).

The minimization of computation errors requires that the error rates of pass junctions are as low as possible, i.e., that filaments do not progress along erroneous paths and emerge at exit nodes not corresponding to target sums (*SI Appendix*, section S1). In contrast, the error rates of split junctions (designed to yield a 50:50 split) are less critical to computational performance because these junctions mainly serve to distribute agents across the network, thus ensuring that no solution is missed. Experiments (see *Materials and Methods Summary* for experimental procedures and imaging details) confirmed that the junction designs in our devices fulfill these performance requirements (Fig. 3). Fluorescently marked cytoskeletal filaments traversing individual split junctions and pass junctions (Fig. 3*A*) were tracked using fluorescence microscopy (Fig. 3*B*). Statistical analysis of the motion of actin filaments and the microtubules showed that 97.9% and 99.7%, respectively, took the correct (straight) paths through pass junctions, whereas split junctions distributed filaments approximately evenly (Fig. 3*C* and *SI Appendix*, section S5).

Our proof-of-concept experiments on the set {2, 5, 9} show that both the actin–myosin system and the microtubule–kinesin system can be used to solve a combinatorial problem by parallel computation (Fig. 4). Superimposed fluorescence micrographs show time-integrated paths of the fluorescently labeled filaments (Fig. 4*A*). These images demonstrate that the filaments traversed the network from the entrance point to the exit nodes that represent correct results (Fig. 4*A*, green exit numbers). Statistical analysis of the number of filaments leaving each exit (obtained by counting the filaments in image sequences tracking each filament) confirms that both types of agents found all of the correct results and that significantly more agents (*P* < 0.002; unpaired two-tailed *t* test) of both types exited nodes corresponding to correct results than incorrect results (Fig. 4*B*). The experimental data are in good agreement with those obtained by Monte Carlo simulations (Fig. 4*C* and *SI Appendix*, section S6), which are based on the experimentally measured error rates at each junction type (obtained separately for actin filaments and microtubules; Fig. 3*C* and *SI Appendix*, section S5).

## Discussion

We developed a parallel-computation approach based on encoding combinatorial problems into the geometry of physical networks. We showed that these networks can be manufactured lithographically and explored using independent agents. Using such a device, we demonstrated the solution of one particular three-variable instance of the SSP.

Notably, once the device is loaded with the required number of agents, the effective computational time for NP-complete problems grows only polynomially, e.g., as *N*^{2} if the elements of *S* are approximately equidistantly spaced. This is in contrast to traditional, sequentially operating, electronic computers, where the time required to explore every possible solution sequentially would scale exponentially as 2^{N}. However, it is inherent to combinatorial and NP-complete problems (assuming P! = NP) that the exploration of the entire solution space requires the use of exponentially increasing amounts of some resource, such as time, space, or material. In the present case this fundamental requirement manifests itself in the number of agents needed, which grows exponentially with 2^{N}*.* Effectively we are trading the need of time for the need of molecular mass.

The error rates of this first device are too large for scaling up to problems containing more than ∼10 variables (see *SI Appendix*, section S1 for a more detailed scaling analysis).

Nevertheless, we argue that our approach has the potential to be more scalable in practice than other approaches because it offers several advantages: (*i*) Myosin II and kinesin-1 molecular motors use a distributed energy supply (ATP in the surrounding solution), thus eliminating the need for external forces (such as pressure or an electric potential) to drive the computation. This need inherently prevents, for example, microfluidic approaches from scaling up, because in these devices the pressures needed to pump fluid through the network become prohibitively large for large *N* (30). (*ii*) The molecular motors operate in a highly energy-efficient manner. As a result, the approach demonstrated here consumes orders of magnitude less energy per operation compared with both electronic and microfluidic computers, eliminating issues related to the dissipation of heat. Specifically, we estimate an energy cost of 2–5 × 10^{−14} J per operation for a molecular-motor-based device compared with about 3–6 × 10^{−10} J per operation for the most advanced electronic computers, or an estimated minimum of 10^{−12} J per operation for microfluidics-based computers (*SI Appendix*, section S7). (*iii*) The networks in which the problems are encoded in our approach are planar and comprise standardized modules, therefore being fully scalable with existing technology (see *SI Appendix*, section S1 for a more detailed discussion). Thus, they avoid potential engineering challenges associated with building large-scale 3D microfluidics devices.

Most importantly, however, we foresee several practical solutions to managing the need for exponentially increasing numbers of agents that we highlighted above. (*i*) The number of agents can self-adjust to the problem size. Specifically, cytoskeletal filaments can self-replicate as they traverse the network by enzymatic splitting and simultaneous elongation (31, 32). Alternatively, self-propelled, dividing microorganisms can be used as agents (33⇓–35). Thus, the larger the network, the more the agents will multiply, in an exponential fashion. Any kind of agent multiplication scheme will also solve potential problems with sequential feeding of the agents into the network through a single entrance, which represents a bottleneck for large *N.* Moreover, for cytoskeletal filaments, the splitting and elongation rates will be limited by the global concentrations of enzymes and filament subunits, respectively. Thus, multiplication will be negatively regulated in parts of the network where the agent density is high (i.e., above the density needed for successful computation), consequently counteracting the risk of channel clogging. (*ii*) The NP-complete problem is encoded into a planar, physical network and not into the agents themselves. This simplifies fabrication and encoding because the network that encodes the problem grows polynomially, whereas the exponentially scaling number of cytoskeletal filaments can be fabricated in bulk. This is in contrast to DNA computing, where large amounts of DNA need to be specifically synthesized for each problem. Furthermore, because of their generic nature, agents can continue to explore the network as long as ATP is available, which means they can be by recirculated and used more than once (*SI Appendix*, Fig. S2.1). (*iii*) Because our device implements basic addition operations, it can benefit from existing optimized algorithms and can be easily combined with a conventional computer to form a hybrid device. For example, an electronic computer could be used to, first, solve a subset of the largest numbers in the SSP. Then, the solutions calculated by the computer would be passed on to a set of biological computers described here, drastically reducing the number of agents needed because the biological computer solves only that part of the problem that overwhelms the electronic computer. Furthermore, the time needed to feed the filaments into the network would be further reduced because many entrances can be used in parallel. An extended analysis of scaling and energy considerations is presented in *SI Appendix*, sections S1 and S7, respectively.

Summarizing, the technical advances that would be necessary for a future device able to challenge an electronic computer are (*i*) scaling up of the physical network size from currently ∼100 × 100 µm^{2} to wafer size, which is achievable by current patterning technology. (*ii*) Reduction of the filament feeding time, which can be achieved by using networks with multiple entrances, or by self-replicating filaments, see above. (*iii*) Reduction of pass-junction error rates. We expect that this can be realized by simulation-driven design (such as described in *SI Appendix*, section S4), by evolutionary algorithms for designing the junction geometries (36, 37), or by using 3D geometries such as bridges or tunnels (38) which would offer zero error rates at pass junctions. (*iv*) To circumvent the inherent difficulties of tracking large numbers of individual filaments, automatic readout schemes at exits of interest can be used (39). (*v*) Programmable devices which can flexibly encode different problems could be achieved by using heat-controlled (40) or electrostatic (41) gates in only one programmable type of junction instead of the two (isomorphic) static junctions. (*vi*) Finally, filaments can be prevented from attaching to or detaching from the network by using closed channels with porous openings for allowing the supply of ATP (42).

The potential practical relevance of our approach goes beyond solving SSP, because all NP-complete problems can be converted to one another using a polynomial-time conversion (7, 43) and due to the general nature of our SSP computation network (namely a computer that can perform addition, and, by using right-to-left diagonals, also subtraction). Therefore, our approach has the potential to be general and to be developed further to enable the efficient encoding and solving of a wide range of large-scale problems. Accomplishing this would move forward (but not remove) the limit of the size of combinatorial problems that can be solved.

## Materials and Methods Summary

Please see the *SI Appendix* for a detailed description of the materials and methods.

### Fabrication of Computational Networks for Use with the Actin–Myosin System.

Electron-beam lithography (EBL) was used for pattern formation in a poly(methyl methacrylate) (PMMA) resist on a SiO_{2}-coated Si substrate. After development and O_{2}-plasma-ashing [to ensure that the PMMA was hydrophilic and therefore unable to support motility (27)], the sample was silanized with trimethylchlorosilane to promote motility on the floor of the exposed SiO_{2} substrate (44). Wetting of the surface was performed to reduce the possibility of air bubbles forming in the channels (45).

### Fabrication of Computational Networks for Use with the Microtubule–Kinesin System.

A silicon wafer was sputter-deposited with Au, sandwiched between two Ti adhesion layers. Next, a quartz layer was deposited, followed by a TiW layer and a ZEP520 positive-tone electron-beam resist layer. After exposure in an EBL system and development, the TiW, the quartz, and the upper Ti layers were etched by reactive ion etching down to the Au layer. Finally, the resist residue and the TiW were removed.

### Actin–Myosin in Vitro Motility Assays.

The in vitro motility assays were performed at 26–29 °C, as described previously (46). Briefly, the flow cell was preincubated with (*i*) heavy meromyosin (47) (120 µg mL^{−1}) for 4 min; (*ii*) 1 mg mL^{−1} bovine serum albumin for 1 min; (*iii*) rhodamine-phalloidin–labeled actin (48) filaments (10-nM monomeric concentration) for 1 min. The flow cell was washed both before and after actin filament incubation. Next, the flow cell was incubated with rigor solution (without ATP) for initial observations. Motility was initiated by introducing a MgAdenosine-5′-triphosphate (MgATP)-containing assay solution.

### Microtubule–Kinesin in Vitro Motility Assays.

Microtubule–kinesin gliding assays were performed using full-length kinesin-1 (kinesin) from *Drosophila* (49) and rhodamine-labeled tubulin (50) by following a procedure (51) that was upgraded for motility in nanochannels (52). The SiO_{2} surface of the computational chip was passivated with 2-[Methoxy(poly-ethyleneoxy) propyl] trimethoxysilane] to prevent protein binding anywhere except on the gold bottom of the channels. Flow cells were perfused with (*i*) casein-containing solution (0.5 mg ml^{−1}, 5 min); *(ii*) kinesin solution (2 nM, 5 min); and (*iii*) motility solution containing 1 mM ATP and rhodamine-labeled, taxol-stabilized.

### Imaging Methods.

Rhodamine-labeled cytoskeletal filaments were observed using inverted fluorescence microscopes. Images were recorded with electron-multiplying charge-coupled device cameras and analyzed with ImageJ (imagej.nih.gov/ij/). Microtubule paths were tracked with software developed in-house (53).

## Acknowledgments

Dan V. Nicolau Jr. thanks Grant Shoffner and Yue Shark Yu from University of California, Berkeley, for help in running stochastic simulations. Financially supported by the European Union Seventh Framework Programme (FP7/2007-2011) under Grant Agreements 228971 [Molecular Nano Devices (MONAD)] and 613044 [Parallel computing based on designed networks explored by self-propelled, biological agents (ABACUS)]; Defense Advanced Research Projects Agency under Grant Agreement N66001-03-1-8913; by NanoLund; by the Miller Foundation; by the Swedish Research Council (Projects 621-2010-5146 and 2010-4527); The Carl Trygger Foundation, German Research Foundation within the Cluster of Excellence Center for Advancing Electronics Dresden and the Heisenberg Program; and by Linnaeus University.

## Footnotes

↵

^{1}Dan V. Nicolau Jr., M.L., and T.K. contributed equally to this work.↵

^{2}Present address: Molecular Sense, Ltd., Wallasey CH44 1AJ, United Kingdom.- ↵
^{3}To whom correspondence may be addressed. Email: heiner.linke{at}ftf.lth.se or dan.nicolau{at}mcgill.ca.

Author contributions: Dan V. Nicolau Jr. and Dan V. Nicolau conceived the calculation method and designed the overall network; F.C.M.J.M.v.D designed the junctions; M.L., T.K., F.C.M.J.M.v.D, A.M., S.D., and H.L., designed the device layouts; M.L. and F.C.M.J.M.v.D fabricated the devices; M.L., T.K., M.P., and E.B. ran motility experiments and analyzed motility data; Dan V. Nicolau Jr., T.K., and A.M. carried out numerical simulations; Dan V. Nicolau initiated the project; Dan V. Nicolau and H.L. coordinated the project; and Dan V. Nicolau Jr., M.L., T.K., F.C.M.J.M.v.D., M.P., E.B., A.M., S.D., H.L., and Dan V. Nicolau contributed to planning the work, to data interpretation, and to writing the manuscript.

The authors declare no conflict of interest.

This article is a PNAS Direct Submission. H.K. is a guest editor invited by the Editorial Board.

This article contains supporting information online at www.pnas.org/lookup/suppl/doi:10.1073/pnas.1510825113/-/DCSupplemental.

Freely available online through the PNAS open access option.

## References

- ↵
- ↵
- ↵.
- Pierce NA,
- Winfree E

- ↵
- ↵.
- Nicolau DV, et al.

*Microelectron Eng*83(4-9 Spec. Iss.):1582-1588 - ↵.
- Adleman LM

- ↵.
- Lipton RJ

- ↵
- ↵.
- Qian L,
- Winfree E

- ↵
- ↵.
- Braich RS,
- Chelyapov N,
- Johnson C,
- Rothemund PWK,
- Adleman L

- ↵.
- Ouyang Q,
- Kaplan PD,
- Liu S,
- Libchaber A

- ↵.
- Reif J,
- LaBean T,
- Sahu S,
- Yan H,
- Yin P

*Unconventional Programming Paradigms*, eds Banâtre J-P, Fradet P, Giavitto J-L, Michel O, Lecture Notes in Computer Science (Springer, Berlin), Vol 3566, pp 173–187 - ↵
- ↵.
- Chiu DT,
- Pezzoli E,
- Wu H,
- Stroock AD,
- Whitesides GM

- ↵.
- Garey MR,
- Johnson DS

- ↵.
- Caprara A,
- Kellerer H,
- Pferschy U

- ↵
- ↵
- ↵
- ↵
- ↵.
- Kron SJ,
- Spudich JA

- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵.
- Sun HQ,
- Yamamoto M,
- Mejillano M,
- Yin HL

- ↵
- ↵
- ↵.
- Tero A, et al.

- ↵
- ↵
- ↵
- ↵
- ↵
- ↵.
- van den Heuvel MG,
- de Graaff MP,
- Dekker C

- ↵.
- Graczyk M,
- Balaz M,
- Kvennefors A,
- Linke H,
- Maximov I

*J Vac Sci Technol*,*B*30(6):06FF09-1–06FF09-4 - ↵.
- Karp RM

- ↵
- ↵
- ↵
- ↵
- ↵
- ↵.
- Coy DL,
- Wagenbach M,
- Howard J

- ↵
- ↵
- ↵
- ↵

## Citation Manager Formats

### More Articles of This Classification

### Physical Sciences

### Computer Sciences

### Biological Sciences

### Biophysics and Computational Biology

### Related Content

### Cited by...

- Something has to give: scaling combinatorial computing by biological agents exploring physical networks encoding NP-complete problems
- Computing exponentially faster: implementing a non-deterministic universal Turing machine using DNA
- Reply to Einarsson: The computational power of parallel network exploration with many bioagents
- New biological device not faster than regular computer