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

↓ Direkt till sidans innehåll
↓ Direkt till sidans sekundära innehåll (sidomenyn)

Sökning: WFRF:(Korten V.) > Design of network-b...

Korten, TillDresden University of Technology (författare)

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

Artikel/kapitelEngelska2021

Förlag, utgivningsår, omfång ...

2021-08-12
IOP Publishing,2021

Nummerbeteckningar

LIBRIS-ID:oai:lup.lub.lu.se:591de30a-6dad-428a-b840-160893bdf89e
https://lup.lub.lu.se/record/591de30a-6dad-428a-b840-160893bdf89eURI
https://doi.org/10.1088/1367-2630/ac175dDOI

Kompletterande språkuppgifter

Språk:engelska
Sammanfattning på:engelska

Ingår i deldatabas

SwePubSwePub

Klassifikation

Ämneskategori:art swepub-publicationtype
Ämneskategori:ref swepub-contenttype

Anmärkningar

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.

Ämnesord och genrebeteckningar

NATURVETENSKAP Biologi Biofysik hsv//swe
NATURAL SCIENCES Biological Sciences Biophysics hsv//eng
TEKNIK OCH TEKNOLOGIER Elektroteknik och elektronik Datorsystem hsv//swe
ENGINEERING AND TECHNOLOGY Electrical Engineering, Electronic Engineering, Information Engineering Computer Systems hsv//eng
NATURVETENSKAP Fysik Annan fysik hsv//swe
NATURAL SCIENCES Physical Sciences Other Physics Topics hsv//eng
Biological computation
Exact cover
Network based biocomputation
NP-complete problems

Biuppslag (personer, institutioner, konferenser, titlar ...)

Diez, StefanDresden University of Technology,Max Planck Institute of Molecular Cell Biology and Genetics (författare)
Linke, HeinerLund University,Lunds universitet,NanoLund: Centre for Nanoscience,Annan verksamhet, LTH,Lunds Tekniska Högskola,Fasta tillståndets fysik,Fysiska institutionen,Institutioner vid LTH,Other operations, LTH,Faculty of Engineering, LTH,Solid State Physics,Department of Physics,Departments at LTH,Faculty of Engineering, LTH(Swepub:lu)ftf-hle (författare)
Nicolau, Jr., Dan V.Queensland University of Technology (författare)
Kugler, HillelBar-Ilan University (författare)
Dresden University of TechnologyMax Planck Institute of Molecular Cell Biology and Genetics (creator_code:org_t)

Sammanhörande titlar

Ingår i:New Journal of Physics: IOP Publishing23:81367-2630

Internetlänk

Hitta via bibliotek

New Journal of Physics (Sök värdpublikationen i LIBRIS)

Till lärosätets databas

Hitta mer i SwePub

Av författaren/redakt...: Korten, Till; Diez, Stefan; Linke, Heiner; Nicolau, Jr., Da ...; Kugler, Hillel

Om ämnet

NATURVETENSKAP: NATURVETENSKAP; och Biologi; och Biofysik

TEKNIK OCH TEKNOLOGIER: TEKNIK OCH TEKNO ...; och Elektroteknik oc ...; och Datorsystem

NATURVETENSKAP: NATURVETENSKAP; och Fysik; och Annan fysik

Artiklar i publikationen: New Journal of P ...

Av lärosätet: Lunds universitet

Sök utanför SwePub

Sök vidare i:: Google; Google Book Search; Google Scholar

Kungliga biblioteket hanterar dina personuppgifter i enlighet med EU:s dataskyddsförordning (2018), GDPR. Läs mer om hur det funkar här.
Så här hanterar KB dina uppgifter vid användning av denna tjänst.

LIBRIS.kb.se