Solving Exact Cover Instances with Molecular-Motor-Powered Network-Based Biocomputation

Publikation: Beitrag in FachzeitschriftForschungsartikelBeigetragenBegutachtung


  • Pradheebha Surendiran - , Lund University (Autor:in)
  • Christoph Robert Meinecke - , Technische Universität Chemnitz (Autor:in)
  • Aseem Salhotra - , Linnaeus University (Autor:in)
  • Georg Heldt - , Linnaeus University (Autor:in)
  • Jingyuan Zhu - , Lund University (Autor:in)
  • Alf Månsson - , Linnaeus University (Autor:in)
  • Stefan Diez - , Professur für BioNano-Werkzeuge, Exzellenzcluster PoL: Physik des Lebens, Max Planck Institute of Molecular Cell Biology and Genetics (Autor:in)
  • Danny Reuter - , Technische Universität Chemnitz, Fraunhofer Institute for Electronic Nano Systems (Autor:in)
  • Hillel Kugler - , Bar-Ilan University (Autor:in)
  • Heiner Linke - , Lund University (Autor:in)
  • Till Korten - , Professur für BioNano-Werkzeuge (Autor:in)


Information processing by traditional, serial electronic processors consumes an ever-increasing part of the global electricity supply. An alternative, highly energy efficient, parallel computing paradigm is network-based biocomputation (NBC). In NBC a given combinatorial problem is encoded into a nanofabricated, modular network. Parallel exploration of the network by a very large number of independent molecular-motor-propelled protein filaments solves the encoded problem. Here we demonstrate a significant scale-up of this technology by solving four instances of Exact Cover, a nondeterministic polynomial time (NP) complete problem with applications in resource scheduling. The difficulty of the largest instances solved here is 128 times greater in comparison to the current state of the art for NBC.


Seiten (von - bis)396-403
Fachzeitschrift ACS nanoscience Au : an open access journal of the American Chemical Society
PublikationsstatusVeröffentlicht - 23 Juni 2022

Externe IDs

unpaywall 10.1021/acsnanoscienceau.2c00013
PubMed 36281252
ORCID /0000-0002-0750-8515/work/142235522


Forschungsprofillinien der TU Dresden


  • biocomputation, biofunctionalization, computational nanotechnology, molecular motors, nanobiotechnology, parallel computing