Semantics of Multimodal Network Models

Abstract

A multimodal network (MMN) is a novel graph-theoretic formalism designed to capture the structure of biological networks and to represent relationships derived from multiple biological databases. MMNs generalize the standard notions of graphs and hypergraphs, which are the bases of current diagrammatic representations of biological phenomena, and incorporate the concept of mode. Each vertex of an MMN is a biological entity, a biot, while each modal hyperedge is a typed relationship, where the type is given by the mode of the hyperedge. The semantics of each modal hyperedge e is given through denotational semantics, where a valuation function f_{e} defines the relationship among the values of the vertices incident on e. The meaning of an MMN is denoted in terms of the semantics of a hyperedge sequence. A companion paper defines MMNs and concentrates on the structural aspects of MMNs. This paper develops MMN denotational semantics when used as a representation of the semantics of biological networks and discusses applications of MMNs in managing complex biological data.

References

1. L.S. Heath and A.A. Sioson, "Multimodal Networks: Structure and Operations," IEEE/ACM Trans. Computational Biology and Bioninformatics, vol. 6, no. 2, pp. 321-332, Apr.-June 2009.
2. P. Smolen, D.A. Baxter, and J.H. Byrne, "Modeling Transcriptional Control in Gene Networks--Methods, Recent Results, and Future Directions," Bull. Math. Biology, vol. 62, pp. 247-292, 2000.
3. L.S. Heath, "Networks in Bioinformatics," Proc. Int'l Symp. Parallel Architectures, Algorithms, and Networks (ISPAN '02), pp. 141-150, 2002.
4. K.W. Kohn, "Molecular Interaction Maps as Information Organizers and Simulation Guides," Chaos, vol. 11, no. 1, pp. 84-97, Dec. 2001.
5. I. Pirson, N. Fortemaison, C. Jacobs, S. Dremier, J.E. Dumont, and C. Maenhaut, "The Visual Display of Regulatory Information and Networks," Trends in Cell Biology, vol. 10, pp. 404-408, 2000.
6. R. Maimon and S. Browning, "Diagrammatic Notation and Computational Structure of Gene Networks," Proc. Second Int'l Conf. Systems Biology (CSB '01), Nov. 2001.
7. D.L. Cook, J. Farley, and S.J. Tapscott, "A Basis for a Visual Language for Describing, Archiving and Analyzing Functional Models of Complex Biological Systems," Genome Biology, vol. 2, no. 4, pp. 0012.1-0012.10, Mar. 2001.
8. H. Kitano, "A Graphical Notation for Biochemical Networks," BioSilico, vol. 1, no. 5, pp. 169-176, Nov. 2003.
9. H. Kitano, A. Funahashi, Y. Matsuoka, and K. Oda, "Using Process Diagrams for the Graphical Representation of Biological Networks," Nature Biotechnology, vol. 23, no. 8, pp. 961-966, Aug. 2005.
10. J. Gollub, C.A. Ball, G. Binkley, J. Demeter, D.B. Finkelstein, J.M. Hebert, T. Hernandez-Boussard, H. Jin, M. Kaloper, J.C. Matese, M. Schroeder, P.O. Brown, D. Botstein, and G. Sherlock, "The Stanford Microarray Database: Data Access and Quality Assessment Tools," Nucleic Acids Research, vol. 31, no. 1, pp. 94-96, Jan. 2003.
11. A.A. Sioson, J.I. Watkinson, C. Vasquez-Robinet, M. Ellis, M. Shukla, D. Kumar, N. Ramakrishnan, L.S. Heath, R. Grene, B.I. Chevone, K. Kadafar, and L.T. Watson, "Expresso and Chips: Creating a Next Generation Microarray Experiment Management System," Proc. 17th Int'l Parallel and Distributed Processing Symp. (IPDPS '03), Next Generation Software Systems Workshop, p. 209b, Apr. 2003.
12. S. Goto, T. Nishioka, and M. Kanehisa, "LIGAND: Chemical Database for Enzyme Reactions," Bioinformatics, vol. 14, no. 7, pp. 591-599, 1998.
13. S. Goto, Y. Okuno, M. Hattor, T. Nishioka, and M. Kanehisa, "LIGAND: Database of Chemical Compounds and Reactions in Biological Pathways," Nucleic Acids Research, vol. 30, pp. 402-404, 2002.
14. M.Y. Galperin, "The Molecular Biology Database Collection: 2007 Update," Nucleic Acids Research, vol. 35, pp. D3-D4, 2007.
15. O. Thimm, O. Blasing, Y. Gibon, A. Nagel, S. Meyer, P. Kruger, J. Selbig, L.A. Muller, S.Y. Rhee, and M. Stitt, "MAPMAN: A User-Driven Tool to Display Genomics Data Sets onto Diagrams of Metabolic Pathways and Other Biological Processes," Plant J., vol. 37, pp. 914-939, 2004.
16. B. Usadel, A. Nagel, O. Thimm, H. Redestig, O.E. Blaesing, N. Palacios-Rojas, J. Selbig, J. Hannemann, M. Conceicao, D. Steinhauser, W.-R. Scheible, Y. Gibon, R. Morcuende, D. Weicht, S. Meyer, and M. Stitt, "Extension of the Visualization Tool MAPMAN to Allow Statistical Analysis of Arrays, Display of Corresponding Genes, and Comparison with Known Responses," Plant Physiology, vol. 138, pp. 1195-1204, July 2005.
17. Gene Ontology Consortium, "The Gene Ontology (GO) Database and Informatics Resource," Nucleic Acids Research, vol. 32, pp. D258-D261, 2004.
18. M. Ashburner, C.A. Ball, J.A. Blake, D. Botstein, H. Butler, J.M. Cherry, A.P. Davis, K. Dolinsky, S.S. Dwight, J.T. Eppig, M.A. Harris, D.P. Hill, L. Issel-Tarver, A. Kasarskis, S. Lewis, J.C. Matese, J.E. Richardson, M. Ringwald, G.M. Rubin, and G. Sherlock, "Gene Ontology: Tool for the Unification of Biology," Nature Genetics, vol. 25, pp. 25-29, May 2000.
19. M. Hucka, A. Finney, H.M. Sauro, H. Bolouri, J.C. Doyle, H. Kitano, B.J.B.A.P. Arkin, D. Bray, A. Cornish-Bowden, A.A. Cuellar, S. Dronov, E.D. Gilles, M. Ginkel, V. Gor, I.I. Goryanin, W.J. Hedley, T.C. Hodgman, J.-H. Hofmeyr, P.J. Hunter, N.S. Juty, J.L. Kasberger, A. Kremling, U. Kummer, N. Le Novere, L.M. Loew, D. Lucio, P. Mendes, E. Minch, E.D. Mjolsness, Y. Nakayama, M.R. Nelson, P.F. Nielsen, T. Sakurada, J.C. Schaff, B.E. Shapiro, T.S. Shimizu, H.D. Spence, J. Stelling, K. Takahashi, M. Tomita, J. Wagner, and J. Wang, "The Systems Biology Markup Language (SBML): A Medium for Representation and Exchange of Biochemical Network Models," Bioinformatics, vol. 19, no. 14, pp. 524-531, 2003.
20. C.A. Ball, I.A. Awad, J. Demeter, J. Gollub, J.M. Hebert, T. Hernandez-Boussard, H. Jin, J.C. Matese, M. Nitzberg, F. Wymore, Z.K. Zachariah, P.O. Brown, and G. Sherlock, "The Stanford Microarray Database Accommodates Additional Microarray Platforms and Data Formats," Nucleic Acids Research, vol. 33, no. 1, pp. D580-D582, Jan. 2005.
21. L. Allison, A Practical Introduction to Denotational Semantics. Cambridge Univ. Press, 1986.
22. M.P. Fiore, A. Jung, E. Moggi, P. O'Hearn, J. Riecke, G. Rosolini, and I. Stark, "Domains and Denotational Semantics: History, Accomplishments and Open Problems," Bull. European Assoc. for Theoretical Computer Science, vol. 59, pp. 227-256, June 1996.
23. R.D. Tennent, "The Denotational Semantics of Programming Languages," Comm. ACM, vol. 19, no. 8, pp. 437-453, Aug. 1976.
24. A.A. Sioson, "Multimodal Networks in Biology," Dept. of Computer Science, Virginia Tech, Nov. 2005.
25. M. Stonebraker and G. Kemnitz, "The POSTGRES Next-Generation Database Management System," Comm. ACM, vol. 34, pp. 78- 92, 1991.
26. J.C. Reynolds, Theories of Programming Languages. Cambridge Univ. Press, 1998.
27. S. Xanthoudakis and D.W. Nicholson, "Heat-Shock Proteins as Death Determinants," Nature Cell Biology, vol. 2, pp. E163-E165, 2000.
28. J.-M. Bruey, C. Ducasse, P. Bonniaud, L. Ravagnan, S.A. Susin, C. Diaz-Latoud, S. Gurbuxani, A.-P. Arrigo, G. Kroemer, E. Solary, and C. Garrido, "HSP27 Negatively Regulates Cell Death by Interacting with Cytochrome c," Nature Cell Biology, vol. 2, pp. 645-652, 2000.
29. A. Saleh, S.M. Srinivasula, L. Balkir, and P.D. Robbins, "Negative Regulation of the Apaf-1 Apoptosome by Hsp70," Nature Cell Biology, vol. 2, pp. 476-483, 2000.
30. H.M. Beere, B.B. Wolf, K. Cain, D.D. Mosser, A. Mahboubi, T. Kuwana, P. Tailor, R.I. Morimoto, and G.M. Cohen, "Heat-Shock Protein 70 Inhibits Apoptosis by Preventing Recruitment of Procaspase-9 to the Apaf-1 Apoptosome," Nature Cell Biology, vol. 2, pp. 469-475, 2000.
31. M.K. Campbell and S.O. Farrell, Biochemistry, fourth ed. Thomson Brooks/Cole, 2005.
32. W.H. Elliott and D.C. Elliott, Biochemistry and Molecular Biology. Oxford Univ. Press, 1997.

Index Terms

• Applied computing

  • Life and medical sciences

    • Computational biology

    • Genetics

    • Systems biology

• Computing methodologies

  • Machine learning

• Mathematics of computing

  • Discrete mathematics

    • Graph theory

      • Hypergraphs

      • Network flows

• Theory of computation

  • Design and analysis of algorithms

    • Graph algorithms analysis

      • Network flows