Combinatorial tasks are among the hardest for traditional computers. A good example is finding the optimum path through a large complicated network. Every possible path must be evaluated and as datasets grow the computing time grows exponentially making some tasks unfeasible. One practical example is verification of VLSI (very large scale integrated) semiconductor circuit design. Indeed, many VLSI circuit designs are never ‘fully verified’ because the combinatorial calculation is prohibitively time-consuming and instead rely on approximations.

Last week, a group of international researchers brought a new approach to the combinatorial problem processing challenge, which they say is the world’s first “biomolecular motor-based” parallel computer. Not only does it solve combinatorial problems much faster but also with orders of magnitude less power consumption than comparable electronic computers, they report.

“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,” write the authors in their paper, “Parallel computation with molecular-motor-propelled agents in nanofabricated networks”[i], published in PNAS last week.

So what is a biomolecular motor-based parallel computer?

The researchers take components of a typical cell – tiny microtubule filaments that are normally part of a cell’s cytoskeleton and motor proteins that do the pushing and pulling – and enter them into a network of microchannels whose geometry is a ‘computing’ machine. As the microtubules flow through the network, they are directed by ‘gates’, which perform a kind of addition. (see diagram on the side).

Conceptually, the approach involves, “[E]ncoding 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….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 [microtubules].”

The new work is from researchers whose various affiliations include UC Berkeley, Lund University, Technische Universitat, Max Planck Institute, Linneaus University, McGill University, and the University of Liverpool (authors listed at end of article). Their proof of concept work, spelled out in more detail below, could have major impact on efforts to solve many combinatorial tasks besides circuit design verification, such as protein folding an design, and optimal network routing.

“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,” contend the authors.

There have been many efforts to develop and apply novel computing architectures to the combinatorial calculation problem. DNA computing and quantum computing come to mind. The authors note most of the new approaches have significant drawbacks:

• DNA computation, which generates mathematical solutions by recombining DNA strands, or DNA static or dynamic nanostructures, is limited by the need for impractically large amounts of DNA.
• Quantum computation is limited in scale by decoherence and by the small number of qubits that can be integrated.
• Microfluidics-based parallel computation 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.

The bio-molecular motor method, argue the authors, overcomes most challenges and has many benefits not least much improved heat dissipation characteristics, “the approach demonstrated here consumes orders of magnitude less energy per operation compared with both electronic and microfluidic computers.”

Here is a bit more detail on how the computation is done. 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 agents are guided downward by the channels in vertical or diagonal directions.

Two types of junctions were designed to regulate the motion of agents in the network: “split junctions,” where agents are randomly distributed between two forward paths, and “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.”

After traversing the network, the filaments emerge at exits corresponding to the target sums and are either recycled back to the entrance point or collected. The channel networks were fabricated by electron-beam lithography on SiO2 substrates to obtain the required resolution and fidelity.

Minimizing computation errors is also an important component; the error rates of microtubules flow at pass junctions must be kept as low as possible. In the proof-of-concept experiment, the results were promising. 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 experimental data are in good agreement with those obtained by Monte Carlo simulations.

The details of the process are best taken directly from the paper, which has multiple figures.

There are certainly challenges beyond the reported POC work to make biomolecular motor-based computing practical. The authors note six:

1. Scaling up of the physical network size from currently “100 × 100 μm2 to wafer size, which is achievable by current patterning technology.
2. Reduction of the filament feeding time, which can be achieved by using networks with multiple entrances, or by self-replicating filaments.
3. Reduction of pass-junction error rates, which can be realized by simulation-driven design by evolutionary algorithms for designing the junction geometries or by using 3D geometries such as bridges or tunnels which would offer zero error rates at pass junctions.
4. To circumvent the inherent difficulties of tracking large numbers of individual filaments, automatic readout schemes at exits of interest will likely be required.
5. Programmable devices which can flexibly encode different problems could be achieved by using heat-controlled or electrostatic gates in only one programmable type of junction instead of the two (isomorphic) static junctions.
6. 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.

[i] Parallel computation with molecular-motor-propelled agents in nanofabricated networks, Proceeding of the National Academy of Science; Dan V. Nicolau Jr., Mercy Lard, Till Kortend, Falco C. M. J. M. van Delftf, Malin Perssong, Elina Bengtssong, Alf Månssong, Stefan Diezd,e, Heiner Linkec, and Dan V. Nicolau; http://www.pnas.org/content/early/2016/02/17/1510825113.abstract

Image Credits: Till Korten, B CUBE; Mercy Lard, Lund University; Falco van Delft, Philips Research