NeMoFinder: dissecting genome-wide protein-protein interactions with meso-scale network motifs

ABSTRACT

Recent works in network analysis have revealed the existence of network motifs in biological networks such as the protein-protein interaction (PPI) networks. However, existing motif mining algorithms are not sufficiently scalable to find meso-scale network motifs. Also, there has been little or no work to systematically exploit the extracted network motifs for dissecting the vast interactomes.We describe an efficient network motif discovery algorithm, NeMoFinder, that can mine meso-scale network motifs that are repeated and unique in large PPI networks. Using NeMoFinder, we successfully discovered, for the first time, up to size-12 network motifs in a large whole-genome S. cerevisiae (Yeast) PPI network. We also show that such network motifs can be systematically exploited for indexing the reliability of PPI data that were generated via highly erroneous high-throughput experimental methods.

REFERENCES

• 1: István Albert , Réka Albert, Conserved network motifs allow protein--protein interaction prediction, Bioinformatics, v.20 n.18, p.3346-3352, December 2004 [doi>10.1093/bioinformatics/bth402]
• 2: J. Chen, W. Hsu, M. L. Lee, and S. K. Ng, Discovering and exploiting meso-scale network motifs in protein interactomes, National University of Singapore, TRC6/06, 2006
• 3: M. B. Eisen, P. T. Spellman, P. O. Brown, and D. Botstein, Cluster analysis and display of genome-wide expression patterns, Proc. Natl Acad. Sci. USA, 1998, volume 95, pages 14863--14868
• 4: S. Fortin, The graph isomorphism problem, Technical Report TR96-20, Department of Computing Science, University of Alberta, 1996
• 5: A. Grigoriev, A relationship between gene expression and protein interactions on the proteome scale, Nucleic Acids Res, Volume 29, Number 17, Pages 3513--3519, 2001
• 6: Jun Huan , Wei Wang , Jan Prins, Efficient Mining of Frequent Subgraphs in the Presence of Isomorphism, Proceedings of the Third IEEE International Conference on Data Mining, p.549, November 19-22, 2003
• 7: Jun Huan , Wei Wang , Jan Prins , Jiong Yang, SPIN: mining maximal frequent subgraphs from graph databases, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014123]
• 8: Akihiro Inokuchi , Takashi Washio , Hiroshi Motoda, An Apriori-Based Algorithm for Mining Frequent Substructures from Graph Data, Proceedings of the 4th European Conference on Principles of Data Mining and Knowledge Discovery, p.13-23, September 13-16, 2000
• 9: N. Kashtan , S. Itzkovitz , R. Milo , U. Alon, Efficient sampling algorithm for estimating subgraph concentrations and detecting network motifs, Bioinformatics, v.20 n.11, p.1746-1758, July 2004 [doi>10.1093/bioinformatics/bth163]
• 10: M. Kuramochi and G. Karypis, An efficient algorithm for discovering frequent subgraphs, TKDE, 2001
• 11: M. Kuramochi and G. Karypis, Finding Frequent Patterns in a Large Sparse Graph, In SIAM International Conference on Data Mining, 2004
• 12: S. Maslov and K. Sneppen, Specificity and stability in topology of protein networks, Science, Volume 296, Number 5569, Pages 910--913, 2002
• 13: C. V. Mering, R. Krause, B. Snel, et al, Comparative assessment of largescale data sets of protein-protein interactions, Nature, volume 417, pages 399--403, 2002
• 14: H. W. Mewes, D. Frishman, U. Guldener, et al, MIPS: a database for genomes and protein sequences, Nucleic Acids Res, Volume 30, Number 1, Pages 31--34, 2002
• 15: R. Milo, S. Shen-Orr, S. Itzkovitz, N. Kashtan, D. Chklovskii, and U. Alon, Network Motifs: Simple Building Blocks of Complex Networks, Science, volume 298, pages 824--827, 2002
• 16: R. Saito, H. Suzuki, and Y. Hayashizaki, Interaction generality, a measurement to assess the reliability of a protein-protein interaction, Nucleic Acids Res, 2002, volume 30, pages 1163--1168
• 17: R. Saito, H. Suzuki, and Y. Hayashizaki, Construction of reliable protein-protein interaction networks with a new interaction generality measure, Bioinformatics, 2002, volume 19, pages 756--763
• 18: F. Schreiber and H. Schwobbermeyer, Frequency Concepts and Pattern Detection for the Analysis of Motifs in Networks, Transactions on Computational Systems Biology, volume 3, pages 89--104, LNBI 3737, 2005
• 19: V. Spirin and L. A. Mirny, Protein complexes and functional modules in molecular networks, PNAS, 2003, volume 100, number 21, pages 12123--12128
• 20: Uetz, P., Giot, L., Cagney, G., et al, A comprehensive analysis of protein-protein interactions in Saccharomyces cerevisiae, Nature, Volume 403, Number 6770, Pages 623--627, 2000
• 21: Xifeng Yan , Jiawei Han, gSpan: Graph-Based Substructure Pattern Mining, Proceedings of the 2002 IEEE International Conference on Data Mining (ICDM'02), p.721, December 09-12, 2002

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

General Terms:
Algorithms, Experimentation, Performance

Keywords:
graph mining, network motif, protein-protein interaction network