Functional modules of metabolic networks are essential for understanding the metabolism of an organism as a whole. With the vast amount of experimental data and the construction of complex and large-scale, often genome-wide, models, the computer-aided identification of functional modules becomes more and more important. Since steady states play a key role in biology, many methods have been developed in that context, for example, elementary flux modes, extreme pathways, transition invariants and place invariants. Metabolic networks can be studied also from the point of view of graph theory, and algorithms for graph decomposition have been applied for the identification of functional modules. A prominent and currently intensively discussed field of methods in graph theory addresses the Q-modularity. In this paper, we recall known concepts of module detection based on the steady-state assumption, focusing on transition-invariants (elementary modes) and their computation as minimal solutions of systems of Diophantine equations. We present the Fourier-Motzkin algorithm in detail. Afterwards, we introduce the Q-modularity as an example for a useful non-steady-state method and its application to metabolic networks. To illustrate and discuss the concepts of invariants and Q-modularity, we apply a part of the central carbon metabolism in potato tubers (Solanum tuberosum) as running example. The intention of the paper is to give a compact presentation of known steady-state concepts from a graph-theoretical viewpoint in the context of network decomposition and reduction and to introduce the application of Q-modularity to metabolic Petri net models.
Hao, D.; Ren, C.; Li, C. Revisiting the variation of clustering coefficient of biological networks suggests new modular structure. BMC Syst. Biol. 2012, 6, 34, doi:10.1186/1752-0509-6-34.
[4]
Reichardt, J.; Bornholdt, S. Detecting fuzzy community structures in complex networks with a potts model. Phys. Rev. Lett. 2004, 93, 218701, doi:10.1103/PhysRevLett.93.218701.
[5]
Scott, J. Social network analysis. Sociology 1988, 22, 109–127, doi:10.1177/0038038588022001007.
[6]
Baldwin, C.Y. Where do transactions come from? Modularity, transactions, and the boundaries of firms. Ind. Corp. Chang. 2008, 17, 155–195, doi:10.1093/icc/dtm036.
[7]
Adomavicius, G.; Tuzhilin, A. Toward the next generation of recommender systems: A survey of the state-of-the-art and possible extensions. IEEE Trans. Knowl. Data Eng. 2005, 17, 734–749, doi:10.1109/TKDE.2005.99.
[8]
Su, X.; Khoshgoftaar, T.M. A survey of collaborative filtering techniques. Adv. Artif. Intell. 2009, 2009, 421425:1–421425:19.
[9]
Zhou, M.; Venkatesh, K. Modeling, Simulation, and Control of Flexible Manufacturing Systems: A Petri Net Approach. In Intelligent Control and Intelligent Automation; World Scientific Publishing Company: Danvers, USA, 1999; Volume 6.
[10]
Billington, J.; Diaz, M.; Rozenberg, G. Application of Petri Nets to Communication Networks; Lecture Notes in Computer Science; Springer: Berlin/Heidelberg, Germany, 1999; Volume 1605.
[11]
Kernighan, B.; Lin, S. An efficient heuristic procedure for partitioning graphs. Bell Syst. Tech. J. 1970, 49, 291–307, doi:10.1002/j.1538-7305.1970.tb01770.x.
[12]
Newman, M.E.J.; Girvan, M. Finding and evaluating community structure in networks. Phys. Rev. E 2004, 69((2 Pt 2)), 026113, doi:10.1103/PhysRevE.69.026113.
[13]
Fortunato, S. Community detection in graphs. Phys. Rep. 2010, 486, 75–174, doi:10.1016/j.physrep.2009.11.002.
[14]
Heide, H.; Bleier, L.; Steger, M.; Ackermann, J.; Dr？se, J.; Schwamb, B.; Z？rnig, M.; Reichert, A.; Koch, I.; Wittig, I.; Brandt, U. Complexome profiling identifies TMEM126B as a component of the mitochondrial complex I assembly (MCIA) complex. Cell Metab. 2012, 16, 538–549, doi:10.1016/j.cmet.2012.08.009.
[15]
Guillaume, J.L.; Latapy, M. Bipartite structure of all complex networks. Inf. Process. Lett. 2004, 90, 215–221, doi:10.1016/j.ipl.2004.03.007.
[16]
Koch, I.; Reisig, W.; Schreiber, F. Modeling in Systems Biology: The Petri Net Approach; Springer: Berlin/Heidelberg, Germany, 2011.
[17]
Zaitsev, D. Decomposition of Petri nets. Cybern. Syst. Anal. 2004, 40, 739–746, doi:10.1007/s10559-005-0012-0.
[18]
Zeng, Q. A polynomial-time decomposition algorithm for petri nets based on indexes of transitions. Inf. Technol. J. 2011, 10, 856–862, doi:10.3923/itj.2011.856.862.
[19]
Berthelot, G. Checking Properties of Nets using Transformations. In Advances in Petri Nets 1985; Rozenberg, G., Ed.; Springer: Berlin/Heidelberg, Germany, 1986; Volume 222. Lecture Notes in Computer Science, pp. 19–40.
[20]
Berthelot, G. Transformations and Decompositions of Nets. In Petri Nets: Central Models and Their Properties; Brauer, W., Reisig, W., Rozenberg, G., Eds.; Springer: Berlin/Heidelberg, Germany, 1987; Volume 254. Lecture Notes in Computer Science, pp. 359–376.
[21]
Murata, T. Petri Nets: Properties, Analysis and Applications. In Proceedings of the IEEE, April 1989; Volume 77, pp. 541–580.
[22]
Starke, P. Analyse von Petri-Netz-Modellen; B.G. Teubner: Stuttgart, Germany, 1990.
[23]
Knuth, D. Fundamental Algorithms, 3 ed.. The Art of Computer Programming ed.; Addison-Wesley: Boston, MA, USA, 1997; Volume 1.
[24]
Cormen, T.; Leiserson, C.; Rivest, R.; Stein, C. Introduction to Algorithms; The MIT Press: Cambridge, MS, USA, 2001.
[25]
Garey, M.; Johnson, D. Computers and Intractability: A Guide to the Theory of NP-Completness; A series of books in the mathematical science; W.H. Freeman and Company: New York, NY, USA, 1979.
[26]
Klee, V.; Minty, G. How good is the simplex algorithm? Inequalities 1972, III, 159–175.
[27]
Zadeh, N. A bad network problem for the simplex method and other minimum cost flow algorithms. Math. Progr. 1973, 5, 255–266, doi:10.1007/BF01580132.
[28]
Adleman, L. Molecular computation of solutions to combinatorial problems. Science 1994, 266, 1021–1024. 7973651
[29]
Lipton, R. DNA solution of hard computational problems. Science 1995, 268, 542–545. 7725098
[30]
Shor, P.W. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. Soc. Ind. Appl. Math. Rev. 1999, 41, 303–332.
[31]
Paun, G. Membrane Computing. In Fundamentals of Computation Theory; Lingas, A., Nilsson, B., Eds.; Springer: Berlin/Heidelberg, Germany, 2003; Volume 2751. Lecture Notes in Computer Science, pp. 177–220.
[32]
Kanehisa, M.; Goto, S. KEGG: Kyoto encyclopedia of genes and genomes. Nucleic Acids Res. 2000, 28, 27–30, doi:10.1093/nar/28.1.27.
[33]
Petri, C. Communication with automata(in German). Ph.D. Thesis 63, Institut für Instrumentelle Mathematik, Bonn, Germany, 1962.
[34]
Bryant, R. Binary Decision Diagrams and Beyond: Enabling Technologies for Formal Verification. In Proceedings International Conference on Computer Aided Design, San Jose, CA, USA, 5–9 November 1995; IEEE Computer Society Press: New York, NY, USA, 1995; pp. 236–245.
[35]
Parikh, R. On context-free languages. J. Assoc. Comput. Mach. 1966, 13, 570–581, doi:10.1145/321356.321364.
[36]
Fourier, J. Solution d’une question particuliére du calcul des inègalitès. In Oeuvres 1826, II, 317–328.
[37]
Colom, J.; Silva, M. Convex geometry and semiflows in P/T nets. A comparative study of algorithms for computation of minimal p-semiflows. Lect. Notes Comput. Sci. 1991, 483, 78–112.
[38]
Esparza, J. Decidability and complexity of Petri net problems—An introduction. Lect. Notes Comput. Sci. 1998, 1491, 374–428, doi:10.1007/3-540-65306-6_20.
[39]
Schuster, S.; Hilgetag, C. On elementary flux modes in biochemical reaction systems at steady state. J. Biol. Syst. 1994, 2, 165–182, doi:10.1142/S0218339094000131.
[40]
Wagner, C. Nullspace approach to determine the elementary modes of chemical reaction systems. J. Phys. Chem. B 2004, 108, 2425–2431, doi:10.1021/jp034523f.
[41]
Terzer, M.; Stelling, J. Large-scale computation of elementary flux modes with bit pattern trees. Bioinformatics 2008, 24, 2229–2235, doi:10.1093/bioinformatics/btn401.
[42]
Jevremovic, D.; Boley, D.; Sosa, C. Divide-and-Conquer Approach to the Parallel Computation of Elementary Flux Modes in Metabolic Networks. In Proceedings of the IEEE International Symposium on Parallel & Distributed Processing, Busan, Korea, 26–28 May 2011; pp. 497–506.
[43]
Lipton, R. The reachability problem requires exponential space; Technical report 63; Department of Computer Science, Yale University: New Haven, CT, USA, 1976.
[44]
Schuster, S.; Pfeiffer, T.; Moldenhauer, F.; Koch, I.; Dandekar, T. Exploring the pathway structure of metabolism: Decomposition into subnetworks and application to Mycoplasma pneumoniae. Bioinformatics 2002, 18, 352–361.
[45]
Farkas, J. Theorie der einfachen Ungleichungen. J. für Die Reine Angew. Math. 1902, 124, 1–27.
[46]
Ackermann, J.; Einloft, J.; N？then, J.; Koch, I. Reduction techniques for network validation in systems biology. J. Theor. Biol. 2012, 315, 71–80, doi:10.1016/j.jtbi.2012.08.042.
[47]
Koch, I.; Junker, B.; Monika Heiner, M. Application of Petri net theory for modelling and validation of the sucrose breakdown pathway in the potato tuber. Bioinformatics 2005, 21, 1219–1226, doi:10.1093/bioinformatics/bti145.
[48]
Liao, J.C.; Hou, S.Y.; Chao, Y.P. Pathway analysis, engineering and physiological considerations for redirecting central metabolism. Biotechnol. Bioeng. 1996, 52, 129–140, doi:10.1002/(SICI)1097-0290(19961005)52:1<129::AID-BIT13>3.0.CO;2-J.
[49]
Schuster, S.; Dandekar, T.; Fell, D.A. Detection of elementary flux modes in biochemical networks: A promising tool for pathway analysis and metabolic engineering. Trends Biotechnolol. 1999, 17, 53–60, doi:10.1016/S0167-7799(98)01290-6.
[50]
Fischer, E.; Sauer, U. A novel metabolic cycle catalyzes glucose oxidation and anaplerosis in hungry Escherichia coli. J. Biol. Chem. 2003, 278, 46446–46451, doi:10.1074/jbc.M307968200.
Ballerstein, K.; von Kamp, A.; Klamt, S.; Haus, U.U. Minimal cut sets in a metabolic network are elementary modes in a dual network. Bioinformatics 2012, 28, 381–387, doi:10.1093/bioinformatics/btr674.
[53]
Sackmann, A.; Formanowicz, D.; Formanowicz, P.; Koch, I.; B？a？ewicz, J. An analysis of the Petri net based model of the human body iron homeostasis process. Comput. Biol. Chem. 2007, 31, 1–10, doi:10.1016/j.compbiolchem.2006.09.005.
[54]
Grafahrend-Belau, E.; Schreiber, F.; Heiner, M.; Sackmann, A.; Junker, B.; Grunwald, S.; Speer, A.; Winder, K.; Ina Koch, I. Modularisation of biochemical networks through hierarchical cluster analysis of T-invariants of biochemical Petri nets. BMC Bioinforma. 2008, 9, doi:10.1186/1471-2105-9-90.
[55]
Bortfeldt, R.; Schuster, S.; Koch, I. Exhaustive analysis of the modular structure of the spliceosomal assembly network: A Petri net approach. In Silico Biol. 2010, 10, 0007.
[56]
Sackmann, A. Modelling and Simulation of signaltransduction pathways of Saccharomyces crerevisiae based on Petri net theory(in German). Diploma Thesis, Ernst Moritz Arndt-University Greifswald, Greifswald, Germany, 2005.
[57]
Sackmann, A.; Heiner, M.; Koch, I. Application of Petri net based analysis techniques to signal transduction pathways. BMC Bioinforma. 2006, 7, 482, doi:10.1186/1471-2105-7-482.
[58]
Grafahrend-Belau, E. Classification of T-invariants in biochemical Petri nets based on different cluster analysis techniques(in German). Master’s Thesis, Technnical University of Applied Sciences Berlin, Berlin, Germany, 2006.
[59]
Backhaus, K.; Erichson, B.; Plinke, W.; Weiber, R. Multivariate Analysis Methods. An Application-oriented Introduction, 10th ed. ed.; Springer: Berlin, Germany, 2003. (in German).
[60]
Steinhausen, D.; Langer, K. Cluster Analysis. An Introduction to Methods for Automatic Classification. (in German); De Gruyter: Berlin, Germany, 1977.
[61]
Durbin, R.; Eddy, S.; Krogh, A.; Mitchison, G. Biological Sequence Analysis-Probabilistic Models of Proteins and Nucleic Acids; Cambridge University Press: Cambridge, MA, USA, 1998.
[62]
Handl, J.; Knowles, J.; Kell, D.B. Computational cluster validation in post-genomic data analysis. Bioinformatics 2005, 21, 3201–3212, doi:10.1093/bioinformatics/bti517.
[63]
Rousseeuw, P.J. Silhouettes: A graphical aid to the interpretation and validation of cluster analysis. J. Comput. Appl. Math. 1987, 20, 53–65, doi:10.1016/0377-0427(87)90125-7.
[64]
Grunwald, S.; Speer, A.; Ackermann, J.; Koch, I. Petri net modelling of gene regulation of the Duchenne muscular dystrophy. BioSystems 2008, 92, 189–205. 18372101
[65]
Pérès, S.; Beurton-Aimar, M.; Mazat, J.P. Pathway classification of TCA cycle. IEE Proc. Syst. Biol. 2006, 5, 369–371.
[66]
Kaleta, C.; de Figueiredo, L.; Schuster, S. Can the whole be less than the sum of its parts? Pathway analysis in genome-scale metabolic networks using elementary flux patterns. Genome Res. 2009, 19, 1872–1883, doi:10.1101/gr.090639.108.
[67]
Pfeiffer, T.; Sánchez-Valdenebro, I.; Nu？o, J.; Montero, F.; Schuster, S. METATOOL: For studying metabolic networks. Bioinformatics 1999, 15, 251–257, doi:10.1093/bioinformatics/15.3.251.
[68]
Kholodenko, B.; Schuster, S.; Rohwer, J.; Cascante, M.; Westerhoff, H. Composite control of cell function:Metabolic pathways behaving as single control units. FEBS Lett. 1995, 368, 1–4, doi:10.1016/0014-5793(95)00562-N.
[69]
Rohwer, J.; Schuster, S.; Westerhoff, H. How to recognize monofunctional units in a metabolic system. J. Theor. Biol. 1996, 179, 213–228, doi:10.1006/jtbi.1996.0062.
[70]
Schlegel, J. Network validation and application of Q-modularity to bipartite, directed graphs, in particular Petri nets. Beachelor’s Thesis, Johann Wolfgang Goethe-University Frankfurt am Main, Frankfurt am Main, Germany, 2012.
[71]
Li, C.; Donizelli, M.; Rodriguez, N.; Dharuri, H.; Endler, L.; Chelliah, V.; Li, L.; He, E.; Henry, A.; Stefan, M.I.; Snoep, J.L.; Hucka, M.; Le Novère, N.; Laibe, C. BioModels database: An enhanced, curated and annotated resource for published quantitative kinetic models. BMC Syst. Biol. 2010, 4, 92, doi:10.1186/1752-0509-4-92.
[72]
Gagneur, J.; Klamt, S. Computation of elementary modes: A unifying framework and the new binary approach. BMC Bioinforma. 2004, 5, 175, doi:10.1186/1471-2105-5-175.
[73]
Einloft, J.; Ackermann, J.; N？then, J.; Koch, I. MonaLisa-visualization and analysis of functional modules in biochemical networks. Bioinformatics 2013, 29, 1469–1470, doi:10.1093/bioinformatics/btt165.
[74]
Murray, J. Mathematical Biology; Springer: Berlin/Heidelberg, Germany, 2002; Volume 2.
[75]
Deuflhard, P.; Bornemann, F. Scientific Computing with Ordinary Differential Equations; Springer: Berlin/Heidelberg, Germany, 2002; Volume 42.
[76]
Haken, H. Synergetics: An introduction; Springer: Berlin/Heidelberg, Germany, 1983; Volume 1.
