zbMATH — the first resource for mathematics

The attributed pi-calculus with priorities. (English) Zbl 1275.92023
Priami, Corrado (ed.) et al., Transactions on Computational Systems Biology XII. Special issue on modeling methodologies. Berlin: Springer (ISBN 978-3-642-11711-4/pbk). Lecture Notes in Computer Science 5945. Lecture Notes in Bioinformatics. Journal Subline, 13-76 (2010).
Summary: We present the attributed \(\pi \)-calculus for modeling concurrent systems with interaction constraints depending on the values of attributes of processes. The \(\lambda \)-calculus serves as a constraint language underlying the \(\pi \)-calculus. Interaction constraints subsume priorities, by which to express global aspects of populations. We present a non-deterministic and a stochastic semantics for the attributed \(\pi \)-calculus. We show how to encode the \(\pi \)-calculus with priorities and polyadic synchronization \(\pi \)@ and thus dynamic compartments, as well as the stochastic \(\pi \)-calculus with concurrent objects spico.
We illustrate the usefulness of the attributed \(\pi \)-calculus for modeling biological systems at two particular examples: Euglena’s spatial movement in phototaxis, and cooperative protein binding in gene regulation of bacteriophage lambda. Furthermore, population-based model is supported beside individual-based modeling. A stochastic simulation algorithm for the attributed \(\pi \)-calculus is derived from its stochastic semantics. We have implemented a simulator and present experimental results, that confirm the practical relevance of our approach.
For the entire collection see [Zbl 1204.92037].
Reviewer: Reviewer (Berlin)

