Finding Frequent Patterns in Biological Networks


  • Rahul Rane
  • Praveen Kaushik





MCMC, Network motifs, Sampling algorithms.


Frequent patterns help to discover the structural behavior of the complex biological network. The networks which show same global structure may have different local structure. The patterns are the actual fingerprints of the network. The pattern frequency and its significance carries very important functionality to classify and cluster the biological network. The sheer number of patterns get generated while traversing the network. Counting these patterns and determining their frequencies in the large biological network is very challenging and computationally expensive task. Previously proposed methods are bound by the size of patterns and networks size. By using approximation method like sampling, we proposed an algorithm. The results show the proposed algorithm is faster than existing algorithms. Also, the error rate is minimum, which makes the proposed method more reliable.




[1] Albert, István, and Réka Albert. "Conserved network motifs allow protein–protein interaction prediction." Bioinformatics 20.18 (2004): 3346-3352.

[2] Callebaut, Werner. "Scientific perspectivism: a philosopher of science’s response to the challenge of big data biology." Studies in History and Philosophy of Science Part C: Studies in History and Philosophy of Biological and Biomedical Sciences 43.1 (2012): 69-80.

[3] Chen, Jin, et al. "Labeling network motifs in protein interactomes for protein function prediction." Data Engineering, 2007. ICDE 2007. IEEE 23rd International Conference on. IEEE, 2007.

[4] Kim, Wooyoung, and Lynnette Haukap. "NemoProfile as an efficient approach to network motif analysis with instance collection." BMC bioinformatics 18.12 (2017): 423.

[5] Milenković, Tijana, and Nataša Pržulj. "Uncovering biological network function via graphlet degree signatures." Cancer informatics 6 (2008): CIN-S680.

[6] Milo, Ron, et al. "Network motifs: simple building blocks of complex networks." Science 298.5594 (2002): 824-827.

[7] Saha, Tanay Kumar, and Mohammad Al Hasan. "Finding network motifs using MCMC sampling." Complex Networks VI. Springer, Cham, 2015. 13-24.

[8] Milo, Ron, et al. "Superfamilies of evolved and designed networks." Science 303.5663 (2004): 1538-1542.

[9] Kim, Wooyoung, et al. "Essential protein discovery based on network motif and gene ontology." Bioinformatics and Biomedicine (BIBM), 2011 IEEE International Conference on. IEEE, 2011.

[10] Kim, Wooyoung, et al. "Biological network motif detection and evaluation." BMC systems biology 5.3 (2011): S5.

[11] Farina, Lorenzo, et al. "Identification of regulatory network motifs from gene expression data." Journal of Mathematical Modelling and Algorithms 9.3 (2010): 233-245.

[12] Kashtan, Nadav, et al. "Efficient sampling algorithm for estimating subgraph concentrations and detecting network motifs." Bioinformatics 20.11 (2004): 1746-1758.

[13] Wernicke, Sebastian, and Florian Rasche. "FANMOD: a tool for fast network motif detection." Bioinformatics 22.9 (2006): 1152-1153.

[14] Kashani, Zahra Razaghi Moghadam, et al. "Kavosh: a new algorithm for finding network motifs." BMC bioinformatics 10.1 (2009): 318.

[15] Li, Xin, et al. "Netmode: Network motif detection without nauty." PloS one 7.12 (2012): e50093.

[16] Bhuiyan, Mansurul A., Mahmudur Rahman, and M. Al Hasan. "Guise: Uniform sampling of graphlets for large graph analysis." Data Mining (ICDM), 2012 IEEE 12th International Conference on. IEEE, 2012.

[17] Yan, Xifeng, and Jiawei Han. "gspan: Graph-based substructure pattern mining." Data Mining, 2002. ICDM 2003. Proceedings. 2002 IEEE International Conference on. IEEE, 2002.

[18] Xenarios, Ioannis, et al. "DIP, the Database of Interacting Proteins: a research tool for studying cellular networks of protein interactions." Nucleic acids research 30.1 (2002): 303-305.

[19] Omidi, Saeed, Falk Schreiber, and Ali Masoudi-Nejad. "MODA: an efficient algorithm for network motif discovery in biological networks." Genes & genetic systems 84.5 (2009): 385-395.

View Full Article: