Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

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

Surendiran, Pradheebha LU ; Meinecke, Christoph Robert ; Salhotra, Aseem ; Heldt, Georg ; Zhu, Jingyuan LU ; Månsson, Alf LU ; Diez, Stefan ; Reuter, Danny ; Kugler, Hillel and Linke, Heiner LU orcid , et al. (2022) In ACS Nanoscience AU 2(5). p.396-403
Abstract

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... (More)

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.

(Less)
Please use this url to cite or link to this publication:
author
; ; ; ; ; ; ; ; and , et al. (More)
; ; ; ; ; ; ; ; ; and (Less)
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
biocomputation, biofunctionalization, computational nanotechnology, molecular motors, nanobiotechnology, parallel computing
in
ACS Nanoscience AU
volume
2
issue
5
pages
396 - 403
publisher
The American Chemical Society (ACS)
external identifiers
  • pmid:36281252
  • scopus:85136696094
ISSN
2694-2496
DOI
10.1021/acsnanoscienceau.2c00013
language
English
LU publication?
yes
id
bbbe8e78-4a08-4c97-a734-be76dab19840
date added to LUP
2022-10-20 13:45:53
date last changed
2024-06-13 20:13:38
@article{bbbe8e78-4a08-4c97-a734-be76dab19840,
  abstract     = {{<p>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.</p>}},
  author       = {{Surendiran, Pradheebha and Meinecke, Christoph Robert and Salhotra, Aseem and Heldt, Georg and Zhu, Jingyuan and Månsson, Alf and Diez, Stefan and Reuter, Danny and Kugler, Hillel and Linke, Heiner and Korten, Till}},
  issn         = {{2694-2496}},
  keywords     = {{biocomputation; biofunctionalization; computational nanotechnology; molecular motors; nanobiotechnology; parallel computing}},
  language     = {{eng}},
  number       = {{5}},
  pages        = {{396--403}},
  publisher    = {{The American Chemical Society (ACS)}},
  series       = {{ACS Nanoscience AU}},
  title        = {{Solving Exact Cover Instances with Molecular-Motor-Powered Network-Based Biocomputation}},
  url          = {{http://dx.doi.org/10.1021/acsnanoscienceau.2c00013}},
  doi          = {{10.1021/acsnanoscienceau.2c00013}},
  volume       = {{2}},
  year         = {{2022}},
}