SING: Subgraph search In Non-homogeneous Graphs

BMC Bioinformatics

Methodology Article

Dennis Shasha¹  Rosalba Giugno²  Raffaele Di Natale²  Alfredo Ferro²  Misael Mongiovì²  Alfredo Pulvirenti² 

[1] Courant Institute of Mathematical Sciences, New York University, New York, USA;Dipartimento di Matematica ed Informatica, Università di Catania, Catania, Italy;

关键词: Query Time;    Large Graph;    Subgraph Isomorphism;    Graph Signature;    Query Graph;   

DOI  :  10.1186/1471-2105-11-96

 received in 2009-07-29, accepted in 2010-02-19,  发布年份 2010

来源: Springer

【 摘 要 】

BackgroundFinding the subgraphs of a graph database that are isomorphic to a given query graph has practical applications in several fields, from cheminformatics to image understanding. Since subgraph isomorphism is a computationally hard problem, indexing techniques have been intensively exploited to speed up the process. Such systems filter out those graphs which cannot contain the query, and apply a subgraph isomorphism algorithm to each residual candidate graph. The applicability of such systems is limited to databases of small graphs, because their filtering power degrades on large graphs.ResultsIn this paper, SING (Subgraph search In Non-homogeneous Graphs), a novel indexing system able to cope with large graphs, is presented. The method uses the notion of feature, which can be a small subgraph, subtree or path. Each graph in the database is annotated with the set of all its features. The key point is to make use of feature locality information. This idea is used to both improve the filtering performance and speed up the subgraph isomorphism task.ConclusionsExtensive tests on chemical compounds, biological networks and synthetic graphs show that the proposed system outperforms the most popular systems in query time over databases of medium and large graphs. Other specific tests show that the proposed system is effective for single large graphs.

【 授权许可】

Unknown   
© Di Natale et al; licensee BioMed Central Ltd. 2010. This article is published under license to BioMed Central Ltd. This is an Open Access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/2.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.