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

      Detection of Network Motif Based on a Novel Graph Canonization Algorithm from Transcriptional Regulation Networks

      research-article

      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

          Network motifs are patterns of complex networks occurring significantly more frequently than those in random networks. They have been considered as fundamental building blocks of complex networks. Therefore, the detection of network motifs in transcriptional regulation networks is a crucial step in understanding the mechanism of transcriptional regulation and network evolution. The search for network motifs is similar to solving subgraph searching problems, which has proven to be NP-complete. To quickly and effectively count subgraphs of a large biological network, we propose a novel graph canonization algorithm based on resolving sets. This method has been implemented in a command line interface (CLI) program sgip using the SeqAn library. Comparing to Babai’s algorithm, this approach has a tighter complexity bound, o ( exp ( n log 2 n + 4 log n ) ) , on strongly regular graphs. Results on several simulated datasets and transcriptional regulation networks indicate that sgip outperforms nauty on many graph cases. The source code of sgip is freely accessible in https://github.com/seqan/seqan/tree/master/apps/sgip and the binary code in http://packages.seqan.de/sgip/.

          Related collections

          Most cited references29

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

          Network motifs in the transcriptional regulation network of Escherichia coli

          Little is known about the design principles of transcriptional regulation networks that control gene expression in cells. Recent advances in data collection and analysis, however, are generating unprecedented amounts of information about gene regulation networks. To understand these complex wiring diagrams, we sought to break down such networks into basic building blocks. We generalize the notion of motifs, widely used for sequence analysis, to the level of networks. We define 'network motifs' as patterns of interconnections that recur in many different parts of a network at frequencies much higher than those found in randomized networks. We applied new algorithms for systematically detecting network motifs to one of the best-characterized regulation networks, that of direct transcriptional interactions in Escherichia coli. We find that much of the network is composed of repeated appearances of three highly significant motifs. Each network motif has a specific function in determining gene expression, such as generating temporal expression programs and governing the responses to fluctuating external signals. The motif structure also allows an easily interpretable view of the entire known transcriptional network of the organism. This approach may help define the basic computational elements of other biological networks.
            Bookmark
            • Record: found
            • Abstract: not found
            • Article: not found

            An Algorithm for Subgraph Isomorphism

              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

                Author and article information

                Journal
                Molecules
                Molecules
                molecules
                Molecules : A Journal of Synthetic Chemistry and Natural Product Chemistry
                MDPI
                1420-3049
                10 December 2017
                December 2017
                : 22
                : 12
                : 2194
                Affiliations
                [1 ]School of Computer Science, Northwestern Polytechnical University, West Youyi Road 127, Xi’an 710072, China; shang@ 123456nwpu.edu.cn
                [2 ]Centre for Multidisciplinary Convergence Computing, School of Computer Science, Northwestern Polytechnical University, Dong Xiang Road 1, Xi’an 710129, China
                Author notes
                [* ]Correspondence: jhu@ 123456nwpu.edu.cn ; Tel.: +86-29-8843-1519
                Article
                molecules-22-02194
                10.3390/molecules22122194
                6150038
                29232861
                7dcf3fcb-f49d-4799-9e0c-04aa996a3baa
                © 2017 by the authors.

                Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license ( http://creativecommons.org/licenses/by/4.0/).

                History
                : 04 November 2017
                : 05 December 2017
                Categories
                Article

                network motif,algorithms,graph canonization
                network motif, algorithms, graph canonization

                Comments

                Comment on this article