Boolean constraint satisfaction problems for reaction networks
arXiv:1306.2480 · doi:10.1088/1742-5468/2013/09/P09009
Abstract
We define and study a class of (random) Boolean constraint satisfaction problems representing minimal feasibility constraints for networks of chemical reactions. The constraints we consider encode, respectively, for hard mass-balance conditions (where the consumption and production fluxes of each chemical species are matched) and for soft mass-balance conditions (where a net production of compounds is in principle allowed). We solve these constraint satisfaction problems under the Bethe approximation and derive the corresponding Belief Propagation equations, that involve 8 different messages. The statistical properties of ensembles of random problems are studied via the population dynamics methods. By varying a chemical potential attached to the activity of reactions, we find first order transitions and strong hysteresis, suggesting a non-trivial structure in the space of feasible solutions.
16 pages (incl. appendix)
References in corpus (6)
- Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
- Clusters of solutions and replica symmetry breaking in random k-satisfiability
- Spontaneous Reaction Silencing in Metabolic Optimization
- Identifying essential genes in E. coli from a metabolic optimization principle
- Von Neumann's expanding model on random graphs
- Propagation of external regulation and asynchronous dynamics in random Boolean networks