Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Design of network-based biocomputation circuits for the exact cover problem

Korten, Till ; Diez, Stefan ; Linke, Heiner LU orcid ; Nicolau, Jr., Dan V. and Kugler, Hillel (2021) In New Journal of Physics 23(8).
Abstract

Exact cover is a non-deterministic polynomial time (NP)-complete problem that is central to optimization challenges such as airline fleet planning and allocation of cloud computing resources. Solving exact cover requires the exploration of a solution space that increases exponentially with cardinality. Hence, it is time- and energy consuming to solve large instances of exact cover by serial computers. One approach to address these challenges is to utilize the inherent parallelism and high energy efficiency of biological systems in a network-based biocomputation (NBC) device. NBC is a parallel computing paradigm in which a given combinatorial problem is encoded into a graphical, modular network that is embedded in a nanofabricated planar... (More)

Exact cover is a non-deterministic polynomial time (NP)-complete problem that is central to optimization challenges such as airline fleet planning and allocation of cloud computing resources. Solving exact cover requires the exploration of a solution space that increases exponentially with cardinality. Hence, it is time- and energy consuming to solve large instances of exact cover by serial computers. One approach to address these challenges is to utilize the inherent parallelism and high energy efficiency of biological systems in a network-based biocomputation (NBC) device. NBC is a parallel computing paradigm in which a given combinatorial problem is encoded into a graphical, modular network that is embedded in a nanofabricated planar device. The network is then explored in parallel using a large number of biological agents, such as molecular-motor-propelled protein filaments. The answer to the combinatorial problem can then be inferred by measuring the positions through which the agents exit the network. Here, we (i) show how exact cover can be encoded and solved in an NBC device, (ii) define a formalization that allows to prove the correctness of our approach and provides a mathematical basis for further studying NBC, and (iii) demonstrate various optimizations that significantly improve the computing performance of NBC. This work lays the ground for fabricating and scaling NBC devices to solve significantly larger combinatorial problems than have been demonstrated so far.

(Less)
Please use this url to cite or link to this publication:
author
; ; ; and
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
Biological computation, Exact cover, Network based biocomputation, NP-complete problems
in
New Journal of Physics
volume
23
issue
8
article number
085004
publisher
IOP Publishing
external identifiers
  • scopus:85113336642
ISSN
1367-2630
DOI
10.1088/1367-2630/ac175d
language
English
LU publication?
yes
additional info
Publisher Copyright: © 2021 The Author(s).
id
591de30a-6dad-428a-b840-160893bdf89e
date added to LUP
2022-01-18 09:51:47
date last changed
2023-11-09 03:10:42
@article{591de30a-6dad-428a-b840-160893bdf89e,
  abstract     = {{<p>Exact cover is a non-deterministic polynomial time (NP)-complete problem that is central to optimization challenges such as airline fleet planning and allocation of cloud computing resources. Solving exact cover requires the exploration of a solution space that increases exponentially with cardinality. Hence, it is time- and energy consuming to solve large instances of exact cover by serial computers. One approach to address these challenges is to utilize the inherent parallelism and high energy efficiency of biological systems in a network-based biocomputation (NBC) device. NBC is a parallel computing paradigm in which a given combinatorial problem is encoded into a graphical, modular network that is embedded in a nanofabricated planar device. The network is then explored in parallel using a large number of biological agents, such as molecular-motor-propelled protein filaments. The answer to the combinatorial problem can then be inferred by measuring the positions through which the agents exit the network. Here, we (i) show how exact cover can be encoded and solved in an NBC device, (ii) define a formalization that allows to prove the correctness of our approach and provides a mathematical basis for further studying NBC, and (iii) demonstrate various optimizations that significantly improve the computing performance of NBC. This work lays the ground for fabricating and scaling NBC devices to solve significantly larger combinatorial problems than have been demonstrated so far.</p>}},
  author       = {{Korten, Till and Diez, Stefan and Linke, Heiner and Nicolau, Jr., Dan V. and Kugler, Hillel}},
  issn         = {{1367-2630}},
  keywords     = {{Biological computation; Exact cover; Network based biocomputation; NP-complete problems}},
  language     = {{eng}},
  number       = {{8}},
  publisher    = {{IOP Publishing}},
  series       = {{New Journal of Physics}},
  title        = {{Design of network-based biocomputation circuits for the exact cover problem}},
  url          = {{http://dx.doi.org/10.1088/1367-2630/ac175d}},
  doi          = {{10.1088/1367-2630/ac175d}},
  volume       = {{23}},
  year         = {{2021}},
}