92C42 Systems biology, networks
68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
Full Text: DOI
[1] Hillston, J.: Process algebras for quantitative analysis. In: Proceedings of 20th IEEE Symposium on Logic in Computer Science (LICS 2005), Chicago, IL, USA, June 26-29, pp. 239–248. IEEE Comp. Soc. Press, Los Alamitos (2005)
[2] Cardelli, L.: On process rate semantics. Theoretical Computer Science 391, 190–215 (2008) · Zbl 1133.68054 · doi:10.1016/j.tcs.2007.11.012
[3] Chabrier-Rivier, N., Fages, F., Soliman, S.: The Biochemical Abstract Machine BIOCHAM. In: Computational Methods in Systems Biology, pp. 172–191 (2004) · Zbl 1088.68817
[4] Regev, A.: Computational Systems Biology: A Calculus for Biomolecular Knowledge. Tel Aviv University, PhD thesis (2003)
[5] Regev, A., Shapiro, E.: Cells as Computation. Nature 419, 343 (2002) · doi:10.1038/419343a
[6] Gilbert, D., Heiner, M., Lehrack, S.: A unifying framework for modelling and analysing biochemical pathways using petri nets. In: Calder, M., Gilmore, S. (eds.) CMSB 2007. LNCS (LNBI), vol. 4695, pp. 200–216. Springer, Heidelberg (2007) · Zbl 05282355 · doi:10.1007/978-3-540-75140-3_14
[7] Danos, V., Feret, J., Fontana, W., Harmer, R., Krivine, J.: Rule-based modelling of cellular signalling. In: Caires, L., Vasconcelos, V.T. (eds.) CONCUR 2007. LNCS, vol. 4703, pp. 17–41. Springer, Heidelberg (2007) · Zbl 1151.68723 · doi:10.1007/978-3-540-74407-8_3
[8] Faeder, J.R., Blinov, M.L., Goldstein, B., Hlavacek, W.S.: Rule-Based Modeling of Biochemical Networks. Complexity 10, 22–41 (2005) · Zbl 05465914 · doi:10.1002/cplx.20074
[9] Krivine, J., Milner, R., Troina, A.: Stochastic bigraphs. In: 24th Conference on the Mathematical Foundations of Programming Semantics. Electronical notes in theoretical computer science, vol. 218, pp. 73–96. Elsevier, Amsterdam (2008) · Zbl 1286.68354
[10] Kuttler, C., Lhoussaine, C., Niehren, J.: A stochastic pi calculus for concurrent objects. In: Anai, H., Horimoto, K., Kutsia, T. (eds.) AB 2007. LNCS, vol. 4545, pp. 232–246. Springer, Heidelberg (2007) · Zbl 1126.92003 · doi:10.1007/978-3-540-73433-8_17
[11] Phillips, A., Cardelli, L.: Efficient, correct simulation of biological processes in the stochastic pi-calculus. In: Calder, M., Gilmore, S. (eds.) CMSB 2007. LNCS (LNBI), vol. 4695, pp. 184–199. Springer, Heidelberg (2007) · Zbl 05282354 · doi:10.1007/978-3-540-75140-3_13
[12] Priami, C., Regev, A., Shapiro, E., Silverman, W.: Application of a Stochastic Name-Passing Calculus to Representation and Simulation of Molecular Processes. Information Processing Letters 80, 25–31 (2001) · Zbl 0997.92018 · doi:10.1016/S0020-0190(01)00214-9
[13] Regev, A., Panina, E.M., Silverman, W., Cardelli, L., Shapiro, E.: BioAmbients: An Abstraction for Biological Compartments. TCS 325, 141–167 (2004) · Zbl 1069.68569 · doi:10.1016/j.tcs.2004.03.061
[14] Cardelli, L.: Brane calculi. In: Danos, V., Schachter, V. (eds.) CMSB 2004. LNCS (LNBI), vol. 3082, pp. 257–278. Springer, Heidelberg (2005) · Zbl 1088.68657 · doi:10.1007/978-3-540-25974-9_24
[15] Ciocchetta, F., Hillston, J.: Bio-PEPA: An Extension of the Process Algebra PEPA for Biochemical Networks. ENTCS 194, 103–117 (2008) · Zbl 1279.68254
[16] Bortolussi, L., Policriti, A.: Modeling biological systems in stochastic concurrent constraint programming. Constraints, an International Journal 13, 66–90 (2008) · Zbl 1144.92001 · doi:10.1007/s10601-007-9034-8
[17] Carbone, M., Maffeis, S.: On the expressive power of polyadic synchronisation in pi-calculus. Nordic Journal of Computing 10, 70–98 (2003) · Zbl 1062.68077
[18] Versari, C.: A Core Calculus for a Comparative Analysis of Bio-inspired Calculi. In: Programming Languages and Systems, pp. 411–425 (2007) · Zbl 1187.68331 · doi:10.1007/978-3-540-71316-6_28
[19] Priami, C.: Stochastic \(\pi\)-calculus. Computer Journal 6, 578–589 (1995) · Zbl 05478217 · doi:10.1093/comjnl/38.7.578
[20] Kuttler, C., Lhoussaine, C., Niehren, J.: A stochastic pi calculus for concurrent objects. In: 1st International Workshop on Probabilistic Automata and Logics (2006) · Zbl 1126.92003
[21] Phillips, A., Cardelli, L.: A correct abstract machine for the stochastic pi-calculus. In: Proceedings of BioConcur 2004 (2004)
[22] Versari, C., Busi, N.: Stochastic simulation of biological systems with dynamical compartment structure. In: Calder, M., Gilmore, S. (eds.) CMSB 2007. LNCS (LNBI), vol. 4695, pp. 80–95. Springer, Heidelberg (2007) · Zbl 05282347 · doi:10.1007/978-3-540-75140-3_6
[23] Jaffar, J., Lassez, J.L.: Constraint Logic Programming. In: POPL 1987: Proceedings of the 14th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages, pp. 111–119. ACM, New York (1987)
[24] Saraswat, V.A., Rinard, M.C.: Concurrent constraint programming. In: ACM SICPLAN-SIGACT Symposium on Principles of Programming Languages, pp. 232–245. ACM Press, New York (1990)
[25] John, M., Lhoussaine, C., Niehren, J., Uhrmacher, A.: The attributed pi calculus. In: Heiner, M., Uhrmacher, A.M. (eds.) CMSB 2008. LNCS (LNBI), vol. 5307, pp. 83–102. Springer, Heidelberg (2008) · Zbl 05351395 · doi:10.1007/978-3-540-88562-7_10
[26] Kuttler, C., Niehren, J.: Gene regulation in the pi calculus: Simulating cooperativity at the lambda switch. Transactions on Computational Systems Biology, 24–55 (2006)
[27] Kuttler, C.: Modeling Bacterial Gene Expression in a Stochastic Pi Calculus with Concurrent Objects. PhD thesis, Université des Sciences et Technologies de Lille - Lille 1 (2007)
[28] Versari, C.: A Core Calculus for the Analysis and Implementation of Biologically Inspired Languages. PhD thesis, University of Bologna (2009)
[29] Himmelspach, J., Uhrmacher, A.M.: Plug’n Simulate. In: ANSS 2007: Proceedings of the 40th Annual Simulation Symposium, Washington, DC, USA, pp. 137–143. IEEE Computer Society, Los Alamitos (2007)
[30] Baldamus, M., Parrow, J., Victor, B.: A fully abstract encoding of the pi-calculus with data terms. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol. 3580, pp. 1202–1213. Springer, Heidelberg (2005) · Zbl 1085.68594 · doi:10.1007/11523468_97
[31] Johansson, M., Parrow, J., Victor, B., Bengtson, J.: Extended pi-calculi. In: Aceto, L., Damgård, I., Goldberg, L.A., Halldórsson, M.M., Ingólfsdóttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part II. LNCS, vol. 5126, pp. 87–98. Springer, Heidelberg (2008) · Zbl 1155.68473 · doi:10.1007/978-3-540-70583-3_8
[32] Guerriero, M.L., Priami, C., Romanel, A.: Modeling static biological compartments with beta-binders. In: Anai, H., Horimoto, K., Kutsia, T. (eds.) AB 2007. LNCS, vol. 4545, pp. 247–261. Springer, Heidelberg (2007) · Zbl 1126.92002 · doi:10.1007/978-3-540-73433-8_18
[33] Priami, C., Quaglia, P., Romanel, A.: Blenx static and dynamic semantics. In: Bravetti, M., Zavattaro, G. (eds.) CONCUR 2009. LNCS, vol. 5710, pp. 37–52. Springer, Heidelberg (2009) · Zbl 1254.68060 · doi:10.1007/978-3-642-04081-8_4
[34] Maurin, M., Magnin, M., Roux, O.H.: Modeling of genetic regulatory network in stochastic pi-calculus. In: Rajasekaran, S. (ed.) BICoB 2009. LNCS (LNBI), vol. 5462, pp. 282–294. Springer, Heidelberg (2009)
[35] Lecca, P.: Stochastic pi-calculus models of the molecular bases of parkinson’s disease. In: International Conference on Bioinformatics and Computational Biology, pp. 298–304 (2008)
[36] Niehren, J.: Uniform confluence in concurrent computation. Journal of Functional Programming 10, 453–499 (2000) · Zbl 0974.68061 · doi:10.1017/S0956796800003762
[37] Huet, G.P.: Confluent reductions: Abstract properties and applications to term rewriting systems. Journal of the ACM 27, 797–821 (1980) · Zbl 0458.68007 · doi:10.1145/322217.322230
[38] Kuttler, C., Lhoussaine, C., Nebut, M.: Rule-based modeling of transcriptional attenuation at the tryptophan operon. In: Transactions on Computational Systems Biology (2009) · Zbl 1275.92024 · doi:10.1109/WSC.2009.5429721
[39] Tait, W.W.: Intensional interpretations of functionals of finite type i. Journal of Symbolic Logic 32, 198–212 (1967) · Zbl 0174.01202 · doi:10.2307/2271658
[40] Mitchell, J.C.: Foundations for Programming Languages. MIT Press, Cambridge (1996)
[41] John, M., Ewald, R., Uhrmacher, A.M.: A Spatial Extension to the Pi Calculus. ENTCS 194, 133–148 (2008) · Zbl 1279.68262
[42] Kholodenko, B.N.: Cell-Signalling Dynamics in Time and Space. Nature Reviews Molecular Cell Biology 7, 165–176 (2006) · doi:10.1038/nrm1838
[43] Grell, K.G.: Protozoologie. Springer, Heidelberg (1968) · doi:10.1007/978-3-662-12841-1
[44] John, M., Lhoussaine, C., Niehren, J.: Dynamic compartments in the imperative pi calculus. In: Degano, P., Gorrieri, R. (eds.) CMSB 2009. LNCS (LNBI), vol. 5688, pp. 235–250. Springer, Heidelberg (2009)
[45] Gillespie, D.T.: A General Method for Numerically Simulating the Stochastic Time Evolution of Coupled Chemical Reactions. Journal of Computational Physics 22, 403–434 (1976) · doi:10.1016/0021-9991(76)90041-3
[46] Khomenko, V., Meyer, R.: Checking pi-calculus structural congruence is graph isomorphism complete. Technical Report CS-TR: 1100, School of Computing Science, Newcastle University, 20 pages (2008)
[47] Gillespie, D.T.: Exact stochastic simulation of coupled chemical reactions. Journal of Physical Chemistry 81, 2340–2361 (1977) · doi:10.1021/j100540a008
[48] Gibson, M.A., Bruck, J.: Efficient exact stochastic simulation of chemical systems with many species and many channels. J. Phys. Chem. 104, 1876–1889 (2000) · doi:10.1021/jp993732q
[49] Pozo, R., Miller, B.: SciMark 2.0 (2009), http://math.nist.gov/scimark2/
[50] Degenring, D., Roehl, M., Uhrmacher, A.: Discrete event, multi-level simulation of metabolite channeling. BioSystems 1-3, 29–41 (2004) · doi:10.1016/j.biosystems.2004.03.008
[51] Mazemondet, O., John, M., Maus, C., Uhrmacher, A.M., Rolfs, A.: Integrating diverse reaction types into stochastic models - a signaling pathway case study in the imperative pi-calculus. In: Rossetti, M.D., Hill, R.R., Johansson, B., Dunkin, A., Ingalls, R.G. (eds.) Proceedings of the Winter Simulation Conference (to appear)
[52] Danos, V., Laneve, C.: Formal molecular biology. Theoretical Computer Science 325, 69–110 (2004) · Zbl 1071.68041 · doi:10.1016/j.tcs.2004.03.065
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.