The Index-based Subgraph Matching Algorithm with General Symmetries (ISMAGS): exploiting symmetry for faster subgraph enumeration.

Subgraph matching algorithms are used to find and enumerate specific interconnection structures in networks. By enumerating these specific structures/subgraphs, the fundamental properties of the network can be derived. More specifically in biological networks, subgraph matching algorithms are used t...

Descripción completa

Guardado en:

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

id	oai:doaj.org-article:acf55fd884a3421096d6705bdbfcf37b
record_format	dspace
spelling	oai:doaj.org-article:acf55fd884a3421096d6705bdbfcf37b2021-11-18T08:17:45ZThe Index-based Subgraph Matching Algorithm with General Symmetries (ISMAGS): exploiting symmetry for faster subgraph enumeration.1932-620310.1371/journal.pone.0097896https://doaj.org/article/acf55fd884a3421096d6705bdbfcf37b2014-01-01T00:00:00Zhttps://www.ncbi.nlm.nih.gov/pmc/articles/pmid/24879305/pdf/?tool=EBIhttps://doaj.org/toc/1932-6203Subgraph matching algorithms are used to find and enumerate specific interconnection structures in networks. By enumerating these specific structures/subgraphs, the fundamental properties of the network can be derived. More specifically in biological networks, subgraph matching algorithms are used to discover network motifs, specific patterns occurring more often than expected by chance. Finding these network motifs yields information on the underlying biological relations modelled by the network. In this work, we present the Index-based Subgraph Matching Algorithm with General Symmetries (ISMAGS), an improved version of the Index-based Subgraph Matching Algorithm (ISMA). ISMA quickly finds all instances of a predefined motif in a network by intelligently exploring the search space and taking into account easily identifiable symmetric structures. However, more complex symmetries (possibly involving switching multiple nodes) are not taken into account, resulting in superfluous output. ISMAGS overcomes this problem by using a customised symmetry analysis phase to detect all symmetric structures in the network motif subgraphs. These structures are then converted to symmetry-breaking constraints used to prune the search space and speed up calculations. The performance of the algorithm was tested on several types of networks (biological, social and computer networks) for various subgraphs with a varying degree of symmetry. For subgraphs with complex (multi-node) symmetric structures, high speed-up factors are obtained as the search space is pruned by the symmetry-breaking constraints. For subgraphs with no or simple symmetric structures, ISMAGS still reduces computation times by optimising set operations. Moreover, the calculated list of subgraph instances is minimal as it contains no instances that differ by only a subgraph symmetry. An implementation of the algorithm is freely available at https://github.com/mhoubraken/ISMAGS.Maarten HoubrakenSofie DemeyerTom MichoelPieter AudenaertDidier ColleMario PickavetPublic Library of Science (PLoS)articleMedicineRScienceQENPLoS ONE, Vol 9, Iss 5, p e97896 (2014)
institution	DOAJ
collection	DOAJ
language	EN
topic	Medicine R Science Q
spellingShingle	Medicine R Science Q Maarten Houbraken Sofie Demeyer Tom Michoel Pieter Audenaert Didier Colle Mario Pickavet The Index-based Subgraph Matching Algorithm with General Symmetries (ISMAGS): exploiting symmetry for faster subgraph enumeration.
description	Subgraph matching algorithms are used to find and enumerate specific interconnection structures in networks. By enumerating these specific structures/subgraphs, the fundamental properties of the network can be derived. More specifically in biological networks, subgraph matching algorithms are used to discover network motifs, specific patterns occurring more often than expected by chance. Finding these network motifs yields information on the underlying biological relations modelled by the network. In this work, we present the Index-based Subgraph Matching Algorithm with General Symmetries (ISMAGS), an improved version of the Index-based Subgraph Matching Algorithm (ISMA). ISMA quickly finds all instances of a predefined motif in a network by intelligently exploring the search space and taking into account easily identifiable symmetric structures. However, more complex symmetries (possibly involving switching multiple nodes) are not taken into account, resulting in superfluous output. ISMAGS overcomes this problem by using a customised symmetry analysis phase to detect all symmetric structures in the network motif subgraphs. These structures are then converted to symmetry-breaking constraints used to prune the search space and speed up calculations. The performance of the algorithm was tested on several types of networks (biological, social and computer networks) for various subgraphs with a varying degree of symmetry. For subgraphs with complex (multi-node) symmetric structures, high speed-up factors are obtained as the search space is pruned by the symmetry-breaking constraints. For subgraphs with no or simple symmetric structures, ISMAGS still reduces computation times by optimising set operations. Moreover, the calculated list of subgraph instances is minimal as it contains no instances that differ by only a subgraph symmetry. An implementation of the algorithm is freely available at https://github.com/mhoubraken/ISMAGS.
format	article
author	Maarten Houbraken Sofie Demeyer Tom Michoel Pieter Audenaert Didier Colle Mario Pickavet
author_facet	Maarten Houbraken Sofie Demeyer Tom Michoel Pieter Audenaert Didier Colle Mario Pickavet
author_sort	Maarten Houbraken
title	The Index-based Subgraph Matching Algorithm with General Symmetries (ISMAGS): exploiting symmetry for faster subgraph enumeration.
title_short	The Index-based Subgraph Matching Algorithm with General Symmetries (ISMAGS): exploiting symmetry for faster subgraph enumeration.
title_full	The Index-based Subgraph Matching Algorithm with General Symmetries (ISMAGS): exploiting symmetry for faster subgraph enumeration.
title_fullStr	The Index-based Subgraph Matching Algorithm with General Symmetries (ISMAGS): exploiting symmetry for faster subgraph enumeration.
title_full_unstemmed	The Index-based Subgraph Matching Algorithm with General Symmetries (ISMAGS): exploiting symmetry for faster subgraph enumeration.
title_sort	index-based subgraph matching algorithm with general symmetries (ismags): exploiting symmetry for faster subgraph enumeration.
publisher	Public Library of Science (PLoS)
publishDate	2014
url	https://doaj.org/article/acf55fd884a3421096d6705bdbfcf37b
work_keys_str_mv	AT maartenhoubraken theindexbasedsubgraphmatchingalgorithmwithgeneralsymmetriesismagsexploitingsymmetryforfastersubgraphenumeration AT sofiedemeyer theindexbasedsubgraphmatchingalgorithmwithgeneralsymmetriesismagsexploitingsymmetryforfastersubgraphenumeration AT tommichoel theindexbasedsubgraphmatchingalgorithmwithgeneralsymmetriesismagsexploitingsymmetryforfastersubgraphenumeration AT pieteraudenaert theindexbasedsubgraphmatchingalgorithmwithgeneralsymmetriesismagsexploitingsymmetryforfastersubgraphenumeration AT didiercolle theindexbasedsubgraphmatchingalgorithmwithgeneralsymmetriesismagsexploitingsymmetryforfastersubgraphenumeration AT mariopickavet theindexbasedsubgraphmatchingalgorithmwithgeneralsymmetriesismagsexploitingsymmetryforfastersubgraphenumeration AT maartenhoubraken indexbasedsubgraphmatchingalgorithmwithgeneralsymmetriesismagsexploitingsymmetryforfastersubgraphenumeration AT sofiedemeyer indexbasedsubgraphmatchingalgorithmwithgeneralsymmetriesismagsexploitingsymmetryforfastersubgraphenumeration AT tommichoel indexbasedsubgraphmatchingalgorithmwithgeneralsymmetriesismagsexploitingsymmetryforfastersubgraphenumeration AT pieteraudenaert indexbasedsubgraphmatchingalgorithmwithgeneralsymmetriesismagsexploitingsymmetryforfastersubgraphenumeration AT didiercolle indexbasedsubgraphmatchingalgorithmwithgeneralsymmetriesismagsexploitingsymmetryforfastersubgraphenumeration AT mariopickavet indexbasedsubgraphmatchingalgorithmwithgeneralsymmetriesismagsexploitingsymmetryforfastersubgraphenumeration
_version_	1718421942788161536

The Index-based Subgraph Matching Algorithm with General Symmetries (ISMAGS): exploiting symmetry for faster subgraph enumeration.

Ejemplares similares