Dynamical Systems for Discovering Protein Complexes and Functional Modules from Biological Networks

ABSTRACT

Recent advances in high throughput experiments and annotations via published literature have provided a wealth of interaction maps of several biomolecular networks, including metabolic, protein-protein, and protein-DNA interaction networks. The architecture of these molecular networks reveals important principles of cellular organization and molecular functions. Analyzing such networks, i.e., discovering dense regions in the network, is an important way to identify protein complexes and functional modules. This task has been formulated as the problem of finding heavy subgraphs, the Heaviest k{\hbox{-}}\rm Subgraph Problem (k{\hbox{-}}\rm HSP), which itself is NP-hard. However, any method based on the k{\hbox{-}}\rm HSP requires the parameter k and an exact solution of k{\hbox{-}}\rm HSP may still end up as a "spurious” heavy subgraph, thus reducing its practicability in analyzing large scale biological networks. We proposed a new formulation, called the rank-HSP, and two dynamical systems to approximate its results. In addition, a novel metric, called the Standard deviation and Mean Ratio (SMR), is proposed for use in "spurious” heavy subgraphs to automate the discovery by setting a fixed threshold. Empirical results on both the simulated graphs and biological networks have demonstrated the efficiency and effectiveness of our proposal.

REFERENCES

• 1: [1] A. Barabasi and Z. N. Oltvai, "Biology: Understanding the Cell's Functional Organization," Nature Rev., vol. 5, pp. 101-113, 2004.
• 2: [2] T. Ito et al., "Toward a Protein-Protein Interaction Map of the Budding Yeast: A Comprehensive System to Examine Two-Hybrid Interactions in All Possible Combinations between the Yeast Proteins," Proc. Nat'l Academy of Sciences USA, vol. 97, pp. 1143-1147, 2000.
• 3: [3] V. Spirin and L. A. Mirny, "Protein Complexes and Functional Modules in Molecular Networks," Proc. Nat'l Academy of Sciences USA, vol. 100, pp. 12123-12128, 2003.
• 4: [4] P. Uetz et al., "A Comprehensive Analysis of Protein-Protein Interactions in Saccharomyces Cerevisiae," Nature, vol. 403, pp. 623-627, 2000.
• 5: [5] A.-C. Gavin et al., "Functional Organization of the Yeast Proteome by Systemic Analysis of Protein Complexes," Nature, vol. 415, pp. 141-147, 2002.
• 6: [6] Y. Ho et al., "Systematic Identification of Protein Complexes in Saccharomyces Cerevisiae by Mass Spectrometry," Nature, vol. 415, pp. 180-183, 2002.
• 7: [7] Y. Qi, J. Klein-Seetharaman, and Z. Bar-Joseph, "Random Forest Similarity for Protein-Protein Interaction Prediction Form Multiple Sources," Proc. Pacific Symp. Biocomputing, pp. 531-542, 2005.
• 8: [8] J. Gagneur, R. Krause, T. Bouwmeester, and G. Casari, "Modular Decomposition of Protein-Protein Interaction Networks," Genome Biology, vol. 5, no. 8, p. R57, 2004.
• 9: [9] S. Tornow and H. Mewes, "Functional Modules by Relating Protein Interaction Networks and Gene Expression," Nucleic Acid Research, vol. 31, no. 21, pp. 6283-6289, 2003.
• 10: [10] L. Hartwell, J. Hopfield, S. Leibler, and A. Murray, "From Molecular to Modular Cell Biology," Nature, vol. 402, no. 6761, supplement, pp. C47-C52, 1999.
• 11: [11] A. Billionnet, "Different Formulations for Solving the Heaviest k-Subgraph Problem," Information Systems and Operational Research , vol. 43, no. 3, pp. 171-186, 2005.
• 12: U. Feige , M. Seltser, On the densest k-subgraph problems, Weizmann Science Press of Israel, Jerusalem, Israel, 1997
• 13: [13] T. S. Motzkin and E. G. Straus, "Maxima for Graphs and a New Proof of a Theorem of Turán," Canadadian J. Math., vol. 17, no. 4, pp. 533-540, 1965.
• 14: [14] J. Hofbauer and K. Sigmund, Evolutionary Games and Population Dynamics. Cambridge Univ. Press, 1998.
• 15: [15] J. F. Crow and M. Kimura, An Introduction to Population Genetics Theory. Harper & Row, 1970.
• 16: [16] L. E. Baum and J. A. Eagon, "An Inequality with Applications to Statistical Estimation for Probabilistic Functions of Markov Processes and to a Model for Ecology," Bull. Am. Math. Soc., vol. 73, p. 360-363, 1967.
• 17: Marcello Pelillo, The Dynamics of Nonlinear Relaxation Labeling Processes, Journal of Mathematical Imaging and Vision, v.7 n.4, p.309-323, Oct. 1997 [doi>10.1023/A:1008255111261 ]
• 18: [18] J. J. Hopfield, "Neural Networks and Physical Systems with Emergent Collective Computational Abilities," Proc. Nat'l Academy of Sciences USA, vol. 79, no. 8, pp. 2554-2558, Apr. 1982.
• 19: Bart Kosko, Bidirectional associative memories, IEEE Transactions on Systems, Man and Cybernetics, v.18 n.1, p.49-60, January/February 1988 [doi>10.1109/21.87054 ]
• 20: [20] J. J. Hopfield and D. W. Tank, "Neural Computations of Decisions in Optimization Problems," Biological Cybernetics, vol. 52, no. 141, pp. 144-152, 1985.
• 21: Kate A. Smith, Neural Networks for Combinatorial Optimization: a Review of More Than a Decade of Research, INFORMS Journal on Computing, v.11 n.1, p.15-34, January 1999
• 22: [22] E. Domíguez and J. Muñoz, "Bidirectional Neural Network for Clustering Problems," Proc. Ninth Ibero-Am. Conf. AI, 2004.
• 23: Gene H. Golub , Charles F. Van Loan, Matrix computations (3rd ed.), Johns Hopkins University Press, Baltimore, MD, 1996
• 24: [24] Y. Qi, Z. Bar-Joseph, and J. Klein-Seetharaman, "Evaluation of Different Biological Data and Computational Classification Methods for Use in Protein Interaction Prediction," PROTEINS: Structure, Function, and Bioinformatics, 2006.
• 25: [25] B. Lemon and R. Tjian, "Orchestral Response: A Symphony of Transcription Factors for Gene Control," Genes & Development, vol. 14, pp. 2551-2569, 2000.
• 26: Haiyan Hu , Xifeng Yan , Yu Huang , Jiawei Han , Xianghong Jasmine Zhou, Mining coherent dense subgraphs across massive biological networks for functional discovery, Bioinformatics, v.21 n.1, p.213-221, January 2005 [doi>10.1093/bioinformatics/bti1049]
• 27: [27] A. Tong, B. Drees, G. Nardelli, G. Bader, B. Brannetti, and L. Castagnoli, "A Combined Experimental and Computational Strategy to Define Protein Interaction Networks for Peptide Recognition Modules," Science, vol. 295, no. 5553, pp. 321-324, 2002.
• 28: N. Pržulj , D.A. Wigle , I. Jurisica, Functional topology in a network of protein interactions, Bioinformatics, v.20 n.3, p.340-348, February 2004 [doi>10.1093/bioinformatics/btg415]
• 29: [29] H. Yu, X. Zhu, D. Greenbaum, J. Karro, and M. Gerstein, "Topnet: A Tool for Comparing Biological Subnetworks, Correlating Protein Proterties with Topological Stastics," Nucleic Acids Research, vol. 32, pp. 328-337, 2004.
• 30: A. D. King , N. Pržulj , I. Jurisica, Protein complex prediction via cost-based clustering, Bioinformatics, v.20 n.17, p.3013-3020, November 2004 [doi>10.1093/bioinformatics/bth351]
• 31: [31] G. Bader and C. Hogue, "An Automated Method for Finding Molecular Complexes in Large Protein Interaction Networks," BMC Bioinformatics, vol. 4, no. 2, 2003.
• 32: Erez Hartuv , Ron Shamir, A clustering algorithm based on graph connectivity, Information Processing Letters, v.76 n.4-6, p.175-181, Dec.31 2000 [doi>10.1016/S0020-0190(00)00142-3 ]
• 33: [33] G. Corneil and Y. Perl, "Clustering and Domination in Perfect Graphs," Discrete Applied Math., vol. 9, no. 1, pp. 7-39, 1984.
• 34: [34] A. Billionnet and F. Roupin, "A Deterministic Approximation Algorithm for the Densest k-Subgraph Problem," Technical Report 486, CEDRIC, CNAM-IIE, 2004.
• 35: Yuichi Asahiro , Kazuo Iwama , Hisao Tamaki , Takeshi Tokuyama, Greedily finding a dense subgraph, Journal of Algorithms, v.34 n.2, p.203-221, Feb. 2000 [doi>10.1006/jagm.1999.1062 ]
• 36: [36] U. Feige, G. Kortsarz, and D. Peleg, "The Dense k-Subgraph Problem," Algorithmica, vol. 29, no. 3, pp. 410-421, 2001.
• 37: Uriel Feige , Michael Langberg, Approximation algorithms for maximization problems arising in graph partitioning, Journal of Algorithms, v.41 n.2, p.174-211, November 2001 [doi>10.1006/jagm.2001.1183 ]
• 38: [38] Q. Han, Y. Ye, and J. Zhang, "An Improved Rounded Method and Semidefinite Programming Relaxation for Graph Partition," Math. Programming, vol. 92, no. 3, pp. 509-535, 2002.
• 39: [39] L. Giot et al., "A Protein Interaction Map of Drosophila Melanogaster," Science, vol. 302, no. 5651, pp. 1727-1736, 2003.
• 40: [40] S. Li et al., "A Map of the Interactome Network of the Metazoan C. Elegans," Science, vol. 303, no. 5657, pp. 540-543, 2004.
• 41: [41] S. Shen-Orr, R. Milo, S. Mangan, and U. Alon, "Network Motifs in the Transcriptional Regulation Network of Escherichia coli," Nature Genetics, vol. 31, pp. 64-68, 2002.
• 42: [42] J. A. Dunne, R. J. Williams, and N. D. Martinez, "Network Structure and Biodiversity Loss in Food Webs: Robustness Increases with Connectance," Ecology Letters, vol. 5, no. 4, pp. 558-567, 2002.

INDEX TERMS

Primary Classification:
  J. Computer Applications
  J.3 LIFE AND MEDICAL SCIENCES
      Subjects: Biology and genetics

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.1 Models
          Subjects: Neural nets

General Terms:
Design, Experimentation, Measurement, Performance

Keywords:
Graph algorithms, neural nets, evolutionary computing, bioinformatics databases.