Oral presentation

Friday, June 17, 2016 (10:50 – 11:20) – Session X
From Nanodevices to General Theory to Living Cells Heiner Linke, Lund University, Sweden, Chair

Doing Maths with Autonomous Biological Agents

Dan Nicolau, Jr., Molecular Sense, Ltd., United Kingdom

Electronic computers are very good at performing a high number of operations at very high speeds – one-at-a-time. As a result, they struggle with combinatorial tasks that can be only be practically solved if many operations are performed in parallel. This has led to ideas about harnessing the parallelism inherent in biological signal processing for producing a new kind of computing system, such as DNA and molecular computing. In recent work, we presented a proof-of-concept for a parallel molecular-motor driven computer that solves a classic “combinatorial” NP-complete problem – Subset Sum. The device consists of a specifically designed, nanostructured network explored by a large number of molecular-motor-driven, protein filaments. This system is highly energy efficient, avoiding the heating issues limiting electronic computers. In this talk, we will discuss the potential and the challenges involved in developing this kind of technology and how it might be able to tackle problem classes that vex existing computational devices

Posters

Parallel Biocomputational Devices Based on Molecular Motors in Nanostructures
14-POS Board 14

Frida W. Lindberg1 , Till Korten2 , Mercy Lard1 , Mohammad A. Rahman3 , Hideyo Taktsuki3 , Cordula Reuther2 , Falco Van Delft4 , Malin Persson5 , Elina Bengtsson3 , Emelie Haettner1 , Alf Månsson3 , Stefan Diez2 , Dan Jr. V. Nicolau6 , Dan Nicolau7 , Heiner Linke1 .

1 Lund University, Lund, Sweden,
2 Technische Universität Dresden, Dresden, Germany,
3 Linnaeus University, Kalmar, Sweden, 4 High Tech Campus
4, Eindhoven, Netherlands,
5 Karolinska Institutet, Stockholm, Sweden,
6 Molecular Sense Ltd, Oxford, United Kingdom,
7 McGill University, Montreal, QC, Canada.

Solving mathematical problems of a combinatorial nature requires the exploration of a large solution space. As the number of possible solutions grows, this task becomes intractable for traditional, serial computation and therefore, calls for parallel computation techniques. Here we demonstrate an approach to solve a combinatorial problem by parallel computation based on molecular-motor driven biomolecules to explore physical networks of nanoscaled channels in a highly energy-efficient manner (Nicolau et al. 2016). We solve a combinatorial problem known as the subset sum problem, by encoding it into physical networks of channels patterned by lithography. These networks encode binary addition computers. The channel floors are covered with molecular motors that propel protein filaments fed into the network at one end, exploring the network. The filaments’ exit-points correspond to different solutions. Each filament explores one solution, thus, a large number of proteins can be used to compute problems in a massively parallel, energy-efficient manner. We present a proof-of-principle demonstration of the parallel-computation technique, and the status of our ongoing work to optimize and up-scale this system. We test different designs to optimize the individual architectural elements, reducing error rates and increase computing efficiency. We also aim to incorporate switchable junctions into the networks, providing programmable “gates” that can be switched on and off, controlling passage of protein filaments, enabling a high variability of networks. Furthermore, we develop different processing methods for fabricating devices. Our approach is scalable using existing nanofabrication technology. Because one NP complete problem can be converted into another, this technique can be used, in principle, to solve many NP complete problems, with applications in, drug design, scheduling activities, checking of electronic circuit designs, etc. Nicolau, D.V.J. et al., 2016. Massively-parallel computation with molecular motor-propelled agents in nanofabricated networks. PNAS 113(10), pp. 2591–2596.

Fungal Space Searching Can Outperform Standard Algorithms
36-POS Board 36

Hsin-Yu V. Lin, Dan V. Nicolau,
McGill University, Department of Bioengineering, Canada.

