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

被引：6

作者：

Surendiran, Pradheebha ^{[1
]}

Meinecke, Christoph Robert ^{[2
]}

Salhotra, Aseem ^{[3
]}

Heldt, Georg ^{[3
]}

Zhu, Jingyuan ^{[1
]}

Mansson, Alf ^{[3
]}

Diez, Stefan ^{[4
,5
,6
]}

Reuter, Danny ^{[2
,7
]}

Kugler, Hillel ^{[8
]}

Linke, Heiner ^{[1
]}

Korten, Till ^{[4
]}

机构：

[1] Lund Univ, NanoLund & Solid State Phys, SE-22100 Lund, Sweden

[2] Tech Univ Chemnitz, Ctr Microtechnol, D-09126 Chemnitz, Germany

[3] Linnaeus Univ, Dept Chem & Biomed Sci, SE-39231 Kalmar, Sweden

[4] Tech Univ Dresden, B CUBE Ctr Mol Bioengn, D-01307 Dresden, Germany

[5] Tech Univ Dresden, Cluster Excellence Phys Life, D-01307 Dresden, Germany

[6] Max Planck Inst Mol Cell Biol & Genet, D-01307 Dresden, Germany

[7] Fraunhofer Inst Elect Nano Syst ENAS, D-09126 Chemnitz, Germany

[8] Bar Ilan Univ, Fac Engn, IL-5290002 Ramat Gan, Israel

来源：

ACS NANOSCIENCE AU | 2022年 / 2卷 / 05期

关键词：

parallel computing; computational nanotechnology; molecular motors; biocomputation; nanobiotechnology; biofunctionalization;

D O I：

10.1021/acsnanoscienceau.2c00013

中图分类号：

TB3 [工程材料学];

学科分类号：

0805 ; 080502 ;

摘要：

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 nano-fabricated, 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.

引用

页码：396 / 403

页数：8

共 28 条

[1]

Andrae ASG., 2015, J. Challenges, V6, P1, DOI [DOI 10.3390/CHALLE6010117, 10.3390/CHALLE6010117]

[2]

Arden W., White Paper

[3] Improved Success Probability with Greater Circuit Depth for the Quantum Approximate Optimization Algorithm [J].

Bengtsson, Andreas ;

Vikstal, Pontus ;

Warren, Christopher ;

Svensson, Marika ;

Gu, Xiu ;

Kockum, Anton Frisk ;

Krantz, Philip ;

Krizan, Christian ;

Shiri, Daryoush ;

Svensson, Ida-Maria ;

Tancredi, Giovanna ;

Johansson, Goran ;

Delsing, Per ;

Ferrini, Giulia ;

Bylander, Jonas .

PHYSICAL REVIEW APPLIED, 2020, 14 (03)

[4]

Chabert M, 2020, J ARTIF INTELL RES, V67, P509

[5] An Exact Cover-Based Approach For Service Composition [J].

Cheikh, B. A. .

2016 IEEE INTERNATIONAL CONFERENCE ON WEB SERVICES (ICWS), 2016, :631-636

[6]

Colbourn C., 2007, HDB COMBINATORIAL DE

[7]

creativecommons, Creative Commons -Attribution 4.0 International -CC BY 4.0

[8]

Garey M. R., 1979, Computers and intractability. A guide to the theory of NP-completeness

[9] Kinesin's processivity results from mechanical and chemical coordination between the ATP hydrolysis cycles of the two motor domains [J].

Hancock, WO ;

Howard, J .

PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA, 1999, 96 (23) :13147-13152

[10] MOVEMENT OF MICROTUBULES BY SINGLE KINESIN MOLECULES [J].

HOWARD, J ;

HUDSPETH, AJ ;

VALE, RD .

NATURE, 1989, 342 (6246) :154-158

← 1 2 3 →