Mining frequent cross-graph quasi-cliques

ABSTRACT

Joint mining of multiple datasets can often discover interesting, novel, and reliable patterns which cannot be obtained solely from any single source. For example, in bioinformatics, jointly mining multiple gene expression datasets obtained by different labs or during various biological processes may overcome the heavy noise in the data. Moreover, by joint mining of gene expression data and protein-protein interaction data, we may discover clusters of genes which show coherent expression patterns and also produce interacting proteins. Such clusters may be potential pathways.

In this article, we investigate a novel data mining problem, mining frequent cross-graph quasi-cliques, which is generalized from several interesting applications in bioinformatics, cross-market customer segmentation, social network analysis, and Web mining. In a graph, a set of vertices S is a γ-quasi-clique (0 < γ ≤ 1) if each vertex v in S directly connects to at least γ ⋅ (|S| − 1) other vertices in S. Given a set of graphs G₁, …, G_n and parameter min_sup (0 < min_sup ≤ 1), a set of vertices S is a frequent cross-graph quasi-clique if S is a γ-quasi-clique in at least min_sup ⋅ n graphs, and there does not exist a proper superset of S having the property.

We build a general model, show why the complete set of frequent cross-graph quasi-cliques cannot be found by previous data mining methods, and study the complexity of the problem. While the problem is difficult, we develop practical algorithms which exploit several interesting and effective techniques and heuristics to efficaciously mine frequent cross-graph quasi-cliques. A systematic performance study is reported on both synthetic and real data sets. We demonstrate some interesting and meaningful frequent cross-graph quasi-cliques in bioinformatics. The experimental results also show that our algorithms are efficient and scalable.

REFERENCES

