Network-based biocomputation: solving NP-complete problems with molecular motors

Speaker: Prof. Dr Heiner Linke, Lund University, Sweden
Date: Thursday 9 May, 1pm-2pm
Venue: Room 207-57, L2, CAI building 57
Zoom: This seminar is complete

Abstract
Network-based biocomputation (NBC) is an alternative, parallel computation approach that can potentially solve technologically important, combinatorial problems with much lower energy consumption than electronic processors. In NBC, a combinatorial problem is encoded into a physical, nanofabricated network. The problem is solved by biological agents (such as cytoskeletal filaments driven by molecular motors) that explore all possible pathways through the network in a massively parallel and highly energy-efficient manner. I will introduce the approach and report the state-of-the-art, which includes proof-of-concept solutions to instances of hard combinatorial problems such as Exact Cover and Satisfiability (SAT). I will also briefly discuss energy limits for computation in finite time, pointing out that massively parallel computation offers a fundamental energy advantage over traditional serial computation.

Nicolau et al.  PNAS 113, 2591 (2016) DOI
Korten et al., Nano Futures 6, 032002 (2022) DOI 10.1088/2399-1984/ac7d81
Konopik, Korten, Lutz & Linke, Nature Communications 14 447 (2023) DOI

Bio
Heiner Linke is a Professor of Nanophysics at Lund University in Sweden. Between 1998 – 2001 he was a research fellow in Sydney/Australia, before joining the physics department at the University of Oregon in 2001 where he received indefinite tenure in 2005 and remained until 2009. During 2013 – 2020 he was the Director of the Center for Nanoscience at Lund University (NanoLund), an interdisciplinary research environment engaging more than 350 scientists in three faculties. During 2021-2023 he served as the elected Deputy Dean (prorector) with responsibility for research at the Faculty of Engineering LTH (10 000 students). He has been the coordinator of five EU projects in the areas of nanoscale energy conversion and biocomputing, most lately an ERC Synergy project on artificial molecular motors (2021 – 2027). He was elected a member of the Royal Swedish Academy of Sciences (physics class) in 2014, where he has been serving on the Nobel Committee for Chemistry since 2016. In 2021 he was appointed to the Committee of Experts of the German Excellence Strategy.