Multimodal Networks: Structure and Operations

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 current paper defines MMNs and concentrates on the structural aspects of MMNs. A companion paper develops MMNs as a representation of the semantics of biological networks and discusses applications of the MMNs in managing complex biological data. The MMN model has been implemented in a database system containing multiple kinds of biological networks.

References

1. 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.
2. K. Fukuda and T. Takagi, "Knowledge Representation of Signal Transduction Pathways," Bioinformatics, vol. 17, no. 9, pp. 829-837, 2001.
3. S. Xanthoudakis and D.W. Nicholson, "Heat-Shock Proteins as Death Determinants," Nature Cell Biology, vol. 2, pp. E163-E165, 2000.
4. P. Holme, M. Huss, and H. Jeong, "Subnetwork Hierarchies of Biochemical Pathways," Bioinformatics, vol. 19, no. 4, pp. 532-538, 2003.
5. S. Schuster, T. Pfeiffer, F. Moldenhauer, I. Koch, and T. Dandekar, "Exploring the Pathway Structure of Metabolism: Decomposition into Subnetworks and Application to Mycoplasma pneumoniae," Bioinformatics, vol. 18, no. 2, pp. 351-361, 2002.
6. H. Ma and A.-P. Zeng, "Reconstruction of Metabolic Networks from Genome Data and Analysis of Their Global Structure for Various Organisms," Bioinformatics, vol. 19, no. 2, pp. 270-277, 2003.
7. C.V. Forst, C. Flamm, I.L. Hofacker, and P.F. Stadler, "Algebraic Comparison of Metabolic Networks, Phylogenetic Inference, and Metabolic Innovation," BMC Bioinformatics, vol. 7, no. 67, Feb. 2006.
8. L.S. Heath, "Networks in Bioinformatics," Proc. Int'l Symp. Parallel Architectures, Algorithms, and Networks (I-SPAN '02), pp. 141-150, 2002.
9. A.A. Sioson and L.S. Heath, "Some Fundamental Operations on Multimodal Networks in Biology," Philippine Computing J., vol. 1, no. 2, pp. 13-22, Dec. 2006.
10. L.S. Heath and A.A. Sioson, "Semantics of Multimodal Network Models," IEEE/ACM Trans. Computational Biology and Bioinformatics , vol. 6, no. 2, pp. 271-280, Apr.-June 2009.
11. A.A. Sioson, "Multimodal Networks in Biology," Virginia Polytechnic Inst. and State Univ., Nov. 2005.
12. M. Stonebraker and G. Kemnitz, "The POSTGRES Next-Generation Database Management System," Comm. ACM, vol. 34, pp. 78- 92, 1991.
13. M. Benjamins, C.D.R. Lindveld, and R. van Nes, "Multimodal Travel Choice Modeling Using a Supernetwork Approach," Proc. 81st Transportation Research Board Ann. Meeting, 2002.
14. K. Uchida, A. Sumalee, D. Watling, and R. Connors, "Study on Optimal Frequency Design Problem for Multimodal Network Using Probit-Based User Equilibrium Assignment," Transportation Research Board, no. 1923, pp. 236-245, 2005.
15. H. Abrach, S. Bhatti, J. Carlson, H. Dai, J. Rose, A. Sheth, B. Shuckler, J. Deng, and R. Han, "Mantis: System Support for Multimodal Networks of In-Situ Sensors," Proc. Second ACM Int'l Workshop Wireless Sensor Networks and Applications (WSNA), 2003.
16. C. Berge, Hypergraphs. North-Holland, 1989.
17. G. Gallo, G. Longo, S. Pallottino, and S. Nguyen, "Directed Hypergraphs and Applications," Discrete Applied Math., vol. 42, pp. 177-201, 1993.
18. M.K. Campbell and S.O. Farrell, Biochemistry, fourth ed. Thomson Brooks/Cole, 2005.
19. W.H. Elliott and D.C. Elliott, Biochemistry and Molecular Biology. Oxford Univ. Press, 1997.
20. D.B. West, Introduction to Graph Theory, second ed. Prentice Hall, 2001.
21. B.C. Pierce, Basic Category Theory for Computer Scientists (Foundations of Computing). MIT Press, 1991.
22. Kyoto Encyclopedia of Genes and Genomes (KEGG) Website, http://www.kegg.org/, 2008.
23. 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.
24. 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.
25. 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.
26. M. Kanehisa, S. Goto, S. Kawashima, and A. Nakaya, "The KEGG Databases at GenomeNet," Nucleic Acids Research, vol. 30, no. 1, pp. 42-46, 2002.
27. M. Kanehisa, S. Goto, S. Kawashima, Y. Okuno, and M. Hattori, "The KEGG Resources for Deciphering the Genome," Nucleic Acids Research, vol. 32, pp. D277-D280, 2004.
28. R.G. Alscher, B.I. Chevone, L.S. Heath, and N. Ramakrishnan, "Expresso--A Problem Solving Environment for Bioinformatics: Finding Answers with Microarray Technology," Proc. High Performance Computing Symp., Advanced Simulation Technologies Conf. (HPC '01), pp. 64-69, 2001.
29. 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. Int'l Parallel and Distributed Processing Symp. Next Generation Software Systems Workshop (IPDPS '03), p. 209b, Apr. 2003.

Index Terms

• Applied computing

  • Life and medical sciences

• Computing methodologies

  • Machine learning

  • Modeling and simulation

    • Model development and analysis

      • Model verification and validation

      • Modeling methodologies

• Mathematics of computing

  • Discrete mathematics

    • Graph theory

      • Hypergraphs

      • Network flows

• Theory of computation

  • Design and analysis of algorithms

    • Graph algorithms analysis

      • Network flows