More specifically in biology, graphs are very well suited to model interactions between different proteins. By interpreting the systems as graphs of interconnected components, a vast array of network processing methods enables detailed analysis of the underlying, fundamental properties. To understand their internal dynamics, many of these systems can be modelled using graph theory. In modern society, technology has been applied to create and study numerous advanced systems in various fields as biology, sociology, informatics and others. The funders had no role in study design, data collection and analysis, decision to publish, or preparation of the manuscript.Ĭompeting interests: The authors have declared that no competing interests exist. This is an open-access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.įunding: Funded by the Research Foundation - Flanders (FWO-Vlaanderen), Ghent University and the Roslin Institute. Received: DecemAccepted: ApPublished: May 30, 2014Ĭopyright: © 2014 Houbraken et al.
PLoS ONE 9(5):Įditor: Peter Csermely, Semmelweis University, Hungary Ĭitation: Houbraken M, 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. An implementation of the algorithm is freely available at. Moreover, the calculated list of subgraph instances is minimal as it contains no instances that differ by only a subgraph symmetry. For subgraphs with no or simple symmetric structures, ISMAGS still reduces computation times by optimising set operations. 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. 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. These structures are then converted to symmetry-breaking constraints used to prune the search space and speed up calculations. ISMAGS overcomes this problem by using a customised symmetry analysis phase to detect all symmetric structures in the network motif subgraphs. However, more complex symmetries (possibly involving switching multiple nodes) are not taken into account, resulting in superfluous output. 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.
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). Finding these network motifs yields information on the underlying biological relations modelled by the network. More specifically in biological networks, subgraph matching algorithms are used to discover network motifs, specific patterns occurring more often than expected by chance. By enumerating these specific structures/subgraphs, the fundamental properties of the network can be derived. Subgraph matching algorithms are used to find and enumerate specific interconnection structures in networks.