On Minimality and Equivalence of Petri Nets

• Autorzy: Wagler A. K. , Wegener J-T.
• Języki publikacji: EN

Abstrakty

EN

The context of this work is the reconstruction of Petri net models for biological systems from experimental data. Such methods aim at generating all network alternatives fitting the given data. To keep the solution set small while guaranteeing its completeness, the idea is to generate only Petri nets being “minimal” in the sense that all other networks fitting the data contain the reconstructed ones. In this paper, we consider Petri nets with extensions in two directions: priority relations among the transitions of a network in order to allow modeling deterministic systems, and control-arcs in order to represent catalytic or inhibitory dependencies. We define a containment relation for Petri nets taking both concepts, priority relations and control-arcs, into account. We discuss the consequences for this kind of Petri nets differing in their sets of control-arcs and priority relations, and the impact of our results towards the reconstruction of such Petri nets.

Słowa kluczowe

EN

Petri nets; biological system; data analysis; set theory; computer networks; computer systems

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2013
• Tom: Vol. 128, nr 1-2
• Strony: 209--222
• Opis fizyczny: Bibliogr. 22 poz.

Twórcy

autor

Wagler A. K.

• Université Blaise Pascal (Clermont-Ferrand II), Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes, BP 10125, 63173 Aubière Cedex, France

autor

Wegener J-T.

• Université Blaise Pascal (Clermont-Ferrand II), Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes, BP 10125, 63173 Aubière Cedex, France

Bibliografia

• [1] Chen, M., Hofestadt, W.: A Petri net application of metabolic processes, Systems Analysis Modelling Simulation,, 16, 1994, 113-122.
• [2] Chen, M., Hofestadt, W.: Quantitative Petri net model fo gene regulated metabolic networks in the cell, In Silico Biology, 3, 2003, 347-365.
• [3] Durzinsky, M., Marwan, W., Wagler, A. K.: Reconstruction of extended Petri nets from time series data and its application to signal transduction and to gene regulatory networks, BMC Systems Biology, 5, 2011.
• [4] Durzinsky, M., Marwan, W., Wagler, A. K.: Reconstruction of extended Petri nets from time-series data by using logical control functions., Journal of Mathematical Biology, 66 (2013), 203-223.
• [5] Durzinsky, M., Wagler, A. K., Weismantel, R.: A Combinatorial Approach to Reconstruct Petri Nets from Experimental Data, CMSB (M. Heiner, A. M. Uhrmacher, Eds.), 5307, Springer, 2008, ISBN 978-3-54088561-0.
• [6] Durzinsky, M., Wagler, A. K., Weismantel, R.: An algorithmic framework for network reconstruction, Journal of Theoretical Computer Science, 412(26), 2011, 2800-2815.
• [7] Esparza, J., Nielsen, M.: Decidability Issues for Petri Nets - a Survey, Bulletin of the European Association for Theoretical Computer Science, 52, 1994, 245-262.
• [8] Favre, M., Wagler, A. K.: Reconstructing X'-deterministic extended Petri nets from experimental time-series data X'. 4th International Workshop on Biological Processes & Petri Nets, CEUR Workshop Proceedings 988 (2013), 45-59 (Special Issue BioPPN 2013).
• [9] Kholodenko, B. N., Kiyatkin, A., Bruggeman, F. J., Sontag, E., Westerhoff, H. V., Hoek, J. B.: Untangling the wires: A strategy to trace functional interactions in signaling and gene networks, Proceedings of the National Academy of Sciences, 99(20), 2002, 12841-12846.
• [10] Koch, I., Heiner, M.: Petri nets, Biological Network Analysis (B. H. Junker, F. Schreiber, Eds.), Wiley Book Series on Bioinformatics, 2007.
• [11] Kot, M., Sawa, Z.: Bisimulation equivalence of a BPP and a finite-state system can be decided in polynomial time, Electronic Notes in Theoretical Computer Science, 138(3), 2005,49-60, ISSN 1571-0661.
• [12] Krishna, R., Guo, S.: A partial granger causality approach to explode causal networks derived from multiparameter data, Computational Methods in Systems Biology, 5307, 2008, 9-27.
• [13] Laubenbacher, R., Stigler, B.: A computational algebra approach to reverse engineering of gene regulatory networks, Journal of Theoretical Biology, 229, 2005, 523-537.
• [14] Marwan, W., Wagler, A. K., Weismantel, R.: A mathematical approach to solve the network reconstruction problem, Math. Methods of Operations Research, 67(1), 2008, 117-132.
• [15] Marwan, W., Wagler, A. K., Weismantel, R.: Petri nets as a framework for the reconstruction and analysis of signal transduction pathways and regulatory networks, Natural Computing, 10, 2011, 639-654, ISSN 1567-7818.
• [16] Park, D.: Concurrency and Automata on Infinite Sequences, Proceedings of the 5th GI-Conference on Theoretical Computer Science, Springer-Verlag, London, UK, 1981, ISBN 3-540-10576-X.
• [17] Pinney, J. W., Westhead, R. D., McConkey, G. A.: Petri net representations in systems biology, Biochem. Soc. Tarns., 31, 2003, 1513-1515.
• [18] Torres, L. M., Wagler, A. K.: Model reconstruction for discrete deterministic systems, Electronic Notes in Discrete Mathematics, 36, 2010, 175-182, http://dx.doi.org/10.1016/j.endm.2010.05.023.
• [19] Torres, L. M., Wagler, A. K.: Encoding the dynamics of deterministic systems, Math. Methods of Operations Research, 73, 2011, 281-300.
• [20] Torres, L. M., Wagler, A. K., Weismantel, R.: Modelling the dynamic behavior of deterministic biological systems (extended abstract), Proc. of ALIO/EURO Workshop on Appl. Comb. Opt., 2008, ISBN 978-950-291116-8.
• [21] Wagler, A. K.: Prediction of network structure, vol. 16 of Computational Biology, Springer London, 2010, 309-338.
• [22] Wagler, A. K., Weismantel, R.: The combinatorics of modeling and analyzing biological systems, Natural Computing, 10, 2011, 655-681.