Parts | Days | Selection | Search | Updates | Downloads | Help
BP: Fachverband Biologische Physik
BP 42: Biotechnology and bioengineering
BP 42.1: Talk
Friday, April 4, 2014, 09:30–09:45, HÜL 386
Massively parallel computation with self-propelled biological agents in nanofabricated networks — •Till Korten1, Dan V. Nicolau Jr.2, Mercy Lard3, Falco van Delft4, Malin Persson5, Elina Bengtsson5, Alf Månsson5, Stefan Diez1, Heiner Linke2, and Dan V. Nicolau6 — 1B CUBE - Center for Molecular Bioengineering, TU Dresden, Dresden, Germany — 2University of California, Berkeley, USA — 3Lund University, Lund, Sweden — 4Philips Research, Eindhoven, The Netherlands — 5Linnaeus University, Kalmar, Sweden — 6McGill University, Montreal, Canada
Combinatorial optimization problems are important for network routing, protein folding, and decrypting encoded messages. Solving such a problem often requires computation of all possible combinations of the elements in a problem set. However, the number of combinations - and thus the number of calculation operations - grows exponentially with the number of elements. Because they work sequentially, conventional computers are quickly overwhelmed with solving even relatively small problem sets of this type. We demonstrate a new parallel and scalable computation approach by encoding the NP-complete subset-sum problem in a physical network of lithographically defined nanochannels. The network, and thereby solution space, is explored in a massively parallel fashion by a large population of cytoskeletal filaments powered by molecular motors. All possible subset sums are recovered from the final positions of the filaments. The method is scalable, energy efficient, and may be used to augment conventional computing devices for solving combinatorial optimization problems.