about this paper

presentation abstract bibitem


slides paper editor link
Vincent Danos, Jérôme Feret, Walter Fontana, and Jean Krivine.
Abstract Interpretation of Cellular Signalling Networks.

In Proceedings of the Ninth International Conference on Verification, Model Checking and Abstract Interpretation, VMCAI'08. San Francisco, USA, January 7--9, 2008, F. Logozzo, D.A. Peled, and L.D. Zuck (Ed.), Lecture Notes in Computer Science 4905, pp 83--97.
© Springer, Berlin, Germany.

Abstract: Biological signalling networks can be described neatly in a language where agents bind and modify their internal states according to some specified rules. However, natural rule sets generate concurrent transition systems (or stochastic ones, given rates for rules), which are large (many agents are involved) and high dimensional (the number of non-isomorphic ways in which agents can connect is high or even infinite), so that even simple tasks such as simulation are costly.
We develop here an abstract interpretation of those networks, based on the natural notion of an agent {view}, which leads, among other things, to an efficient computation of a superset of the system dimensions. We show this superset is the exact one, ie not just a superset, iff the latter is closed under {swap} (an operation whereby pairs of edges of the same type can permute their ends).
That property can be taken as the definition of a {local} signalling network, a rather strong constraint which is implied by a simple syntactic restriction on rules. Suprisingly we can show that two substantial examples - the EGF/FGF receptors early response pathways - verify that syntactic condition (up to some transformations), and therefore despite their apparent complexity fall within the class of local networks.

   author =    {Vincent Danos and J\'er\^ome Feret and Walter Fontana and Jean Krivine},
   title =     {Abstract interpretation of cellular signalling networks},
   editor =    {Francesco Logozzo and Doron A.\ Peled and Lenore D.\ Zuck},
   booktitle = {Proceedings of the Ninth International Conference on Verification, Model Checking and Abstract Interpretation, VMCAI$\,$'2008},
   address =   {San Francisco, USA},
   series =    {Lecture Notes in Computer Science},
   volume =    {4905},
   publisher = {Springer, Berlin, Germany},
   pages =     {83--97},
   month =     {7--9 January},
   year =      {2008},