Computing properties of stable configurations of thermodynamic binding networks

DOI10.1016/J.TCS.2018.10.027MaRDI QIDQ2315010zbMATH OpenOpenAlexWikidataFDO

Authors Keenan Breik, Chris Thachuk, Marijn J. H. Heule, David Soloveichik

Publication date 31 July 2019

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1709.08731

zbMATH Keywords

hardness of approximationchemical computationreduction to SAT

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Kinetics in biochemical problems (pharmacokinetics, enzyme kinetics, etc.) (92C45)

Abstract: The promise of chemical computation lies in controlling systems incompatible with traditional electronic micro-controllers, with applications in synthetic biology and nano-scale manufacturing. Computation is typically embedded in kinetics---the specific time evolution of a chemical system. However, if the desired output is not thermodynamically stable, basic physical chemistry dictates that thermodynamic forces will drive the system toward error throughout the computation. The thermodynamic binding network (TBN) model was introduced to formally study how the thermodynamic equilibrium can be made consistent with the desired computation, and it idealizes tradeoffs between configurational entropy and binding. Here we prove the computational hardness of natural questions about TBNs and develop a practical algorithm for verifying the correctness of constructions by translating the problem into propositional logic and solving the resulting formula. The TBN model together with automated verification tools will help inform strategies for error reduction in molecular computing, including the extensively studied models of strand displacement cascades and algorithmic tile assembly.

Recommendations

• Thermodynamic binding networks
• Thermodynamically favorable computation via tile self-assembly
• Automated Design and Verification of Localized DNA Computation Circuits
• Computation with finite stochastic chemical reaction networks
• Probability 1 computation with chemical reaction networks

Cites work

• scientific article; zbMATH DE number 1796153 (Why is no real title available?)
• A Richer Understanding of the Complexity of Election Systems
• Bounded model checking using satisfiability solving
• Efficient SAT-based bounded model checking for software verification
• Leakless DNA strand displacement systems
• On stoichiometry for the assembly of flexible tile DNA complexes
• Programmable control of nucleation for algorithmic self-assembly
• Programming substrate-independent kinetic barriers with thermodynamic binding networks
• Theory and Applications of Satisfiability Testing
• Thermodynamic binding networks
• Thermodynamically favorable computation via tile self-assembly
• Towards an Optimal CNF Encoding of Boolean Cardinality Constraints
• \(P^{NP[O(\log n)]}\) and sparse turing-complete sets for NP

Cited in

(7)

• Formal semantics and verification of network-based biocomputation circuits
• Computing the Minimal Rebinding Effect Included in a Given Kinetics
• Performance limits and trade-offs in entropy-driven biochemical computers
• Programming substrate-independent kinetic barriers with thermodynamic binding networks
• Thermodynamically favorable computation via tile self-assembly
• Thermodynamic binding networks
• Computing properties of thermodynamic binding networks: an integer programming approach

Describes a project that uses

Uses Software

• MiniSat

This page was built for publication: Computing properties of stable configurations of thermodynamic binding networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2315010)