Detection of network motif based on a novel graph canonization algorithm from transcriptional regulation networks

Jialu Hu, Xuequn Shang

Research output: Contribution to journalArticlepeer-review

19 Scopus citations

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 log2 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/.

Original languageEnglish
Article number2194
JournalMolecules
Volume22
Issue number12
DOIs
StatePublished - Dec 2017

Keywords

  • Algorithms
  • Graph canonization
  • Network motif

Fingerprint

Dive into the research topics of 'Detection of network motif based on a novel graph canonization algorithm from transcriptional regulation networks'. Together they form a unique fingerprint.

Cite this