Skip to Main content Skip to Navigation
Journal articles

Invariants and Other Structural Properties of Biochemical Models as a Constraint Satisfaction Problem

Sylvain Soliman 1, *
* Corresponding author
1 CONTRAINTES - Constraint programming
Inria Paris-Rocquencourt
Abstract : Background
We present a way to compute the minimal semi-positive invariants of a Petri net representing a biological reaction system, as resolution of a Constraint Satisfaction Problem. The use of Petri nets to manipulate Systems Biology models and make available a variety of tools is quite old, and recently analyses based on invariant computation for biological models have become more and more frequent, for instance in the context of module decomposition.
In our case, this analysis brings both qualitative and quantitative information on the models, in the form of conservation laws, consistency checking, etc. thanks to finite domain constraint programming. It is noticeable that some of the most recent optimizations of standard invariant computation techniques in Petri nets correspond to well-known techniques in constraint solving, like symmetry-breaking. Moreover, we show that the simple and natural encoding proposed is not only efficient but also flexible enough to encompass sub/sur-invariants, siphons/traps, etc., i.e., other Petri net structural properties that lead to supplementary insight on the dynamics of the biochemical system under study.
A simple implementation based on GNU-Prolog's finite domain solver, and including symmetry detection and breaking, was incorporated into the BIOCHAM modelling environment and in the independent tool Nicotine. Some illustrative examples and benchmarks are provided.
Document type :
Journal articles
Complete list of metadatas

Cited literature [31 references]  Display  Hide  Download
Contributor : Ed. Bmc <>
Submitted on : Monday, February 4, 2013 - 1:00:55 PM
Last modification on : Monday, September 24, 2018 - 2:00:04 PM
Document(s) archivé(s) le : Monday, June 17, 2013 - 6:37:16 PM





Sylvain Soliman. Invariants and Other Structural Properties of Biochemical Models as a Constraint Satisfaction Problem. Algorithms for Molecular Biology, BioMed Central, 2012, 7 (1), pp.15. ⟨10.1186/1748-7188-7-15⟩. ⟨hal-00784404⟩



Record views


Files downloads