The ecological success of basidiomycetous fungi, accounting for ~30% of known fungal species, can be attributed to the efficient expansion of branched filaments (hyphae) when seeking out nutritional resources in the surrounding environment. Despite the fact that these fungi naturally colonize 3D micro-structured media, their growth behaviour has been primarily studied on flat surfaces. Fortunately, microfluidics provides a versatile methodology for the probing the fungal various space search strategies. Solving mazes is a difficult algorithmic exercise, which is why mazes are used to estimate the optimality of the behavioural response, or intelligence, of many higher organisms including ants, bees, mice, rats, octopi, and humans, as well as artificial intelligence-enabled robots. When presented to “intelligence-testing” geometries, e.g., mazes, fungi use a natural program for searching the available space. While different species present different variants of this fungal program, its framework is common and it consists of the interplay of two ‘sub-routines’: collision-induced branching, and directional memory. These studies also demonstrated that the natural program comprising the two ‘sub-routines’ is markedly superior to variants where one of these is, or both are suppressed. A comparison of the performance of the natural algorithm against those of several standard space searching ones revealed that fungi consistently outperforms Depth-First-Search (DFS) algorithm. Although the performance of the natural algorithms is inferior to that of’ informed algorithms’, e.g., A*, this under-performance does not importantly increase with the increase of the size of the maze. These findings encourage a systematic effort to harvest the natural space searching algorithms used by microorganisms, which, if efficient, can be reverse-engineered for graph and tree search strategies

Attention Everyone,

mark your calendar and watch online

Wednesday, May 25, 2016 – 4:30pm to 5:30pm

Dan V. Nicolau will present ‘Unconventional Computing’ at Stanford University.

Additional info: here + video

About the talk:

Many important mathematical problems, ranging from cryptography, network routing, and protein folding, require the exploration a large number of candidate solutions. Because the time required for solving these problems grows exponentially with their size, electronic computers, which operate sequentially, cannot solve them in a reasonable timeframe. Unfortunately, the parallel-computation approaches proposed so far, e.g., DNA-, and quantum-computing, suffer from fundamental and practical drawbacks, which prevented their successful implementation. On the other hand, biological entities, from microorganisms to humans, process information in parallel, routinely, for essential tasks, such as foraging, searching for available space, competition, and cooperation. However, aside of their sheer complexity, parallel biological processes are difficult to harness for artificial parallel computation because of a fundamental difference: biological entities process analog information, e.g., concentration gradients, whereas computing devices require the processing of numbers. This subtle, but important difference between artificial and biological computation, together with the opportunity to operate biocomputation with large numbers of (small) biological agents, opens three possible avenues for development.

Biological IT. The first opportunity relies on the study of the natural procedures used by biological agents, e.g., for space search and partitioning, chemotaxis, etc., followed by the translation of these procedures in abstract mathematical algorithms. These bioinspired algorithms can be then benchmarked against standard analogues used for similar tasks, and, if appropriate, improved and implemented. Along this development avenue, which is conceptually similar to other biomimetics efforts, such as biomimetic materials, we have shown that fungi used exquisitely efficient algorithms for search for available space; and that the chemotaxis procedures used by bacteria can be used to find edges of geometrical patterns.

Biosimulation. The second opportunity relies on the capacity of using large numbers of biological agents to explore complex networks which mimic real traffic situations. This line of development has been almost entirely dedicated to the study of network optimization performed by amoeboid organisms, e.g., Physarum, placed in geometrically confined environments which also contain chemotactic ‘cues’, e.g., larger concentrations of nutrients in set coordinates. This physical simulation of traffic networks resulted in many studies assessing the optimality of real traffic networks in many countries.

Biocomputation with biological agents in networks. Finally, the third, and arguably the most exciting development consists in the use of very large number of agents exploring purposefully-designed microfluidics networks. For instance, we reported the foundations of a 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, agents, e.g., 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.

The lecture will conclude with a perspective on the computation and simulation using biological entities in microfluidics structures, weighing the opportunities and challenges offered by various technological avenues.

Meet Us at the 2016 E-MRS Spring Meeting in Lille (France) from May 2 to 6

The conference will include 31 parallel symposia, 3 workshops & tutorials, one plenary session, one exhibition and much more. All technical sessions and non-technical events will be held at Lille Grand Palais.

V. Tokárová – Solving geometrical problems with bacteria

oral presentation is scheduled for 03/05/2016 – 16h15 – session B6.5

***

O. Kašpar – Confinement of water nanodroplets on micro/nano chessboard-like patterned surfaces

poster presentation is scheduled for 03/05/2016 – 17h35 – session B.P4.15