• The index-based subgraph match...

Result: The index-based subgraph matching algorithm (ISMA): fast subgraph enumeration in large networks using optimized search trees.

Title:
The index-based subgraph matching algorithm (ISMA): fast subgraph enumeration in large networks using optimized search trees.
Authors:
Demeyer S; Department of Information Technology, Ghent University, Ghent, Belgium. Sofie.Demeyer@intec.ugent.be, Michoel T, Fostier J, Audenaert P, Pickavet M, Demeester P
Source:
PloS one [PLoS One] 2013 Apr 19; Vol. 8 (4), pp. e61183. Date of Electronic Publication: 2013 Apr 19 (Print Publication: 2013).
Publication Type:
Journal Article; Research Support, Non-U.S. Gov't
Language:
English
Journal Info:
Publisher: Public Library of Science Country of Publication: United States NLM ID: 101285081 Publication Model: Electronic-Print Cited Medium: Internet ISSN: 1932-6203 (Electronic) Linking ISSN: 19326203 NLM ISO Abbreviation: PLoS One Subsets: MEDLINE
Imprint Name(s):
Original Publication: San Francisco, CA : Public Library of Science
MeSH Terms:
Algorithms* , Signal Transduction*, Software ; Time Factors
References:
Genes Dev. 2007 May 1;21(9):1010-24. (PMID: 17473168)
Phys Rev E Stat Nonlin Soft Matter Phys. 2004 Sep;70(3 Pt 1):031909. (PMID: 15524551)
Nat Rev Genet. 2007 Jun;8(6):450-61. (PMID: 17510665)
Nucleic Acids Res. 2006 Jan 1;34(Database issue):D535-9. (PMID: 16381927)
Mol Biosyst. 2011 Oct;7(10):2769-78. (PMID: 21860879)
Nucleic Acids Res. 2008 Jan;36(Database issue):D263-6. (PMID: 18055500)
IEEE Trans Pattern Anal Mach Intell. 2004 Oct;26(10):1367-72. (PMID: 15641723)
Science. 2010 May 21;328(5981):1043-6. (PMID: 20489023)
Genome Biol. 2006;7(7):R55. (PMID: 16859507)
Bioinformatics. 2011 Jun 1;27(11):1587-8. (PMID: 21478195)
Proc Natl Acad Sci U S A. 2004 Apr 20;101(16):5934-9. (PMID: 15079056)
Bioinformatics. 2007 Jan 15;23(2):232-9. (PMID: 17110368)
Science. 2002 Oct 25;298(5594):824-7. (PMID: 12399590)
Cell. 2009 Mar 6;136(5):952-63. (PMID: 19269370)
Genome Res. 2004 Jun;14(6):1107-18. (PMID: 15173116)
BMC Bioinformatics. 2004 Jan 30;5:10. (PMID: 15018656)
Science. 2009 Jul 24;325(5939):405. (PMID: 19628849)
Nucleic Acids Res. 2009 Jan;37(Database issue):D412-6. (PMID: 18940858)
Grant Information:
BBS/E/D/20211552 United Kingdom BB_ Biotechnology and Biological Sciences Research Council
Entry Date(s):
Date Created: 20130427 Date Completed: 20131111 Latest Revision: 20250529
Update Code:
20250530
PubMed Central ID:
PMC3631255
DOI:
10.1371/journal.pone.0061183
PMID:
23620730
Database:
MEDLINE

Further Information

Subgraph matching algorithms are designed to find all instances of predefined subgraphs in a large graph or network and play an important role in the discovery and analysis of so-called network motifs, subgraph patterns which occur more often than expected by chance. We present the index-based subgraph matching algorithm (ISMA), a novel tree-based algorithm. ISMA realizes a speedup compared to existing algorithms by carefully selecting the order in which the nodes of a query subgraph are investigated. In order to achieve this, we developed a number of data structures and maximally exploited symmetry characteristics of the subgraph. We compared ISMA to a naive recursive tree-based algorithm and to a number of well-known subgraph matching algorithms. Our algorithm outperforms the other algorithms, especially on large networks and with large query subgraphs. An implementation of ISMA in Java is freely available at http://sourceforge.net/projects/isma/.