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