Skip to Main content Skip to Navigation
Conference papers

Proving the absence of unbounded polymers in rule-based models

Abstract : Rule-based languages, such as Kappa and BNGL, allow for the description of very combinatorial models of interactions between proteins. A huge (when not infinite) number of different kinds of bio-molecular compounds may arise due to proteins with multiple binding and phosphorylation sites. Knowing beforehand whether a model may involve an infinite number of different kinds of bio-molecular compounds is crucial for the modeller. On the first hand, having an infinite number of kinds of bio-molecular compounds is sometimes a hint for modelling flaws: forgetting to specify the conflicts among binding rules is a common mistake. On the second hand, it impacts the choice of the semantics for the models (among stochastic, differential, hybrid). In this paper, we introduce a data-structure to abstract the potential unbounded polymers that may be formed in a rule-based model. This data-structure is a graph, the nodes and the edges of which are labelled with patterns. By construction, every potentially unbounded polymer is associated to at least one cycle in that graph. This data-structure has two main advantages. Firstly, as opposed to site-graphs, one can reason about cycles without enumerating them (by the means of Tarjan's algorithm for detecting strongly connected components). Secondly, this data-structures may be combined easily with information coming from additional reachability analysis: the edges that are labelled with an overlap that is proved unreachable in the model may be safely discarded.
Document type :
Conference papers
Complete list of metadata

Cited literature [18 references]  Display  Hide  Download
Contributor : Jérôme Feret Connect in order to contact the contributor
Submitted on : Tuesday, January 1, 2019 - 6:30:57 AM
Last modification on : Wednesday, June 8, 2022 - 12:50:03 PM
Long-term archiving on: : Tuesday, April 2, 2019 - 3:55:03 PM


Files produced by the author(s)


  • HAL Id : hal-01967632, version 1



Pierre Boutillier, Jérôme Feret, Aurélie Faure de Pebeyre. Proving the absence of unbounded polymers in rule-based models. Static Analysis and Systems Biology 2018, Aug 2018, Freiburg im Breisgau, Germany. ⟨hal-01967632⟩



Record views


Files downloads