Published in Volume XXIV, Issue 1, 2014, pages 91-136, doi: 10.7561/SACS.2014.1.91
Authors: C. Bodei, L. Brodo, R. Bruni, D. Chiarugi
Abstract
The link-calculus has been recently proposed as a process calculus for representing interactions that are open (i.e., that the number of processes may vary), and multiparty (i.e., that may involve more than two processes). Here, we apply the link-calculus for expressing, possibly hierarchical and non dyadic, biological interactions. In particular, we provide a natural encoding of Cardelli’s Brane calculus, a compartment-based calculus, introduced to model the behaviour of nested membranes. Notably, the link-calculus is flat, but we can model membranes just as special processes taking part in the biological reaction. Moreover, we give evidence that the link-calculus allows one to directly model biological phenomena at the more appropriate level of abstraction.
Full Text (PDF)References
[1] B. Alberts, A. Johnson, P. Water, J. Lewis, M. Raff, K. Roberts, and N. Orme. Molecular Biology of the Cell. Garland, 2007.
[2] R. Barbuti, G. Caravagna, A. Maggiolo-Schettini, P. Milazzo, and G. Pardini. The calculus of looping sequences. In Formal Methods for Computational Systems Biology, 8th International School on Formal Methods for the Design of Computer, Communication, and Software Systems (SFM 2008), volume 5016 of Lecture Notes in Computer Science, pages 387–423, 2008. http://dx.doi.org/10.1007/978-3-540-68894-5_11 .
[3] E. Bartocci, F. Corradini, M.R. Di Berardini, E. Merelli, and L. Tesei. Shape calculus. a spatial mobile calculus for 3d shapes. Scientific Annals of Computer Science, 20, 2010.
[4] C. Bodei, L. Brodo, and R. Bruni. Open multiparty interaction. In Recent Trends in Algebraic Development Techniques, 21st International Workshop (WADT 2012), volume 7841 of Lecture Notes in Computer Science, pages 1–23, 2013. http://dx.doi.org/10.1007/978-3-642-37635-1_1 .
[5] F. Bonchi, F. Gadducci, and G. V. Monreale. Labelled transitions for mobile ambients (as synthesized via a graphical encoding). Electronic Notes in Theoretical Computer Science, 242(1):73–98, 2009. http://dx.doi.org/10.1016/j.entcs.2009.06.014 .
[6] F. Bonchi, F. Gadducci, and G. V. Monreale. Reactive systems, barbed semantics, and the mobile ambients. In Foundations of Software Science and Computational Structures (FoSSaCS 2009), volume 5504 of Lecture Notes in Computer Science, pages 272–287, 2009. http://dx.doi.org/10.1007/978-3-642-00596-1_20 .
[7] L. Brodo. On the expressiveness of the π-calculus and the mobile ambients. In M. Johnson and D. Pavlovic, editors, Algebraic Methodology and Software Technology – 13th International Conference (AMAST 2010), volume 6486 of Lecture Notes in Computer Science, pages 44–59. Springer, 2010. http://dx.doi.org/10.1007/978-3-642-17796-5_3 .
[8] L. Cardelli. Brane calculi – interactions of biological membranes. In Computational Methods in Systems Biology, 7th International Conference (CMSB 2004), volume 3082 of Lecture Notes in Computer Science, pages 257–280. Springer, 2005. http://dx.doi.org/10.1007/978-3-540-25974-9_24 .
[9] L. Cardelli and A. D. Gordon. Mobile ambients. Theoretical Computer Science, 240(1):177–213, 2000. http://dx.doi.org/doi:10.1016/S0304-3975(99)00231-5 .
[10] G. Ciobanu, R. Desai, and A. Kumar. Membrane systems and distributed computing. In G. Pãun, G. Rozenberg, A. Salomaa, and C. Zandron, editors, Membrane Computing, International Workshop (WMC-CdeA 2002), volume 2597 of Lecture Notes in Computer Science, pages 187–202. Springer, 2003. http://dx.doi.org/10.1007/3-540-36490-0_12 .
[11] G. Ciobanu, M.J. Pérez-Jiménez, and G. Pa˘un, editors. Applications of Membrane Computing. Natural Computing Series. Springer, 2006.
[12] G. Ciobanu and V. A. Zakharov. Encoding mobile ambients into the π -calculus. In I. Virbitskaite and A. Voronkov, editors, Ershov Memorial Conference, 2006, volume 4378 of Lecture Notes in Computer Science, pages 148–165. Springer, 2007. http://dx.doi.org/10.1007/978-3-540-70881-0_15 .
[13] F. Ciocchetta. The BlenX language with biological transactions. In C. Priami, editor, Transactions on Computational Systems Biology IX, volume 5121 of Lecture Notes in Computer Science, pages 114–152. Springer, 2008. http://dx.doi.org/10.1007/978-3-540-88765-2_4 .
[14] F. Ciocchetta and J. Hillston. Bio-PEPA: An extension of the process algebra PEPA for biochemical networks. Electronic Notes in Theoretical Computer Science, 194(3):103–117, 2008. http://dx.doi.org/10.1016/j.entcs.2007.12.008 .
[15] V. Danos and C. Laneve. Graphs for core molecular biology. In Computational Methods in Systems Biology, 7th International Conference (CMS 2003), volume 2602 of Lecture Notes in Computer Science, pages 34–46, 2003. http://dx.doi.org/10.1007/3-540-36481-1_4 .
[16] L. Dematté, C. Priami, and A. Romanel. The BlenX language: a tutorial. In Formal Methods for Computational Systems Biology, School on Formal Methods for the Design of Computer, Communication, and Software Systems (SFM 2008), volume 5016 of Lecture Notes in Computer Science, pages 313–365. Springer, 2008. http://dx.doi.org/10.1007/978-3-540-68894-5_9.
[17] G. L. Ferrari, U. Montanari, and E. Tuosto. A LTS semantics of ambients via graph synchronization with mobility. In Theoretical Computer Science, 7th Italian Conference (ICTCS 2001), vol- ume 2202 of Lecture Notes in Computer Science, pages 1–16, 2001. http://dx.doi.org/10.1007/3-540-45446-2_1 .
[18] P. Gardner, C. Laneve, and L. Wischik. Linear forwarders. Information and Computation, 205(10):1526–1550, 2007. http://dx.doi.org/10.1016/j.ic.2007.01.006 .
[19] J. Heath, M.Z. Kwiatkowska, G. Norman, and D. Parker O. Tymchyshyn. Probabilistic model checking of complex biological pathways. Theoretical Computer Science, 391(3):239–257, 2008. http://dx.doi.org/10.1016/j.tcs.2007.11.013 .
[20] M. Kwiatkowska, G. Norman, and D. Parker. Using probabilistic model checking in systems biology. ACM SIGMETRICS Performance Evaluation Review, 35(4):14–21, 2008. http://dx.doi.org/10.1145/1364644.1364651 .
[21] C. Laneve and F. Tarissan. A simple calculus for proteins and cells. Electronic Notes in Theoretical Computer Science, 171(2):139–154, 2007. http://dx.doi.org/10.1016/j.entcs.2007.05.013 .
[22] M. Merro and F. Zappa Nardelli. Behavioral theory for mobile ambients. Journal of the ACM, 52(6):961–1023, 2005. http://dx.doi.org/10.1145/1101821.1101825 .
[23] C. Priami and P. Quaglia. Beta binders for biological interactions. In Computational Methods in Systems Biology, 7th International Conference (CMSB 2004), volume 3082 of Lecture Notes in Computer Science, pages 20–33, 2005. http://dx.doi.org/10.1007/978-3-540-25974-9_3 .
[24] J. Rathke and P. Sobociński. Deriving structural labelled transitions for mobile ambients. Information and Computation, 208(10):1221–1242, 2010. http://dx.doi.org/10.1007/978-3-540-85361-9_36 .
[25] A. Regev, E.M. Panina, W. Silverman, L. Cardelli, and E.Y. Shapiro. BioAmbients: An abstraction for biological compartments. Theoretical Computer Science, 325(1):141–167, 2004. http://dx.doi.org/10.1016/j.tcs.2004.03.061 .
[26] A. Regev, W. Silverman, and E.Y. Shapiro. Representation and simulation of biochemical processes using the π-calculus process algebra. In Pacific Symposium of Biocomputing 2001, volume 6, pages 459–470, 2001.
[27] C. Versari. A core calculus for a comparative analysis of bio-inspired calculi. In Programming Languages and Systems, 16th European Symposium on Programming (ESOP 2007), volume 4421 of Lecture Notes in Computer Science, pages 411–425, 2007. http://dx.doi.org/10.1007/978-3-540-71316-6_28 .
Bibtex
@article{sacscuza:bodei2014afpcfnmi,
title={A Flat Process Calculus for Nested Membrane Interactions},
author={C. Bodei and L. Brodo and R. Bruni and D. Chiarugi},
journal={Scientific Annals of Computer Science},
volume={24},
number={1},
organization={``A.I. Cuza'' University, Iasi, Romania},
year={2014},
pages={91--136},
doi={10.7561/SACS.2014.1.91},
publisher={``A.I. Cuza'' University Press}
}