GADDI: distance index based subgraph matching in biological networks

ABSTRACT

Currently, a huge amount of biological data can be naturally represented by graphs, e.g., protein interaction networks, gene regulatory networks, etc. The need for indexing large graphs is an urgent research problem of great practical importance. The main challenge is size. Each graph may contain thousands (or more) vertices. Most of the previous work focuses on indexing a set of small or medium sized database graphs (with only tens of vertices) and finding whether a query graph occurs in any of these. In this paper, we are interested in finding all the matches of a query graph in a given large graph of thousands of vertices, which is a very important task in many biological applications. This increases the complexity significantly. We propose a novel distance measurement which reintroduces the idea of frequent substructures in a single large graph. We devise the novel structure distance based approach (GADDI) to efficiently find matches of the query graph. GADDI is further optimized by the use of a dynamic matching scheme to minimize redundant calculations. Last but not least, a number of real and synthetic data sets are used to evaluate the efficiency and scalability of our proposed method.

REFERENCES

• 1: Ricardo A. Baeza-Yates , Berthier Ribeiro-Neto, Modern Information Retrieval, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 2: Bettina Berendt , Andreas Hotho , Gerd Stumme, Towards Semantic Web Mining, Proceedings of the First International Semantic Web Conference on The Semantic Web, p.264-278, June 09-12, 2002
• 3: J. Berg, and M. Lassig, Local graph alignment and motif search in biological networks, PNAS, 2004.
• 4: B. Bringmann, and S. Nijssen: What Is Frequent in a Single Graph? PAKDD 2008.
• 5: James Cheng , Yiping Ke , Wilfred Ng , An Lu, Fg-index: towards verification-free query processing on graph databases, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247574]
• 6: Diane J. Cook , Lawrence B. Holder , Surnjani Djoko, Knowledge discovery from structural data, Journal of Intelligent Information Systems, v.5 n.3, p.229-248, Nov. 1995 [doi>10.1007/BF00962235]
• 7: Luigi P. Cordella , Pasquale Foggia , Carlo Sansone , Mario Vento, A (Sub)Graph Isomorphism Algorithm for Matching Large Graphs, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.26 n.10, p.1367-1372, October 2004 [doi>10.1109/TPAMI.2004.75]
• 8: T. Dandekar, S. Schuster, B. Snel, M. Huynen, and P. Bork, Pathway alignment: application to the comparative analysis of glycolytic enzymes, Biochem, 1999.
• 9: L. Dehaspe, H. Toivonen, and R. King. Finding frequent substructures in chemical compounds. Proc. of KDD, 1998.
• 10: Mukund Deshpande , Michihiro Kuramochi , George Karypis, Frequent Sub-Structure-Based Approaches for Classifying Chemical Compounds, Proceedings of the Third IEEE International Conference on Data Mining, p.35, November 19-22, 2003
• 11: B. Dost, T. Shlomi, N. Gupta, E. Ruppin, V. Bafna, and R. Sharan. QNet: A Tool for Querying Protein Interaction Networks, Proc. of RECOMB, 2007.
• 12: Mathias Fiedler , Christian Borgelt, Subgraph Support in a Single Large Graph, Proceedings of the Seventh IEEE International Conference on Data Mining Workshops, p.399-404, October 28-31, 2007 [doi>10.1109/ICDMW.2007.105]
• 13: Shayan Ghazizadeh , Sudarshan S. Chawathe, SEuS: Structure Extraction Using Summaries, Proceedings of the 5th International Conference on Discovery Science, p.71-85, November 24-26, 2002
• 14: David Gibson , Ravi Kumar , Andrew Tomkins, Discovering large dense subgraphs in massive graphs, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 15: J. Gonzalez, L. Holder, and D. Cook. Application of graph-based concept learning to the predictive toxicology domain. Proc. of the Predictive Toxicology Challenge Workshop, 2001.
• 16: R. Giugno, D. Shasha, GraphGrep:, A Fast and Universal Method for Querying Graphs. Proc. of ICPR, 2002.
• 17: Huahai He , Ambuj K. Singh, Closure-Tree: An Index Structure for Graph Queries, Proceedings of the 22nd International Conference on Data Engineering, p.38, April 03-07, 2006 [doi>10.1109/ICDE.2006.37]
• 18: Huahai He , Ambuj K. Singh, Graphs-at-a-time: query language and access methods for graph databases, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376660]
• 19: 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]
• 20: 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
• 21: 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
• 22: D. Jensen, and H. Goldberg. Artificial Intelligence and Link Analysis. AAAI Press, 1998.
• 23: H. Jiang, H. Wang, P. Yu, and S. Zhou. Gstring: A novel approach for efficient search in graph databases. Proc. of ICDE, 2007.
• 24: Yiping Ke , James Cheng , Wilfred Ng, Correlation search in graph databases, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA [doi>10.1145/1281192.1281236]
• 25: J. Kleinberg, R. Kumar, P. Raghavan, S. Rajagopalan, and A. Tomkins. The Web as a graph: Measurements, models and methods. Lecture Notes in Computer Science, 1999.
• 26: Calvin Ko, Logic Induction of Valid Behavior Specifications for Intrusion Detection, Proceedings of the 2000 IEEE Symposium on Security and Privacy, p.142, May 14-17, 2000
• 27: Mehmet Koyutürk , Ananth Grama , Wojciech Szpankowski, An efficient algorithm for detecting frequent subgraphs in biological networks, Bioinformatics, v.20 n.1, p.200-207, January 2004 [doi>10.1093/bioinformatics/bth919]
• 28: M. Koyuturk, A. Grama, and W. Szpankowski. Pairwise Local Alignment of Protein Interaction Networks Guided by Models of Evolution. RECOMB 2005.
• 29: M. Koyuturk, Y. Kim, U. Topkara, S. Subramaniam, W. Szpankowski, and A. Grama. Pairwise Alignment of Protein Interaction Networks, RECOMB 2005.
• 30: Stefan Kramer , Luc De Raedt , Christoph Helma, Molecular feature mining in HIV data, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.136-143, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502533]
• 31: M. Kuramochi, and G. Karypis. Frequent subgraph discovery. Proc. of ICDE, 2001.
• 32: Michihiro Kuramochi , George Karypis, Finding Frequent Patterns in a Large Sparse Graph*, Data Mining and Knowledge Discovery, v.11 n.3, p.243-271, November 2005 [doi>10.1007/s10618-005-0003-9]
• 33: Wenke Lee , Salvatore J. Stolfo, A framework for constructing features and models for intrusion detection systems, ACM Transactions on Information and System Security (TISSEC), v.3 n.4, p.227-261, Nov. 2000 [doi>10.1145/382912.382914]
• 34: R. Mooney, P. Melville, L. Tang, J. Shavlik, I. Castro Dutra, and D. Page. Relational data mining with inductive logic programming for link discovery. AAAI Press/The MIT Press, 2004.
• 35: Siegfried Nijssen , Joost N. Kok, A quickstart in frequent structure mining can make a difference, 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.1014134]
• 36: 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]
• 37: Ron Y. Pinter , Oleg Rokhlenko , Esti Yeger-Lotem , Michal Ziv-Ukelson, Alignment of metabolic pathways, Bioinformatics, v.21 n.16, p.3401-3408, August 2005 [doi>10.1093/bioinformatics/bti554]
• 38: Dennis Shasha , Jason T. L. Wang , Rosalba Giugno, Algorithmics and applications of tree and graph searching, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin [doi>10.1145/543613.543620]
• 39: R. Singh, J. Xu, and B. Berger. Pairwise Global Alignment of Protein Interaction Networks by Matching Neighborhood Topology, RECOMB 07'.
• 40: Y. Tian and J. Patel. TALE: A Tool for Approximate Large Graph Matching, Proc. of ICDE, 2008.
• 41: J. R. Ullmann, An Algorithm for Subgraph Isomorphism, Journal of the ACM (JACM), v.23 n.1, p.31-42, Jan. 1976 [doi>10.1145/321921.321925]
• 42: N. Vanetik , E. Gudes , S. E. Shimony, Computing Frequent Graph Patterns from Semistructured Data, Proceedings of the 2002 IEEE International Conference on Data Mining, p.458, December 09-12, 2002
• 43: S. Wasserman, K. Faust, and D. Iacobucci. Social network analysis: Methods and applications. Cambridge University Press, 1994.
• 44: D. Williams, J. Huan, and W. Wang. Graph database indexing using structured graph decomposition. Proc. of ICDE, 2007.
• 45: 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
• 46: 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]
• 47: Xifeng Yan , Philip S. Yu , Jiawei Han, Substructure similarity search in graph databases, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066244]
• 48: Xifeng Yan , Feida Zhu , Jiawei Han , Philip S. Yu, Searching Substructures with Superimposed Distance, Proceedings of the 22nd International Conference on Data Engineering, p.88, April 03-07, 2006 [doi>10.1109/ICDE.2006.136]
• 49: Ken'ichi Yoshida , Hiroshi Motoda, CLIP: concept learning from inference patterns, Artificial Intelligence, v.75 n.1, p.63-92, May 1995 [doi>10.1016/0004-3702(94)00066-A]
• 50: K. Yoshida, H. Motoda, and N. Indurkhya, Graph-based induction as a unified learning framework. Journal of Applied Intelligence, 1994.
• 51: S. Zhang, M. Hu, and J. Yang. Treepi: a new graph indexing method. Proc. of ICDE, 2007.
• 52: Peixiang Zhao , Jeffrey Xu Yu , Philip S. Yu, Graph indexing: tree + delta <= graph, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 53: Lei Zou , Lei Chen , Jeffrey Xu Yu , Yansheng Lu, A novel spectral coding in a large graph database, Proceedings of the 11th international conference on Extending database technology: Advances in database technology, March 25-29, 2008, Nantes, France [doi>10.1145/1353343.1353369]
• 54: Gene Ontology. http://www.geneontology.org/.
• 55: Social Network. http://www-personal.umich.edu/mejn/netdata/.