Advanced search
1 file | 418.70 KB

The index-based subgraph matching algorithm with general symmetries (ISMAGS): exploiting symmetry for faster subgraph enumeration

Maarten Houbraken (UGent) , Sofie Demeyer (UGent) , Tom Michoel (UGent) , Pieter Audenaert (UGent) , Didier Colle (UGent) and Mario Pickavet (UGent)
(2014) PLOS ONE. 9(5).
Author
Organization
Project
Bioinformatics: from nucleotids to networks (N2N)
Abstract
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.
Keywords
NETWORK MOTIFS, ISOMORPHISM, IBCN

Downloads

  • 5966.pdf
    • full text
    • |
    • open access
    • |
    • PDF
    • |
    • 418.70 KB

Citation

Please use this url to cite or link to this publication:

Chicago
Houbraken, Maarten, Sofie Demeyer, Tom Michoel, Pieter Audenaert, Didier Colle, and Mario Pickavet. 2014. “The Index-based Subgraph Matching Algorithm with General Symmetries (ISMAGS): Exploiting Symmetry for Faster Subgraph Enumeration.” Plos One 9 (5).
APA
Houbraken, Maarten, Demeyer, S., Michoel, T., Audenaert, P., Colle, D., & Pickavet, M. (2014). The index-based subgraph matching algorithm with general symmetries (ISMAGS): exploiting symmetry for faster subgraph enumeration. PLOS ONE, 9(5).
Vancouver
1.
Houbraken M, Demeyer S, Michoel T, Audenaert P, Colle D, Pickavet M. The index-based subgraph matching algorithm with general symmetries (ISMAGS): exploiting symmetry for faster subgraph enumeration. PLOS ONE. 2014;9(5).
MLA
Houbraken, Maarten, Sofie Demeyer, Tom Michoel, et al. “The Index-based Subgraph Matching Algorithm with General Symmetries (ISMAGS): Exploiting Symmetry for Faster Subgraph Enumeration.” PLOS ONE 9.5 (2014): n. pag. Print.
@article{5704541,
  abstract     = {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.},
  articleno    = {e97896},
  author       = {Houbraken, Maarten and Demeyer, Sofie and Michoel, Tom and Audenaert, Pieter and Colle, Didier and Pickavet, Mario},
  issn         = {1932-6203},
  journal      = {PLOS ONE},
  keyword      = {NETWORK MOTIFS,ISOMORPHISM,IBCN},
  language     = {eng},
  number       = {5},
  pages        = {15},
  title        = {The index-based subgraph matching algorithm with general symmetries (ISMAGS): exploiting symmetry for faster subgraph enumeration},
  url          = {http://dx.doi.org/10.1371/journal.pone.0097896},
  volume       = {9},
  year         = {2014},
}

Altmetric
View in Altmetric
Web of Science
Times cited: