Parallel network motif search using message passing approach for biological complex networks

HIMANSHU; A BANDYOPADHYAY; SARIKA JAIN

doi:10.56093/ijans.v87i9.74339

Authors

HIMANSHU Amity Institute of Information Technology, Amity University, Noida, Uttar Pradesh 201 313 India
A BANDYOPADHYAY Amity Institute of Information Technology, Amity University, Noida, Uttar Pradesh 201 313 India
SARIKA JAIN Amity Institute of Information Technology, Amity University, Noida, Uttar Pradesh 201 313 India

https://doi.org/10.56093/ijans.v87i9.74339

Keywords:

Complex networks, Data structures, HPC, MPI, Network motif search, Parallelization

Abstract

Study of complex biological networks is essential for understanding their functional characteristics. Network motifs have functional significance in biological networks as they represent building blocks of these networks. This study evaluates master-worker parallelization approach on sequential PATRICIA trie based fast network motif search algorithm for distributed memory model based High Performance Clusters (HPCs). Proposed algorithm uses PATRICIA trie for data compression during census of subgraphs based upon ESU algorithm. Parallel implementation was done using MPI and C language. We applied proposed parallel algorithm to three real networks viz. networks of metabolic pathway of E.coli, electronic and social networks. PATRICIA based parallel approach was able to achieve speedup of 50.75, 49.37, 38.07 as analysed on 101 cores on networks of metabolic pathway of E.coli, electronic and social networks respectively for large motifs of size 9 for E.coli, social and 10 for electronic networks over the PATRICIA trie based sequential algorithm.

Downloads

Download data is not yet available.

References

Guy Karlebach and Ron Shamir. 2008. Modelling and analysis of gene regulatory networks, Nature Reviews Molecular Cell Biology 9: 770–80. DOI: https://doi.org/10.1038/nrm2503

Grochow J A and Kellis M. 2007. Network motif discovery using sub-graph enumeration and symmetry-breaking. RECOMB, pp 92–106. DOI: https://doi.org/10.1007/978-3-540-71681-5_7

Himanshu, Chaturvedi K K, Bandyopadhyay A and Jain Sarika. 2017. PATRICIA Trie based time and memory optimization for fast network motif search. Indian Journal of Animal Sciences 87(4): 512–19.

Khakabimamaghani S, Sharafuddin I and Dichter N. 2013. QuateXelero: an accelerated exact network motif detection algorithm. PLoSOne 8(7): e68073. DOI: https://doi.org/10.1371/journal.pone.0068073

McKay B D. 1981. Practical graph isomorphism. Congressus Numerantium 30: 45–87.

Milo R, Shen-Orr S and Itzkovitz S. 2002. Network motifs: Simple building blocks of complex networks. Science 298: 824–27. DOI: https://doi.org/10.1126/science.298.5594.824

Rauber T and Rünger G. 2009. Parallel Programming. Springer Berlin Heidelberg. p196. doi: 10.1007/978-3-642-04818-0_4. DOI: https://doi.org/10.1007/978-3-642-04818-0

Ribeiro P, Silva F and Lopes L. 2010. Efficient parallel subgraph counting using G-tries. Proceedings of IEEE International Conference on Cluster Computing pp. 2: 17–26. DOI: https://doi.org/10.1109/CLUSTER.2010.27

Ribeiro P, Silva F and Lopes L. 2011. Parallel discovery of network motifs. Journal of Parallel Distribution Computers [Internet]. Elsevier Inc. 72(2): 144–54. DOI: https://doi.org/10.1016/j.jpdc.2011.08.007

Schatz M, Cooper-Balis E and Bazinet A. 2008. Parallel Network Motif Finding.

Shen-Orr S, Milo R, Mangan S and Alon V. 2002. Network motifs in the transcriptional regulation network of Escherichia coli. Nature Genetics 31(1): 64–68. DOI: https://doi.org/10.1038/ng881

Tran, N, Mohan S, Xu Z and Huang C. 2014. Current innovations and future challenges of network motif detection. Briefings in Bioinformatics 16(3): 497–525. DOI: https://doi.org/10.1093/bib/bbu021

Wang T, Touchman J W, Zhang W, Suh E B and Xue G. 2005. A parallel algorithm for extracting transcription regulatory network motifs. IEEE International Symposium on Bioinformatics and Bioengineering, pp. 193–200.

Wernicke S and Rasche F. 2006. FANMOD: A tool for fast network motif detection. Bioinformatics 22(9): 1152–53. DOI: https://doi.org/10.1093/bioinformatics/btl038

Batagelj M and Mrvar A. 2006. Pajek Datasets. Available at http://vlado.fmf.uni-lj.si/pub/networks/data/

Newman M. 2009. Network Data. Available at: http://www-personal.umich.edu/mejn/netdata/