Blog
About

24
views
0
recommends
+1 Recommend
0 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      A subgraph isomorphism algorithm and its application to biochemical data

      1 , , 2 , 2 , 3 , 2

      BMC Bioinformatics

      BioMed Central

      Ninth Annual Meeting of the Italian Society of Bioinformatics (BITS)

      2-4 May 2012

      Subgraph isomorphism algorithms, biochemical graph data, search strategies, algorithms comparisons and distributions

      Read this article at

      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          Abstract

          Background

          Graphs can represent biological networks at the molecular, protein, or species level. An important query is to find all matches of a pattern graph to a target graph. Accomplishing this is inherently difficult (NP-complete) and the efficiency of heuristic algorithms for the problem may depend upon the input graphs. The common aim of existing algorithms is to eliminate unsuccessful mappings as early as and as inexpensively as possible.

          Results

          We propose a new subgraph isomorphism algorithm which applies a search strategy to significantly reduce the search space without using any complex pruning rules or domain reduction procedures. We compare our method with the most recent and efficient subgraph isomorphism algorithms (VFlib, LAD, and our C++ implementation of FocusSearch which was originally distributed in Modula2) on synthetic, molecules, and interaction networks data. We show a significant reduction in the running time of our approach compared with these other excellent methods and show that our algorithm scales well as memory demands increase.

          Conclusions

          Subgraph isomorphism algorithms are intensively used by biochemical tools. Our analysis gives a comprehensive comparison of different software approaches to subgraph isomorphism highlighting their weaknesses and strengths. This will help researchers make a rational choice among methods depending on their application. We also distribute an open-source package including our system and our own C++ implementation of FocusSearch together with all the used datasets ( http://ferrolab.dmi.unict.it/ri.html). In future work, our findings may be extended to approximate subgraph isomorphism algorithms.

          Related collections

          Most cited references 14

          • Record: found
          • Abstract: not found
          • Article: not found

          An Algorithm for Subgraph Isomorphism

           J. R. Ullmann (1976)
            Bookmark
            • Record: found
            • Abstract: found
            • Article: not found

            FANMOD: a tool for fast network motif detection.

            Motifs are small connected subnetworks that a network displays in significantly higher frequencies than would be expected for a random network. They have recently gathered much attention as a concept to uncover structural design principles of complex biological networks. FANMOD is a tool for fast network motif detection; it relies on recently developed algorithms to improve the efficiency of network motif detection by some orders of magnitude over existing tools. This facilitates the detection of larger motifs in bigger networks than previously possible. Additional benefits of FANMOD are the ability to analyze colored networks, a graphical user interface and the ability to export results to a variety of machine- and human-readable file formats including comma-separated values and HTML.
              Bookmark
              • Record: found
              • Abstract: found
              • Article: not found

              A (sub)graph isomorphism algorithm for matching large graphs.

              We present an algorithm for graph isomorphism and subgraph isomorphism suited for dealing with large graphs. A first version of the algorithm has been presented in a previous paper, where we examined its performance for the isomorphism of small and medium size graphs. The algorithm is improved here to reduce its spatial complexity and to achieve a better performance on large graphs; its features are analyzed in detail with special reference to time and memory requirements. The results of a testing performed on a publicly available database of synthetically generated graphs and on graphs relative to a real application dealing with technical drawings are presented, confirming the effectiveness of the approach, especially when working with large graphs.
                Bookmark

                Author and article information

                Conference
                BMC Bioinformatics
                BMC Bioinformatics
                BMC Bioinformatics
                BioMed Central
                1471-2105
                2013
                22 April 2013
                : 14
                : Suppl 7
                : S13
                Affiliations
                [1 ]Dept. Computer Science - University of Verona, Verona, 37134, Italy
                [2 ]Dept. Clinical and Molecular Biomedicine - University of Catania, Catania, 95125, Italy
                [3 ]Courant Institute of Mathematical Sciences - New York University, NY 10012, USA
                Article
                1471-2105-14-S7-S13
                10.1186/1471-2105-14-S7-S13
                3633016
                23815292
                Copyright ©2013 Bonnici et al.; licensee BioMed Central Ltd.

                This is an open access article distributed under the terms of the Creative Commons Attribution License ( http://creativecommons.org/licenses/by/2.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

                Ninth Annual Meeting of the Italian Society of Bioinformatics (BITS)
                Catania, Sicily
                2-4 May 2012
                Categories
                Research

                Comments

                Comment on this article