Improved computational methods to analyze the mathematical structure and function of biochemical networks are needed when the biomolecular connectivity is known but when a complete set of the equilibrium and rate constants may not be available. We use Petri nets, which are equivalently bipartite digraphs, to analyze the rule-based flow of information through the network. We present several computational improvements to Petri net modeling as an aid to improve this approach, previously limited by the combinatorics of network size and complexity. The generation of Petri nets using equations for three elemental stencils (molecular reaction, synthesis complex formation, and decomposition complex formation) has been automated. A set of finite probability measures is defined in terms of a partition information entropy, where the complete listing of unique minimal cycles (UMCs) of the Petri net provides the natural partitioning. This enables the ranking of the UMC listing that covers all possible information flows in the reaction network; the information entropy measure enables the identification of which UMCs are more significant than others. In terms of the information entropy, forward cycles are less surprising and carry less information entropy, whereas backward cycles carry more information entropy and serve as regulators by providing feedback to control the network. As the systems analyzed increase in size and complexity, the automatic rank ordering of the UMCs provides a mechanism to highlight the globally most important information without the need to make local simplifying modeling choices. The information entropy metric is also used to compute source-to-sink information costs and is related to knockout analyses. The hybrid Petri net approach shows the most important species and where it is easiest to disrupt or otherwise affect the network. As exemplar, the enhanced methodology is applied to a model of the initial subnetwork in the EGFR network.
AbroudiA, SamarasingheS, KulasiriD. Towards abstraction of computational modelling of mammalian cell cycle: Model reduction pipeline incorporating multi-level hybrid petri nets. J Theor Biol, 2020; 496:110212; doi: 10.1016/j.jtbi.2020.110212
2.
AckermannJ, KochI. Quantitative analysis. In: Modeling in Systems Biology: The Petri Net Approach. (KochI, ReisigW, SchreiberF. eds.) Springer-Verlag: New York; 2011:153–178; doi: 10.1007/978-1-84996-474-6
3.
AksoySG, HagberA, JoslynCA, et al.Models and methods for sparse (Hyper) network; Science in Business, Industry, and Government. Notices Amer Math Soc, 2022; 69(02):1–291; doi: 10.1090/noti2424
4.
AlexisA, SchulteCCM, CardelliL, et al.Regulation strategies for two-output biomolecular networks. J R Soc Interface, 2023; 20(205):20230174; doi: 10.1098/rsif.2023.0174
5.
AlonU. An Introduction to Systems Biology: Design Principles of Biological Circuits, 2nd Ed. CRC Press: Boca Raton, FL; 2020.
6.
AmsteinL, AckermannJ, ScheidelJ, et al.Manatee invariants reveal functional pathways in signaling networks. BMC Syst Biol, 2017; 11(1):72; doi: 10.1186/s12918-017-0448-7
7.
AnslynEV, DoughertyDA. Modern Physical Organic Chemistry. University Science Books: Melville, NY; 2006.
8.
ArabzadehM, ZamaniMS, SedighiM, et al.A graph-based approach to analyze flux-balanced paths in metabolic networks. Biosystems, 2018; 165:40–51; doi: 10.1016/j.biosystems.2017.12.001
9.
AsthagiriAR, LauffenburgerDA. Bioengineering models of cell signaling. Annu Rev Biomed Eng, 2000; 2:31–53; doi: 10.1146/annurev.bioeng.2.1.31
BradshawRA, DennisEA. (eds). Handbook of Cell Signaling, Cell Biology, 2nd ed.. Academic Press, Elsevier: Amsterdam, Netherlands; 2010; Three volume set.
16.
CormenTH, LeisersonCH, RivestRL, et al.Introduction to Algorithms, 4th ed. MIT Press and McGraw-Hill; 2022.
17.
Cornish-BowdenA. Zacharias Dische and the discovery of feedback inhibition: A landmark paper published in the forerunner of Biochimie. Biochimie, 2021; 182:120–130; doi: 10.1016/j.biochi.2020.11.013
18.
DavidR, AllaH. Discrete, Continuous, and Hybrid Petri Nets. Springer-Verlag: Berlin, Germany; 2005.
19.
DiaconisP, GrahamR, HolmesSP. Statistical problems involving permutations with restricted positions in state of the art in probability and statistics: Festschrift for Willem R. van Zwet. In: IMS Lecture Notes Monogr Ser, 36. (de GunstM, KlaasenC, van der VaartA. eds.), Cambridge University Press; 2001; 195–222; doi: 10.1214/lnms/1215090070
20.
DischeZ. Sur l’interdépendance des Divers Enzymes du Système Glycolytique et sur la Régulation Automatique de leur Activité dans les Cellules. Bull Soc Chim Biol, 1941; 23:1140–1148.
21.
DiStefanoJ.III. Dynamic Systems Biology Modeling and Simulation. Elsevier: New York; 2014; 618–621.
22.
DoiA, FujitaS, MatsunoH, et al.Constructing biological pathway models with hybrid functional petri nets. In Silico Biol, 2004; 4(3):271–291.
23.
EllermanD. Counting distinctions: On the conceptual foundations of shannon’s information theory. Synthese, 2009; 168(1):119–149; doi: 10.1007/s11229-008-9333-7
24.
EllermanD. Introduction to logical entropy and its relationship to shannon entropy. 4open, 2022; 5:1–33; doi: 10.1051/fopen/2021004
25.
EllermanD. New Foundations for Information Theory: Logical Entropy and Shannon Entropy. Springer, Berlin, 2021; doi: 10.1007/978-3-030-86552-8
FormanowiczD, RybarczykA, RadomM, et al.A stochastic petri net-based model of the involvement of interleukin 18 in Atherosclerosis. Int J Mol Sci, 2020; 21(22):8574; doi: 10.3390/ijms21228574
29.
GajdošP, JežowiczT, UherV, et al.A parallel fruchterman-reingold algorithm optimized for fast visualization of large graphs and swarms of data. Swarm and Evol Comput, 2016; 26:56–63; doi: 10.1016/j.swevo.2015.07.006
30.
GalloG, LongoG, PallottinoS, et al.Directed hypergraphs and applications. North-Holland, Elsevier Science Publishers. Discrete Appl. Math, 1993; 42(2–3):177–201; doi: 10.1016/0166-218X(93)90045-P
GilbertD, HeinerM. From petri nets to differential equations: an integrative approach for biochemical network analysis. In: Petri Nets and Other Models of Concurrency - ICATPN 2006, LNCS, 4024. (DonatelliS, ThiagarajanPS. eds.) Springer-Verlag: Berlin; 2006; 181–200; doi: 10.1007/11767589_11
33.
GiraultC, ValkR. Petri Nets for Systems Engineering: A Guide to Modeling, Verification, and Applications. Springer-Verlag: Berlin, Germany; 2003; 1–607.
34.
GogolińskaA, NowakW. Chapter 9: Petri nets in biology modeling. In: Graph-Based Modelling in Science, Technology and Art. Mechanisms and Machine Science 107. (ZawiślakS, RysińskiJ. eds.) Springer, Berlin; 2022; 175–200; doi: 10.1007/978-3-030-76787-7
GutowskaK, KogutD, KardynskaM, et al.Petri Nets and ODEs as complementary methods for comprehensive analysis on an example of the ATM-p53-NF-B signaling paths. . Sci Rep, 2022; 12(1):1135; doi: 10.1038/s41598-022-04849-0
HardyS, IyengarR. Analysis of dynamical models of signaling networks with petri nets and dynamic graphs. In: Modeling in Systems Biology: The Petri Net Approach. (KochI, ReisigW, SchreiberF. eds.) Springer-Verlag: New York; 2011; 225–251; doi: 10.1007/978-1-84996-474-6
39.
HeinerM, KochI. Petri net based model validation in systems biology. In: Applications and Theory of Petri Nets 2004; ICATPN; Vo. 3099. Lecture Note in Computer Science. Springer; 2004. (CortadellaJ, ReisigW. eds.);216–237; doi: 10.1007/978-3-540-27793-4_13
40.
HeinerM, UhrmacherAM. (eds.). Computational methods in systems biology. LNBI 5307, Springer, Berlin, 2008.
41.
HeinerM, HerajyM, LiuF, et al.Snoopy–A Unifying Petri Net Tool. In: Application and Theory of Petri Nets. PETRI NETS 2012. Lecture Notes in Computer Science, vol 7347. HaddadS, PomelloL (eds). Springer: Berlin, Heidelberg; 2012, 398–407; doi: 10.1007/978-3-642-31131-4_22
42.
HelmreichEJM. The Biochemistry of Cell Signaling. Oxford University Press: Oxford; 2001.
43.
HerajyM, LiuF, RohrC, et al.Coloured hybrid petri nets: An adaptable modelling approach for multi-scale biological networks. Comput Biol Chem, 2018; 76:87–100; doi: 10.1016/j.compbiolchem.2018.05.023
44.
HofestädtR. Advantages of petri-net modeling and simulation for biological networks. Int. J. Biosci. Biochem. Bioinform, 2017; 7:221–229; doi: 10.17706/ijbbb.2017.7.4.221-229
45.
HollandJH. Hidden Order: How Adaptation Builds Complexity.The Ulam Lecture Series, Helix Books, Basic Books, Perseus Books Group: New York; 1995.
JensenK, KristensenLM. Colored petri nets: A graphical language for formal modeling and validation of concurrent systems: Formal executable models enable systematic evaluation of system designs prior to implementation and deployment. CACM, 2015; 58:61–70; doi: 10.1145/2663340
48.
JensenK. Coloured petri net and the invariant-method. Theor Comput Sci, 1981; 14(3):317–336; doi: 10.1016/0304-3975(81)90049-9
49.
JensenK. Coloured Petri Nets: Basic Concepts, Analysis Methods and Practical Use, Vols 1–3, 2nd Corrected edition. Springer-Verlag: New York, 1997.
50.
JohnsonDB. Finding all the elementary circuits of a directed graph. SIAM J Comput, 1975; 4(1):77–84; doi: 10.1137/0204007
51.
KochI, BüttnerB. Computational modeling of signal transduction networks without kinetic parameters: Petri net approaches. Am J Physiol Cell Physiol, 2023; 324(5):C1126–C1140; doi: 10.1152/ajpcell.00487.2022
52.
KochI, ReisigW, SchreiberF, (eds.). Modeling in System Biology: The Petri Net Approach. Springer-Verlag London Ltd; 2011; doi: 10.1007/978-1-84996-474-6
53.
KolitzSE, LauffenburgerDA. Measurement and modeling of signaling at the single-cell level. Biochem, 2012; 51(38):7433–7443; doi: 10.1021/bi300846p
KraussG. Biochemistry of Signal Transduction and Regulation, 5th Ed. Wiley: Weinheim, Germany; 2014.
56.
KungJPS, RotaG-C, YanCH. Combinatorics: The Rota Way. Cambridge University Press: New York; 2009; 28–40.
57.
LautenbachK, PinlA. A petri net representation of bayesian message flows: Importance of bayesian networks for biological applications. Nat Comput, 2011; 10(2):683–709; doi: 10.1007/s11047-009-9142-z
58.
LautenbachK. Exakte Bedingungen der Lebendigkeit für eine Klasse von Petri-Netzen (“Exact Liveness Conditions of a Petri Net Class”, dissertation). Rheinische Friedrich-Wilhelms-Universität Bonn: Germany; 1973. Number 82 in Berichte der GMD, (In German). Gesellschaft für Mathematik und Datenverarbeitung, Sankt Augustin. Available from: https://publica.fraunhofer.de/entities/publication/b673abda-ed35-4aae-83e2-5bb5f9fd5a1d [Last accessed: January29, 2025].
59.
LautenbachK. Linear algebraic techniques for place/transition nets. In: Petri Nets: Central Models and Their Properties. Lecture Notes in Computer Science. (BrauerW, ReisigW, RozenbergG. eds.). Springer: Berlin; 1987; 254:142–167, doi: 10.1007/978-3-540-47919-2_7
60.
LehrackS. Three Petri Net Approaches for Biochemical Network Analysis. Report 01/06, (Supervision by Gilbert D, Heiner M), Brandenburg University of Technology at Cottbus, Mathematics, Natural Sciences and Computer Science, Institute of Computer Science: Germany; 2006. Available from: https://www-dssz.informatik.tu-cottbus.de/publications/btu-reports/btuReport_2006_01_lehrack.pdf [Last accessed: September24, 2024].
61.
LiuG. Petri Nets: Theoretical Models and Analysis Methods for Concurrent Systems. Springer: Singapore; 2022.
MarksF, KlingmüllerU, Müller-DeckerK. Cellular Signal Processing: An Introduction to the Molecular Mechanisms of Signal Transduction, 2nd ed. Routledge: London; 2017; doi: 10.4324/9781315165479
64.
MatsunoH, DoiA, NagasakiM, et al.Hybrid petri net representation of gene regulatory network. In:. Pacific Symposium on Biocomputing; 2000; (AltmanRB, LauderdaleK, DunkerAK, HunterL, KleinTE. eds.) World Scientific: Singapore; 2000, 339–349.
65.
MatsunoH, LiuF, ChenM. Editorial: Petri nets for cellular process modelling. Biosystems, 2022; 212:104603; doi: 10.1016/j.biosystems.2021.104603
66.
MurataT. Petri nets: Properties, analysis and applications. Proc IEEE, 1989; 77(4):541–580; doi: 10.1109/5.24143
67.
OliveiraJS, BaileyCG, Jones-OliveiraJB, et al.A computational model for the identification of biochemical pathways in the Krebs Cycle. J Comput Biol, 2003; 10(1):57–82; doi: 10.1089/106652703763255679
68.
OliveiraJS, BaileyCG, Jones-OliveiraJB, et al.An algebraic-combinatorial model for the identification and mapping of biochemical paths. Bull Math Biol, 2001; 63(6):1163–1196; doi: 10.1006/bulm.2001.0263
69.
OliveiraJS, Jones-OliveiraJB, DixonDA, et al.Hyperdigraph-Theoretic analysis of the EGFR signaling network: Initial steps leading to GTP: RAS complex formation. J Comput Biol, 2004; 11(5):812–842; doi: 10.1089/cmb.2004.11.812
70.
PalssonBØ. Systems Biology: Properties of Reconstructed Networks. Cambridge University Press: New York; 2006; doi: 10.1017/CBO9780511790515
PinterCC. A Book of Set Theory. Dover: New York; 2014; 1–256.
73.
ReddyVN, MavrovouniotisML, LiebmanMN. Petri net representations in metabolic pathways. Proceedings of the First International Conference on Intelligent Systems for Molecular Biology, Book 1, ISMB Proceedings, 3, Association for the Advancement of Artificial Intelligence, Washington DC, 1993; 328–336.
ReisigW. Petri nets: An introduction. In: EATCS Monographs on Theoretical Computer Science. (BrauerW, RozenbergG, SalomaaA. eds.) Springer-Verlag, Berlin; 1985; 4.
76.
RotaG-C. Twelve problems in probability no one likes to bring up. In: Algebraic Combinatorics and Computer Science. (CrapoH, SenatoD. eds.), Springer-Verlag Italia: Milano; 2001, 57–93; doi 10.1007/978-88-470-2107-5
77.
RuthsD, MullerM, TsengJ-T, et al.The signaling petri net-based simulator: A non-parametric strategy for characterizing the dynamics of cell-specific signaling networks. PLoS Comput Biol, 2008; 4(2):e1000005; doi: 10.1371/journal.pcbi.1000005
78.
SchrijverA. On the history of the shortest path problem. In: Optimization Stories: 21st International Symposium on Mathematical Programming Berlin, August 19–24, 2012. (GrötschelM, ed.), Documenta Mathematica: Bielefeld, Germany, 2012, 155–167 doi: 10.4171/DMS/6/19
79.
SchrijverA. Theory of Linear and Integer Programming. Wiley; 1998.
80.
SchusterS, HilgetagC. On elementary flux modes in biochemical reaction systems at steady state. J Biol Syst, 1994; 02(02):165–182; doi: 10.1142/S0218339094000131
81.
SchusterS, KlamtS, WeckwerthW, et al.Use of network analysis of metabolic systems in bioengineering. Bioprocess Biosyst Eng, 2002; 24:363–372; doi: 10.1007/s004490100253
82.
SelimkhanovJ, TaylorB, YaoJ, et al.Accurate information transmission through dynamic biochemical signaling networks. Science, 2014; 346(6215):1370–1373; doi: 10.1126/science.1254933
83.
ShafiekhaniS, PoursheykhaniA, RahbarS, et al.Simulating ATO mechanism and EGFR signaling with fuzzy logic and petr net. J Biomed Phys Eng, 2021; 11(3):325–336; doi: 10.31661/jbpe.v0i0.796
84.
ShannonCE, WeaverW. The Mathematical Theory of Communication, University of Illinois Press: Urbana; 1949.
85.
ShannonCE. A mathematical theory of communications: Part III. Bell System Tech J, 1948b;27(4):623–656; doi: 10.1002/j.1538-7305.1948.tb00917.x
86.
ShannonCE. A mathematical theory of communications: Parts 1 and 2. Bell Systems Tech J, 1948a;27(3):379–423; doi: 10.1002/j.1538-7305.1948.tb01338.x
87.
ShannonCE. A Symbolic Analysis of Relay and Switching Circuits. Master’s Thesis, Massachusetts Institute of Technology, Cambridge, MA, 1937. Available from: https://dspace.mit.edu/handle/1721.1/11173
88.
ShannonCE. An Algebra for Theoretical Genetics. Dissertation, Massachusetts Institute of Technology, Cambridge, MA, 1940. Available from: https://dspace.mit.edu/handle/1721.1/11174
89.
SimoviciDA, DjerabaC. Mathematical Tools for Data Mining: Set Theory, Partial Orders, Combinatorics. Springer-Verlag: London; 2008; 305–321; doi 10.1007/978-1-4471-6407-4
90.
SitaramayyaA, (ed). Introduction to Cellular Signal Transduction. Birkhaüser: Boston, MA; 1999.
91.
TarjanRE. Depth-First search and linear graph algorithms. SIAM J Comput, 1972; 1(2):146–160; doi: 10.1137/0201010
92.
VossK, HeinerM, KochI. Steady state analysis of metabolic pathways using petri nets. In: Silico Biol, 2003; 3(3):367–387.
93.
WangL, DashS, ChiamYN, et al.A review of computational tools for design and reconstruction of metabolic paths. Synth Syst Biotechnol, 2017; 2(4):243–252; doi: 10.1016/j.synbio.2017.11.002
