2009 · 238 citations · 42 references
Life SciencesBioinformaticsBiologyComputational BiologyData StructuresGene Regulatory NetworksBiological NetworksGraph AlgorithmsProtein-protein Interaction NetworksGraph IndexingGraph QueryingGraph Similarity SearchIndexing Data StructuresNetwork GraphsRegulatory Gene Networks
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.
42
An Algorithm for Subgraph Isomorphism
J. R. Ullmann · Journal of the ACM · 1976 · 2.3K citations · Full text
gSpan: graph-based substructure pattern mining
Xifeng Yan, Jiawei Han · 2003 · 2K citations
M. Kuramochi, George Karypis · 2002 · 1.1K citations · Full text