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.
Results
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.
Conclusions
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

https://hal.inria.fr/hal-00784404
Contributor : Ed. Bmc <>
Submitted on : Monday, February 4, 2013 - 1:00:55 PM
Last modification on : Monday, September 24, 2018 - 2:00:04 PM
Long-term archiving on : Monday, June 17, 2013 - 6:37:16 PM

Files

1748-7188-7-15.pdf
Publisher files allowed on an open archive

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

465

Files downloads

223