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

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 subgr...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Sofie Demeyer, Tom Michoel, Jan Fostier, Pieter Audenaert, Mario Pickavet, Piet Demeester
Formato:	article
Lenguaje:	EN
Publicado:	Public Library of Science (PLoS) 2013
Materias:	Medicine R Science Q
Acceso en línea:	https://doaj.org/article/ad94542584ea4c32af481b9f54acf72b
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:ad94542584ea4c32af481b9f54acf72b
record_format	dspace
spelling	oai:doaj.org-article:ad94542584ea4c32af481b9f54acf72b2021-11-18T07:48:48ZThe index-based subgraph matching algorithm (ISMA): fast subgraph enumeration in large networks using optimized search trees.1932-620310.1371/journal.pone.0061183https://doaj.org/article/ad94542584ea4c32af481b9f54acf72b2013-01-01T00:00:00Zhttps://www.ncbi.nlm.nih.gov/pmc/articles/pmid/23620730/pdf/?tool=EBIhttps://doaj.org/toc/1932-6203Subgraph 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/.Sofie DemeyerTom MichoelJan FostierPieter AudenaertMario PickavetPiet DemeesterPublic Library of Science (PLoS)articleMedicineRScienceQENPLoS ONE, Vol 8, Iss 4, p e61183 (2013)
institution	DOAJ
collection	DOAJ
language	EN
topic	Medicine R Science Q
spellingShingle	Medicine R Science Q Sofie Demeyer Tom Michoel Jan Fostier Pieter Audenaert Mario Pickavet Piet Demeester The index-based subgraph matching algorithm (ISMA): fast subgraph enumeration in large networks using optimized search trees.
description	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/.
format	article
author	Sofie Demeyer Tom Michoel Jan Fostier Pieter Audenaert Mario Pickavet Piet Demeester
author_facet	Sofie Demeyer Tom Michoel Jan Fostier Pieter Audenaert Mario Pickavet Piet Demeester
author_sort	Sofie Demeyer
title	The index-based subgraph matching algorithm (ISMA): fast subgraph enumeration in large networks using optimized search trees.
title_short	The index-based subgraph matching algorithm (ISMA): fast subgraph enumeration in large networks using optimized search trees.
title_full	The index-based subgraph matching algorithm (ISMA): fast subgraph enumeration in large networks using optimized search trees.
title_fullStr	The index-based subgraph matching algorithm (ISMA): fast subgraph enumeration in large networks using optimized search trees.
title_full_unstemmed	The index-based subgraph matching algorithm (ISMA): fast subgraph enumeration in large networks using optimized search trees.
title_sort	index-based subgraph matching algorithm (isma): fast subgraph enumeration in large networks using optimized search trees.
publisher	Public Library of Science (PLoS)
publishDate	2013
url	https://doaj.org/article/ad94542584ea4c32af481b9f54acf72b
work_keys_str_mv	AT sofiedemeyer theindexbasedsubgraphmatchingalgorithmismafastsubgraphenumerationinlargenetworksusingoptimizedsearchtrees AT tommichoel theindexbasedsubgraphmatchingalgorithmismafastsubgraphenumerationinlargenetworksusingoptimizedsearchtrees AT janfostier theindexbasedsubgraphmatchingalgorithmismafastsubgraphenumerationinlargenetworksusingoptimizedsearchtrees AT pieteraudenaert theindexbasedsubgraphmatchingalgorithmismafastsubgraphenumerationinlargenetworksusingoptimizedsearchtrees AT mariopickavet theindexbasedsubgraphmatchingalgorithmismafastsubgraphenumerationinlargenetworksusingoptimizedsearchtrees AT pietdemeester theindexbasedsubgraphmatchingalgorithmismafastsubgraphenumerationinlargenetworksusingoptimizedsearchtrees AT sofiedemeyer indexbasedsubgraphmatchingalgorithmismafastsubgraphenumerationinlargenetworksusingoptimizedsearchtrees AT tommichoel indexbasedsubgraphmatchingalgorithmismafastsubgraphenumerationinlargenetworksusingoptimizedsearchtrees AT janfostier indexbasedsubgraphmatchingalgorithmismafastsubgraphenumerationinlargenetworksusingoptimizedsearchtrees AT pieteraudenaert indexbasedsubgraphmatchingalgorithmismafastsubgraphenumerationinlargenetworksusingoptimizedsearchtrees AT mariopickavet indexbasedsubgraphmatchingalgorithmismafastsubgraphenumerationinlargenetworksusingoptimizedsearchtrees AT pietdemeester indexbasedsubgraphmatchingalgorithmismafastsubgraphenumerationinlargenetworksusingoptimizedsearchtrees
_version_	1718422931770441728

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

Ejemplares similares