• 1: James Abello , Mauricio G. C. Resende , Sandra Sudarsky, Massive Quasi-Clique Detection, Proceedings of the 5th Latin American Symposium on Theoretical Informatics, p.598-612, April 03-06, 2002
• 2: Alon, U., Barkai, N., Notterman, D., Gish, K., Ybarra, S., Mack, D., and Levine, A. 1999. Broad patterns of gene expression revealed by clustering analysis of tumor and normal colon tissues probed by oligonucleotide array. Proc. Natl. Acad. Sci. 96, 12, 6745--6750.
• 3: Bader, G. and Hogue, C. 2003. An automated method for finding molecular complexes in large protein interaction networks. BMC Bioinformatics 4, 1, 2.
• 4: Barab´si, A. and Albert, R. 1999. Emergence of scaling in random networks. Science 286.
• 5: Bayada, D., Simpson, R., and Johnson, A. 1992. An algorithm for the multiple common subgraph problem. J. Chemi. Inform. Comput. Sci., 680--685.
• 6: Beissbarth, T., Fellenberg, K., Brors, B., et al. 2000. Processing and quality control of DNA array hybridization data. Bioinformatics 16, 1014--1022.
• 7: Ben-Dor, A., Shamir, R., and Yakhini, Z. 1999. Clustering gene expression patterns. J. Computati. Biol. 6, 3/4, 281--297.
• 8: Brazma, A. and Vilo, J. 2000. Minireview: Gene expression data analysis. Federation European Biochemical Societies 480, 17--24.
• 9: Bu, D., Zhao, Y., Cai, L., et al. 2003. Topological structure analysis of the protein-protein interaction network in budding yeast. Nucl. Acids Research. 31, 9, 2443--2450.
• 10: Cho, R., Campbell, M., Winzeler, E., et al. 1998. A genome-wide transcriptional analysis of the mitotic cell cycle. Mole. Cell 2, 1, 65--73.
• 11: Choi, K., Satterberg, B., Lyons, D., and Elion, E. 1994. Ste5 tethers multiple protein kinases in the map kinase cascade required for mating in S. cerevisiae. Cell 78, 499--C512.
• 12: Chu, S., DeRisi, J., Eisen, M., Mulholland, J., Botstein, D., Brown, P., and Herskowitz, I. 1998. The transcriptional program of sporulation in budding yeast. Science 282, 5389, 699--705.
• 13: DeRisi, J., Iyer, V., and Brown, P. 1997. Exploring the metabolic and genetic control of gene expression on a genomic scale. Science, 680--686.
• 14: Chris H. Q. Ding , Xiaofeng He , Hongyuan Zha , Ming Gu , Horst D. Simon, A Min-max Cut Algorithm for Graph Partitioning and Data Clustering, Proceedings of the 2001 IEEE International Conference on Data Mining, p.107-114, November 29-December 02, 2001
• 15: Dongen, S. 2000. Graph clustering by flow simulation. PhD Thesis, University of Utrecht, The Netherlands.
• 16: Sašo Džeroski, Multi-relational data mining: an introduction, ACM SIGKDD Explorations Newsletter, v.5 n.1, July 2003 [doi>10.1145/959242.959245]
• 17: Eisen, M., Spellman, P., Brown, P., and Botstein, D. 1998. Cluster analysis and display of genome-wide expression patterns. Proc. Natl. Acad. Sci. 95, 14863--14868.
• 18: Enright, A., Dongen, S., and Ouzounis, C. 2002. An efficient algorithm for large-scale detection of protein families. Nucl. Acids Resear. 30, 7, 1575--1584.
• 19: Christos Faloutsos , Kevin S. McCurley , Andrew Tomkins, Fast discovery of connection subgraphs, 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.1014068]
• 20: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 21: Gasch, A., Huang, M., Metzner, S., Botstein, D., Elledge, S., and Brown, P. 2001. Genomic expression responses to DNA-damaging agents and the regulatory role of the yeast ATR homolog Mec1p. Mol. Biol. Cell 12, 10, 2987--3003.
• 22: Gasch, A., Spellman, P., Kao, C., Carmel-Harel, O., Eisen, M., Storz, G., Botstein, D., and Brown, P. 2000. Genomic expression programs in the response of yeast cells to environmental changes. Mol. Biol. Cell 11, 12, 4241--4257.
• 23: Gavin, A., Bosche, M., Krause, R., and et. al. 2002. Functional organization of the yeast proteome by systematic analysis of protein complexes. Nature 415, 6868, 123--124.
• 24: 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]
• 25: Ho, Y., Gruhler, A., Heilbut, A., et al. 2002. Systematic identification of protein complexes in saccharomyces cerevisiae by mass spectrometry. Nature 415, 180--183.
• 26: Holder, L., Cook, D., and Djoko, S. 1994. Substructure discovery in the subdue system. In Proceedings of the AAAI'94 Workshop on Knowledge Discvoery in Databases (KDD'94). 359--370.
• 27: 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
• 28: Ito, T., Tashiro, K., Muta, S., Ozawa, R., Chiba, T., Nishizawa, M., Yamamoto, K., Kuhara, S., and Sakaki, Y. Toward a protein-protein interaction map of the budding yeast: A comprehensive system to examine twohybrid interactions in all possible combinations between the yeast proteins. Proc. Natl. Acad. Sci.
• 29: Glen Jeh , Jennifer Widom, Mining the space of graph properties, 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.1014075]
• 30: Michihiro Kuramochi , George Karypis, Frequent Subgraph Discovery, Proceedings of the 2001 IEEE International Conference on Data Mining, p.313-320, November 29-December 02, 2001
• 31: Lee, H., Hsu, A., Sajdak, J., Qin, J., and Pavlidis, P. 2004. Coexpression analysis of human genes across many microarray data sets. Genome Resear. 14, 1085--1094.
• 32: Lyons, D., Mahanty, S., Choi, K., Manandhar, M., and Elion, E. 1996. The Sh3-domain protein Bem1 coordinates mitogen-activated protein kinase cascade activation with cell cycle control in Saccharomyces cerevisiae. Mol. Cell Biol. 16, 4095--C4106.
• 33: H. Matsuda , T. Ishihara , A. Hashimoto, Classifying molecular sequences using a linkage graph with their pairwise similarities, Theoretical Computer Science, v.210 n.2, p.305-325, Jan. 17, 1999 [doi>10.1016/S0304-3975(98)00091-7]
• 34: Mewes, H., Frishman, D., Mayer, K., et al. 2006. MIPS: Analysis and annotation of proteins from whole genomes in 2005. Nucl. Acids Resear. 34 (Supplement 1), D169--D172.
• 35: Moreau, Y., Aerts, S., Moor, B., Strooper, B., and Dabrowski, M. 2003. Comparison and meta-analysis of microarray data: From the bench to the computer desk. TRENDS Genetics 19, 570--577.
• 36: Ng, A., Jordan, M., and Weiss, Y. 2001. On spectral clustering: analysis and an algorithm. Adv. Neural Inform. Process. Syst. 14.
• 37: David Page , Mark Craven, Biological applications of multi-relational data mining, ACM SIGKDD Explorations Newsletter, v.5 n.1, July 2003 [doi>10.1145/959242.959250]
• 38: Christopher R. Palmer , Phillip B. Gibbons , Christos Faloutsos, ANF: a fast and scalable tool for data mining in massive graphs, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775059]
• 39: Jian Pei , Daxin Jiang , Aidong Zhang, On mining cross-graph quasi-cliques, Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA [doi>10.1145/1081870.1081898]
• 40: Rymon, R. 1992. Search through systematic set enumeration. In Proceedings of International Conference on Principles of Knowledge Representation Reasoning (RR'92).
• 41: Segal, E., Wang, H., and Koller, D. 2003. Discovering molecular pathways from protein interaction and gene expression data. Bioinformatics 19, i264--i272.
• 42: Roded Sharan , Ron Shamir, Center CLICK: A Clustering Algorithm with Applications to Gene Expression Analysis, Proceedings of the Eighth International Conference on Intelligent Systems for Molecular Biology, p.307-316, August 19-23, 2000
• 43: Spellman, P., Sherlock, G., Zhang, M., Iyer, V., Anders, K., Eisen, M., Brown, P., Botstein, D., and Futcher, B. 1998. Exploring the metabolic and genetic control of gene expression on a genomic scale. Mol. Biol. Cell 3273.
• 44: Stuart, J., Segal, E., Koller, D., and Kim, S. 2003. A gene-coexpression network for global discovery of conserved genetic modules. Science 302, 249--255.
• 45: Takahashi, Y., Satoh, Y., and Sasaki, S. 1987. Recognition of largest common fragment among a variety of chemical structures. Analyt. Sci., 23--28.
• 46: Tamayo, P., Solni, D., Mesirov, J., Zhu, Q., Kitareewan, S., Dmitrovsky, E., Lander, E., and Golub, T. 1999. Interpreting patterns of gene expression with self-organizing maps: Methods and application to hematopoietic differentiation. Proc. Natl. Acad. Sci. 96, 6, 2907--2912.
• 47: Tavazoie, S., Hughes, D., Campbell, M., Cho, R., and Church, G. 1999. Systematic determination of genetic network architecture. Nature Genet. 281--285.
• 48: Tong, A. H., Evangelista, M., Parsons, A. B., and et al. 2001. Systematic genetic analysis with ordered arrays of yeast deletion mutants. Science 294, 2364--2368.
• 49: Tong, A. H. Y., Lesage, G., Bader, G. D., and et al. 2004. Global mapping of the yeast genetic interaction network. Science 303, 808--813.
• 50: Tseng, G., Oh, M., Rohlin, L., Liao, J., and Wong, W. 2001. Issues in cDNA microarray analysis: Quality filtering, channel normalization, models of variations and assessment of gene effects. Nucleic Acids Resear. 29, 2549--2557.
• 51: Uetz, P., Giot, L., Cagney, G., and et. al. 2000. A comprehensive analysis of protein-protein interactions in Saccharomyces Cerevisiae. Nature 403, 6770, 601--603.
• 52: Chen Wang , Wei Wang , Jian Pei , Yongtai Zhu , Baile Shi, Scalable mining of large disk-based 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.1014088]
• 53: Xu, Y., Olman, V., and Xu, D. 2002. Clustering gene expression data using a graph-theoretic approach: an application of minimum spanning trees. Bioinformatics 18, 536--545.
• 54: Xifeng Yan , Jiawei Han, gSpan: Graph-Based Substructure Pattern Mining, Proceedings of the 2002 IEEE International Conference on Data Mining, p.721, December 09-12, 2002
• 55: Xifeng Yan , Jiawei Han, CloseGraph: mining closed frequent graph patterns, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956784]
• 56: Xifeng Yan , Philip S. Yu , Jiawei Han, Graph indexing: a frequent structure-based approach, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007607]

INDEX TERMS

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

General Terms:
Algorithms, Experimentation

Keywords:
Graph mining, bioinformatics, clique, joint mining