Dataset Information

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

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 greater in comparison to the current state of the art for NBC.

SUBMITTER: Surendiran P

PROVIDER: S-EPMC9585575 | biostudies-literature | 2022 Oct

REPOSITORIES: biostudies-literature

ACCESS DATA

Publications

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

Surendiran Pradheebha P Meinecke Christoph Robert CR Salhotra Aseem A Heldt Georg G Zhu Jingyuan J Månsson Alf A Diez Stefan S Reuter Danny D Kugler Hillel H Linke Heiner H Korten Till T

ACS nanoscience Au 20220623 5

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 s ...[more]

PMID: 36281252

Similar Datasets

Project description:BackgroundSolutions to stochastic Boolean models are usually estimated by Monte Carlo simulations, but as the state space of these models can be enormous, there is an inherent uncertainty about the accuracy of Monte Carlo estimates and whether simulations have reached all attractors. Moreover, these models have timescale parameters (transition rates) that the probability values of stationary solutions depend on in complex ways, raising the necessity of parameter sensitivity analysis. We address these two issues by an exact calculation method for this class of models.ResultsWe show that the stationary probability values of the attractors of stochastic (asynchronous) continuous time Boolean models can be exactly calculated. The calculation does not require Monte Carlo simulations, instead it uses graph theoretical and matrix calculation methods previously applied in the context of chemical kinetics. In this version of the asynchronous updating framework the states of a logical model define a continuous time Markov chain and for a given initial condition the stationary solution is fully defined by the right and left nullspace of the master equation's kinetic matrix. We use topological sorting of the state transition graph and the dependencies between the nullspaces and the kinetic matrix to derive the stationary solution without simulations. We apply this calculation to several published Boolean models to analyze the under-explored question of the effect of transition rates on the stationary solutions and show they can be sensitive to parameter changes. The analysis distinguishes processes robust or, alternatively, sensitive to parameter values, providing both methodological and biological insights.ConclusionUp to an intermediate size (the biggest model analyzed is 23 nodes) stochastic Boolean models can be efficiently solved by an exact matrix method, without using Monte Carlo simulations. Sensitivity analysis with respect to the model's timescale parameters often reveals a small subset of all parameters that primarily determine the stationary probability of attractor states.

Dataset Information

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

Publications

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

Similar Datasets

OmicsDI is part of the ELIXIR infrastructure

Tweets