Maximally Parallel Probabilistic Semantics for Multiset Rewriting

• Autorzy: Barbuti R. , Levi F. , Milazzo P. , Scatena G.
• Języki publikacji: EN

Abstrakty

EN

Maximally parallel semantics have been proposed for many formalisms as an alternative to the standard interleaving semantics for some modelling scenarios. Nevertheless, in the probabilistic setting an affirmed interpretation of maximal parallelism still lacks. We define a synchronous maximally parallel probabilistic semantics for multiset rewriting tailored to describe, simulate and verify biological systems evolving with maximally parallel steps. Each step of the proposed semantics is parallel as each reaction can happen multiple times, and it is maximal as it leaves no enabled reaction i.e. as many reactions as possible are executed. We define a maximally parallel probabilistic semantics in terms of Discrete Time Markov Chain for systems described by stochastic multiset rewriting. We propose a simple, maximally parallel, model of Caenorhabditis elegans vulval development on which we show probabilistic simulations results.

Słowa kluczowe

EN

maximally parallel semantics

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2011
• Tom: Vol. 112, nr 1
• Strony: 1--17
• Opis fizyczny: Bibliogr. 32 poz., tab., wykr.

Twórcy

autor

Barbuti R.

autor

Levi F.

autor

Milazzo P.

autor

Scatena G.

• IMT Lucca Inst. for Advanced Studies, Piazza San Ponziano 6, 55100 - Lucca, Italy,

Bibliografia

