PATRICIA trie based time and memory optimization for fast network motif Search

HIMANSHU; K K CHATURVEDI; A BANDYOPADHYAY; SARIKA JAIN

doi:10.56093/ijans.v87i4.69625

Authors

HIMANSHU Amity Institute of Information Technology, Amity University, Noida, Uttar Pradesh 201 313 India
K K CHATURVEDI 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.v87i4.69625

Keywords:

Algorithms, Bioinformatics, Complex networks, Data structures, Network motifs, Optimization, PATRICIA

Abstract

Network motif search is useful in uncovering the important functional components of complex networks in biological, chemical, social and other domains. PATCOMP - a PARTICIA based novel approach for network motif search is proposed in this paper. The algorithm of PATCOMP takes benefit of memory compression and speed of PATRICIA trie to store the collection of subgraphs in memory and search them for classification and census of network. The structure of trie nodes and how data structure is developed to use it for counting the subgraphs is also described. PATCOMP was compared with QuateXelero and G-Tries.The main benefit of this approach is significant reduction in memory space requirement particularly for large network motifs with acceptable time performance. The experiments with directed networks like E.coli, yeast, social and electronic validated the advantage of PATCOMP in terms of reduction in memory usage by 2.7-27.7% as compared to QuateXelero for smaller motif sizes (with exceptions of s=6 for E. coli and s=6 for social), and 7.8-38.35% for larger motif sizes. For undirected networks, PATCOMP utilizes less memory by 0.07%-43% (with exception of s=7 for electronic and s=6,8 for dolphin networks).

Downloads

Download data is not yet available.

References

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

Himanshu and Jain S. 2016. Impact of memory space optimization technique on fast network motif search algorithm. ICCCCS 2016, Ajmer, India (accepted). Springer. DOI: https://doi.org/10.1007/978-981-10-3770-2_52

Kashani Z R, Ahrabian H, Elahi E et al. 2009. Kavosh: a new algorithm for finding network motifs. BMC Bioinformatics 10: 318. DOI: https://doi.org/10.1186/1471-2105-10-318

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

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

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

Robert S. 1983. Algorithms. Addison Wesley. Ribeiro P, Silva F and Kaiser M. 2009. Strategies for network motifs discovery. Proceedings of the 5th IEEE International Conference on E-Science, IEEE CSPress, Oxford, UK.

Ribeiro P and Silva F. 2010. Efûcient subgraph frequency estimation with G-tries. International Workshop on Algorithms in Bioinformatics (WABI), LNCS 6293: 238–49. Springer. DOI: https://doi.org/10.1007/978-3-642-15294-8_20

Rao A R, Dash M and Sahu T K et al. 2014. Statistical and bio- computational applications in animal sciences. Indian Journal of Animal Sciences 84(5): 475–89.

Schreiber H, and Schwobbermeyer. 2004. Towards motif detection in networks: frequency concepts and flexible search. Proceedings of the International Workshop on Network Tools and Applications in Biology 91–102. Camerino, Italy.

Warnicke S. 2006. Efficient detection of network motifs. IEEE/ ACM Transactions on Computational Biology and Bioinformatics 3(4): 347–59. DOI: https://doi.org/10.1109/TCBB.2006.51

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

Wong E, Baur B, Quader S et al. 2001. Biological network motif detection: principles and practice. Briefings in Bioinformatics 13(2): 202–15. DOI: https://doi.org/10.1093/bib/bbr033

The E. coli Database. Available: http: //www.genome.jp/kegg/ Alon U. 2002. The S. cerevisiae Database. Available: http://www.weizmann.ac.il/mcb/UriAlon.

Bu D, Zhao Y, Cai L et al. 2003. Topological structure analysis of the protein-protein interaction network in budding yeast. Nucleic Acids Research 31: 2443–50. DOI: https://doi.org/10.1093/nar/gkg340

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

Lusseau D, Schneider K, Boisseau O J et al. 2003. The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations. can geographic isolation explain this unique trait? Behavioral Ecology and Sociobiology 54: 396–405. DOI: https://doi.org/10.1007/s00265-003-0651-y

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