Design of network-based biocomputation circuits for the exact cover problem
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 cardinali...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IOP Publishing
2021-01-01
|
| Series: | New Journal of Physics |
| Subjects: | |
| Online Access: | https://doi.org/10.1088/1367-2630/ac175d |
| _version_ | 1797750114873245696 |
|---|---|
| author | Till Korten Stefan Diez Heiner Linke Dan V Nicolau Jr Hillel Kugler |
| author_facet | Till Korten Stefan Diez Heiner Linke Dan V Nicolau Jr Hillel Kugler |
| author_sort | Till Korten |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-03-12T16:29:00Z |
| format | Article |
| id | doaj.art-f17d1c4e9c1441618fbbaa0dbdba4ae1 |
| institution | Directory Open Access Journal |
| issn | 1367-2630 |
| language | English |
| last_indexed | 2024-03-12T16:29:00Z |
| publishDate | 2021-01-01 |
| publisher | IOP Publishing |
| record_format | Article |
| series | New Journal of Physics |
| spelling | doaj.art-f17d1c4e9c1441618fbbaa0dbdba4ae12023-08-08T15:37:50ZengIOP PublishingNew Journal of Physics1367-26302021-01-0123808500410.1088/1367-2630/ac175dDesign of network-based biocomputation circuits for the exact cover problemTill Korten0Stefan Diez1https://orcid.org/0000-0002-0750-8515Heiner Linke2https://orcid.org/0000-0003-4451-4006Dan V Nicolau Jr3Hillel Kugler4https://orcid.org/0000-0001-7924-5665B CUBE - Center for Molecular Bioengineering, Technische Universität Dresden , D-01307 Dresden, GermanyB CUBE - Center for Molecular Bioengineering, Technische Universität Dresden , D-01307 Dresden, Germany; Max Planck Institute of Molecular Cell Biologiy and Genetics , D-01307 Dresden, GermanyNanoLund and Solid State Physics, Lund University , Box 118, S-22100 Lund, SwedenSchool of Mathematical Sciences, and ARC Centre of Excellence for Mathematical and Statistical Frontiers, Queensland University of Technology , Gardens Point, Brisbane, Qld, AustraliaFaculty of Engineering, Bar-Ilan University , Ramat Gan, IsraelExact 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.https://doi.org/10.1088/1367-2630/ac175dnetwork based biocomputationNP-complete problemsexact coverbiological computation |
| spellingShingle | Till Korten Stefan Diez Heiner Linke Dan V Nicolau Jr Hillel Kugler Design of network-based biocomputation circuits for the exact cover problem New Journal of Physics network based biocomputation NP-complete problems exact cover biological computation |
| title | Design of network-based biocomputation circuits for the exact cover problem |
| title_full | Design of network-based biocomputation circuits for the exact cover problem |
| title_fullStr | Design of network-based biocomputation circuits for the exact cover problem |
| title_full_unstemmed | Design of network-based biocomputation circuits for the exact cover problem |
| title_short | Design of network-based biocomputation circuits for the exact cover problem |
| title_sort | design of network based biocomputation circuits for the exact cover problem |
| topic | network based biocomputation NP-complete problems exact cover biological computation |
| url | https://doi.org/10.1088/1367-2630/ac175d |
| work_keys_str_mv | AT tillkorten designofnetworkbasedbiocomputationcircuitsfortheexactcoverproblem AT stefandiez designofnetworkbasedbiocomputationcircuitsfortheexactcoverproblem AT heinerlinke designofnetworkbasedbiocomputationcircuitsfortheexactcoverproblem AT danvnicolaujr designofnetworkbasedbiocomputationcircuitsfortheexactcoverproblem AT hillelkugler designofnetworkbasedbiocomputationcircuitsfortheexactcoverproblem |