• [1] Bistarelli, S., Cervesato, I., Lenzini, G., Marangoni, R. and Martinelli, F.: On Representing Biological Systems through Multiset Rewriting, Proc. EUROCAST03. LNCS 2809, 415-426, Springer, 2003.
• [2] Cavaliere, M., and Sedwards, S.: Modeling and simulating biological processes with stochastic multiset rewriting, Proc. Simulation and Verification of Dynamic Systems, Dagstuhl Seminar Proceedings, 06161, 2006.
• [3] Cervesato, I., Durgin, N. A., Lincoln, P. D., Mitchell, J. C. and Scedrov A.: A meta-notation for protocol analysis, Proc. CSFW, 55-69, 1999.
• [4] Fisher, J., Henzinger, T. A., Mateescu, M. and Piterman, N.: Bounded Asynchrony: Concurrency for Modeling Cell-Cell Interactions, Proc. FMSB, LNCS 5054, 17-32, Springer, 2008.
• [5] Pǎun, G.: Membrane computing: An introduction, Springer, 2002.
• [6] Burkhard, H.D.: On priorities of parallelism, Proc. Logics of Programs, LNCS 148, 86-97, Springer, 1980,
• [7] Alhazoc, A. and Verlan, S.: Minimization strategies for maximal parallel multiset rewriting systems, Technical report, Turku Centre for Computer Science, 2008.
• [8] Ciobanu, G., Paun, G. and Pérez-Jiménez, M.J.: On the branching complexity of P Systems, Fundam. Inform., 73(1-2), 27-36, 2006.
• [9] Gutirrez-Naranjo, M. A., Prez-Jimnez, M. J., Riscos-Nez, A. : On the degree of parallelism in membrane systems, Theor. Comput. Sci., 183-195, Elsevier, 2007.
• [10] Fisher, J., Piterman, N., Hajnal, A., and Henzinger, T.A.: Predictive modeling of signaling crosstalk during C. elegans vulval development, PLoS computational biology, 3(5), 2007.
• [11] Fisher, J., Piterman, N., Hubbard, E.J.A., Stern, M.J. and Harel, D.: Computational insights into C. elegans vulval development, Proc. Nat. Acad. Sci. USA, 102(6), 1951-1956, 2005.
• [12] Sadot, A., Fisher, J., Barak, D., Admanit ,Y, Stern, M.J., Hubbard, E.J.A. and Harel, D.: Toward verified biological models, IEEE/ACM Trans. Comput. Biol. Bioinform., 5(2), 223-234, 2008.
• [13] Bonzanni, N., Krepska, E., Feenstra, K.A., Fokkink, W., Kielmann, T., Bal, H.E. and Heringa, J.: Executing multicellular differentiation: quantitative predictive modelling of C. elegans vulval development, Bioinformatics, 25(16), 2049-2056, 2009.
• [14] Li, C., Nagasaki, M., Ueno, K., and Miyano, S.: Simulation-based model checking approach to cell fate specification during C. elegans vulval development by hybrid functional petri net with extension, BMC Syst. Biol., 3(1):42, 2009.
• [15] Sternberg, P.W. and Horvitz, H.R.: The combined action of two intercellular signaling pathways specifies three cell fates during vulval induction in C. elegans, Cell, 58, 679-693, 1989.
• [16] Sternberg, P.W.: Vulval development, The C. elegans Research Community, ed. WormBook, 2005.
• [17] Petri, C.:Kommunikation mit Automaten, PhD th., Un. of Bonn, Germany, 1962.
• [18] Heiner, H., Gilbert, D., and Donaldson, R.: Petri nets for systems and synthetic biology, Proc. SFM, LNCS 5016, 215-264, Springer, 2008.
• [19] Pescini, D., Besozzi, D., Mauri, G. and Zandron, C.: Dynamical probabilistic P Systems, Int. J. Found. Comput. Sci., 17(1), 183-204. 2006.
• [20] Ciobanu, G. and Cornacel, L.: Probabilistic transitions for P Systems, Progr. Nat. Sci., 17(4), 431-441, 2007.
• [21] Ardelean, I. and Cavaliere, M.: Modelling biological processes by using a probabilistic P Systems software, Nat. Comp., 2(2), 173-197. Springer Netherlands, 2003.
• [22] Madhu, M.: Probabilistic rewriting P Systems, Int. J. Found. Comput. Sci., 14(1), 157-166, 2003.
• [23] Obtulowicz, A. Probabilistic P Systems. Proc. WMC-CdeA. LNCS 2597, 377-387. Springer, 2003.
• [24] Obtulowicz, A. and Pǎun, G.: (In search of) Probabilistic P Systems. BioSystems, 70(2), 107-121, 2003.
• [25] Cardelli, L., Zavattaro, G.: On the Computational Power of Biochemistry, Proc. Algebraic Biology. LNCS 5147, 65-80. Springer, 2008.
• [26] Spicher, A., Michel, O., Cieslak, M., Giavitto, J.L., and Prusinkiewicz, P.: Stochastic P Systems and the simulation of biochemical processes with dynamic compartments, Biosystems, 91(3), 458-472, 2008.
• [27] Romero-Campero, F.J. and Pérez-Jiménez, M.J.: A model of the quorum sensing system in vibrio fischeri using P Systems, Artif. Life, 14(1), 95-109, (2008)
• [28] Bernardini, F., Romero-Campero, F.J., Gheorghe, M., Perez-Jimenez, M.J., Margenstern, M., Verlan, S. and Krasnogor, N.: On P systems with bounded parallelism, Proc. SYNASC, 399-407. IEEE, 2005.
• [29] Romero-Campero, F.J., Gheorghe,M., Bianco, L., Pescini, D., Pérez-Jiménez,M.J and Ceterchi, R.: Towards Probabilistic Model Checking on P Systems Using PRISM, Proc. WMC. LNCS 4361, 477-495. Springer (2006)
• [30] Gillespie, D.: Exact stochastic simulation of coupled chemical reactions, Journ. Phys. Chem., 81(25) 2340-2361, 1977.
• [31] Phillips, A., Cardelli, L.: Efficient, Correct Simulation of Biological Processes in the Stochastic Pi-calculus. Proc. CMSB. LNCS 4695, 184-199. Springer, 2007.
• [32] Barbuti, R., Levi, F., Milazzo, P., Scatena, G.: Probabilistic Model Checking of Biological Systems with Uncertain Kinetic Rates. Proc. RP. LNCS 5797, 64-78. Springer, 2009.