Rigid Geometric Constraints for Kappa Models

AbstractRule-based modeling languages such as Kappa [Danos, V. and C. Laneve, Formal molecular biology, Theor. Comput. Sci. 325 (2004), pp. 69–110, Danos, V., J. Feret, W. Fontana, R. Harmer and J. Krivine, Rule-based modelling of cellular signalling, in: L. Caires and V. Vasconcelos, editors, Proceedings of the Eighteenth International Conference on Concurrency Theory (CONCUR07), Lecture Notes in Computer Science 4703 (2007), pp. 17–41, available at http://www.pps.univ-paris-diderot.fr/~danos/pdf/ka-fix.pdf] and BNGL [Blinov, M. L., J. R. Faeder, B. Goldstein and W. S. Hlavacek, Bionetgen: software for rule-based modeling of signal transduction based on the interactions of molecular domains, Bioinformatics 20 (2004), pp. 3289–3291. URL http://bioinformatics.oxfordjournals.org/content/20/17/3289.abstract, Blinov, M., J. Yang, J. Faeder and W. Hlavacek, Graph theory for rule-based modeling of biochemical networks, in: C. Priami, A. Ingólfsdóttir, B. Mishra and H. Riis Nielson, editors, Transactions on Computational Systems Biology VII, Lecture Notes in Computer Science 4230, Springer Berlin/Heidelberg, 2006 pp. 89–106. URL http://dx.doi.org/10.1007/11905455_5] allow for a concise description of combinatorially complex biochemical processes as well as efficient simulations of the resulting models [Danos, V., J. Feret, W. Fontana and J. Krivine, Scalable simulation of cellular signaling networks, invited paper, in: Z. Shao, editor, Proceedings of the Fifth Asian Symposium on Programming Systems, APLAS2007, Singapore, Lecture Notes in Computer Science 4807 (2007), pp. 139–157, available at http://www.pps.univ-paris-diderot.fr/~danos/pdf/scalability.pdf, Danos, V., J. Feret, W. Fontana, R. Harmer and J. Krivine, Rule-based modelling of cellular signalling, in: L. Caires and V. Vasconcelos, editors, Proceedings of the Eighteenth International Conference on Concurrency Theory (CONCUR07), Lecture Notes in Computer Science 4703 (2007), pp. 17–41, available at http://www.pps.univ-paris-diderot.fr/~danos/pdf/ka-fix.pdf]. A key aspect of the rule-based modeling approach is to partially expose the structure of the chemical species involved. However, the above-mentioned languages do not provide means to directly express the three-dimensional geometry of chemical species. As a consequence models typically capture only the network-topological structure of the species involved. For certain biochemical processes, such as the assembly of molecular complexes, in which steric constraints play a key role, it would seem natural to also model the geometric structure of species. We propose an extension to the Kappa modeling language allowing the annotation of the structure of chemical species with three-dimensional geometric information. This naturally introduces rigidity constraints on the species and reduces the state space of the resulting model by excluding species that are not geometrically sound. We show that models extended in this way can still be simulated efficiently, albeit at the cost of a greater number of null-events occurring during the simulation. The geometric constraints introduced by the extension are inherently non-local in that they may entangle the position and orientation of sub-structures at arbitrary distances in large species such as polymers. We give a formal definition of the notion of locality based on the intuition that local modifications should only affect sub-structures within a finite radius around the point where the modification occurred. We show that there are indeed geometrically enhanced Kappa models that are non-local, and conversely, that every local model can be simulated accurately using a finite classical Kappa model at the expense of a possible combinatorial explosion of its rule set. We also give some sufficient conditions for the locality of a model but show that locality is undecidable in general