Stochastic Concurrent Constraint Programming

Stochastic Concurrent Constraint Programming (sCCP, [1,2,3]) is a stochastic variant of CCP, a process algebra in which agents interact asynchronously exchanging information, encoded as constraints, through a shared memory, the constraint store.

The characterizing features of sCCP, as a a stochastic modeling language, are:

  • The stochastic duration is given in terms of functional rates (depending on the state of the store).
  • Constraints can be used easily to program complex behaviors.

These features have been exploited to model a wide variety of biological systems: simple biochemical and genetic networks [5], tumour growth [4], biochemical networks described by Molecular Interaction Maps [6], spatial structures [7] and even the folding of a protein [1,2].

More recently, we focused our attention on approximating the stochastic behavior of sCCP programs.

First, we studied fluid-flow approximation techniques, associating a set of ODEs to sCCP ([8], [10]). In [9] we proved that with our technique we obtain a first-order approximation of the equation for the average of the stochastic system.

This method, however, can be troublesome when the model has inherently discrete states, like a gene with more than one inner state (states are described in ODEs by continuous variables). In these cases, we found more natural an approximation based on hybrid automata, dynamical systems mixing discrete and continuous behavior ([11],[12]), extended in [4] to deal with immediate events. This approximation can be formally justified in terms of mean field limits [17,18].

 

Bibliography

  1. L. Bortolussi. Computational Systems Biology With Constraints. Stochastic modeling of biological systems with concurrent constraint programming. ISBN: 978-3-639-08875-5. VDM Verlag Dr. Mueller e.K., Germany, 2008.
  2. L. Bortolussi. Constraint-based approaches to stochastic dynamics of biological systems, University of Udine PhD Thesis Series, CS2007/1. Supervisor: A. Dovier.
sCCP
  1. L. Bortolussi. Stochastic Concurrent Constraint Programming. Proceedings of 4th International Workshop of Quantitative Aspects of Programming Languages, QAPL 2006, ENTCS 164-3, Wien, Austria, April 2006.
Modeling Biological Systems in sCCP
  1. L. Bortolussi and A. Policriti. Studying cancer-cell populations by programmable models of networks. Network Model Analysis in Health Informatics and Bioinformatics, 1:117-133, 2012.
  2. L. Bortolussi and A. Policriti. Modeling Biological Systems in Stochastic Concurrent Constraint Programming, Constraints, pag. 66-90, Vol 13(1), 2008.
  3. L. Bortolussi, S. Fonda, and A. Policriti. Constraint-based simulation of biological systems described by Molecular Interaction Maps. Proceedings of IEEE conference on Bioinformatics and Biomedicine, BIBM 2007, Silicon Valley, USA, November 2007.
  4. L. Bortolussi, A. Policriti.  2009.  Tales of Spatiality in stochastic Concurrent Constraint Programming. Bio Logical 2009. 
Approximating sCCP with ODEs
  1. L. Bortolussi and A. Policriti. Stochastic Concurrent Constraint Programming and Differential Equations, Proceeding of 5th International Workshop of Quantitative Aspects of Programming Languages, QAPL 2007, ENTCS 16713, Braga, Portugal, March 2007.
  2. L. Bortolussi. On the Approximation of Stochastic Concurrent Constraint Programming by Master Equation. Proceeding of the Sixth Workshop on Quantitative Aspects of Programming Languages, QAPL 2008, Budapest, Hungary, March 2008.
  3. L. Bortolussi and A. Policriti. Dynamical Systems and Stochastic Programming - To Ordinary Differential Equations and Back. Transactions of Computational Systems Biology, 11:216–267.
Approximating sCCP with Hybrid Automata
  1. L. Bortolussi and A. Policriti. (Hybrid) Automata and (Stochastic) Programs. The hybrid automata lattice of a stochastic program. Journal of Logic and Computation, online first.
  2. L. Bortolussi, A. Policriti. Hybrid dynamics of stochastic programs. Theoretical Computer Science, vol. 411(20), 2010,
  3. L. Bortolussi and A. Policriti. Hybrid approximation of stochastic process algebras for systems biology. Proceedings of the 17th IFAC World Congress, Seoul, South Korea, July 2008.
  4. L. Bortolussi and A. Policriti. The importance of being (a little bit) discrete. Proceedings of the 2nd International Workshop "From Biology to Concurrency and back", FBTC 2008, Reykjavik, Iceland, July 2008.
  5. L.Bortolussi and A. Policriti. Stochastic Programs and Hybrid Automata for (Biological) Modeling. Proceeding of CiE 2009 (Computability in Europe), Heidelberg, Germany. 
  6. L. Bortolussi and A. Policriti. Hybrid Semantics of Stochastic Programs with Dynamic Reconfiguration. Proceedings of CompMod 2011, Eindhoven, Netherlands. 
Hybrid Mean Field
  1. L. Bortolussi. Hybrid Behaviour of Markov Population Models. CoRR abs/1211.1643, 2012 
  2. L. Bortolussi.  Limit behavior of the hybrid approximation of Stochastic Process Algebras. Proceedings of ASMTA 2010.
Related work
  1. L. Bortolussi and A. Policriti. Hybrid Semantics for Stochastic pi-calculus. Proceedings of 3rd International Conference on Algebraic Biology, AB 2008, pag. 40-57, LNCS  5147, Springer-Verlag.
  2. L. Bortolussi, A. Policriti. Hybrid Dynamics of Stochastic pi-calculus. Mathematics In Computer Science. 2:465–491, 2009
  3. L. Bortolussi, A. Policriti. Hybrid Systems and Biology.Continuous and Discrete Modeling for Systems Biology. Formal Methods For Computational System Biology. 5016:424–448, 2008