Parallel Matrix Multiplication Algorithms Acquire Connected Network Motifs

Efendi Zaenudin; Ka-Lok Ng

doi:10.56873/jitu.6.1.4983

Authors

Efendi Zaenudin The National Research and Innovation Agency Republic Indonesia
Ka-Lok Ng Department Bioinformatics and Medical Engineering, Asia University, Taichung, Taiwan

DOI:

https://doi.org/10.56873/jitu.6.1.4983

Keywords:

Molecular Networks, Graph theory, Digraphs, Network Motifs, Parallel Algorithm, Matrix Multiplication

Abstract

The network of interactions between biomolecules is essential to biological processes. Many studies have shown that molecular networks can be analyzed by breaking them down into smaller modules known as network motifs. We hypothesize that identifying the set of possible 5-node motifs and 6-node motifs embedded in a network is a necessary step to elucidate the complex topology of a network. Accomplishing this goal requires determining the complete set of motifs that are composed of five and six connected nodes.

We developed a parallel algorithm to reduce time consumption that tackles the exponential problem. It is implemented in matrix multiplication insert in the process of identifying isomorphic patterns and removing the isolated and disconnected patterns. The experiment showed that the parallelization matrix multiplication algorithm is approximately 1.4 times faster than serial programming for identifying 5-node motifs and approximately 1.3 times faster than serial programming for identifying 6-node motifs with all the nodes connected

References

"Transcriptome and Proteome: Macromolecular Networks," in Bioinformatics, 2006, pp. 169-209.

"Genetic Information and Biological Sequences," in Bioinformatics, 2006, pp. 85-106.

"Statistics and Sequences," in Bioinformatics, 2006, pp. 107-129.

A. Ma'ayan et al., "SNAVI: Desktop application for analysis and visualization of large-scale signaling networks," BMC Systems Biology, vol. 3, no. 1, p. 10, 2009/01/20 2009.

U. Alon, "Network motifs: theory and experimental approaches," Nature Reviews Genetics, vol. 8, no. 6, pp. 450-461, 2007/06/01 2007.

S. S. Shen-Orr, R. Milo, S. Mangan, and U. Alon, "Network motifs in the transcriptional regulation network of Escherichia coli," Nature Genetics, vol. 31, no. 1, pp. 64-68, 2002/05/01 2002.

R. Milo, S. Shen-Orr, S. Itzkovitz, N. Kashtan, D. Chklovskii, and U. Alon, "Network motifs: simple building blocks of complex networks," Science, vol. 298, no. 5594, pp. 824-7, Oct 25, 2002.

J. Fodor, M. Brand, R. J. Stones, and A. M. Buckle, "Intrinsic limitations in mainstream methods of identifying network motifs in biology," BMC Bioinformatics, vol. 21, no. 1, p. 165, 2020/04/29 2020.

M. B. Z. Joveini and J. Sadri, "Application of Fractal Theory on Motifs Counting in Biological Networks," IEEE/ACM Trans Comput Biol Bioinform, vol. 15, no. 2, pp. 613-623, Mar-Apr 2018.

K. Mukherjee, M. M. Hasan, C. Boucher, and T. Kahveci, "Counting motifs in dynamic networks," BMC Syst Biol, vol. 12, no. Suppl 1, p. 6, Apr 11 2018.

J. Wang, Y. Huang, F. X. Wu, and Y. Pan, "Symmetry Compression Method for Discovering Network Motifs," IEEE/ACM Transactions on Computational Biology and Bioinformatics, vol. 9, no. 6, pp. 1776-1789, 2012.

S. Wernicke, "Efficient detection of network motifs," IEEE/ACM Trans Comput Biol Bioinform, vol. 3, no. 4, pp. 347-59, Oct-Dec 2006.

W. Kim, M. Diko, and K. Rawson, "Network motif detection: Algorithms, parallel and cloud computing, and related tools," Tsinghua Science and Technology, vol. 18, no. 5, pp. 469-489, 2013.

S. Mangan and U. Alon, "Structure and function of the feed-forward loop network motif," vol. 100, no. 21, pp. 11980-11985, 2003.

P. J. Ingram, M. P. H. Stumpf, and J. Stark, "Network motifs: structure does not determine function," BMC Genomics, vol. 7, no. 1, p. 108, 2006/05/05 2006.

M. M. Babu, N. M. Luscombe, L. Aravind, M. Gerstein, and S. A. Teichmann, "Structure and evolution of transcriptional regulatory networks," Curr Opin Struct Biol, vol. 14, no. 3, pp. 283-91, Jun 2004.

G. Swiers, R. Patient, and M. Loose, "Genetic regulatory networks programming hematopoietic stem cells and erythroid lineage specification," Dev Biol, vol. 294, no. 2, pp. 525-40, Jun 15, 2006.

M. De Domenico et al., "Mathematical Formulation of Multilayer Networks," Physical Review X, vol. 3, no. 4, p. 041022, 12/04/ 2013.

M. Kivelä and M. A. Porter, "Isomorphisms in Multilayer Networks," IEEE Transactions on Network Science and Engineering, vol. 5, no. 3, pp. 198-211, 2018.

E. Zaenudin, C.-H. Huang, K.-L. J. I. J. o. M. Ng, and C. Sciences, "Identifying Network Subgraph-Associated Essential Genes in Molecular Networks," vol. 15, no. 5, pp. 71-77, 2021.

C.-H. Huang, E. Zaenudin, J. J. Tsai, N. Kurubanjerdjit, E. Y. Dessie, and K.-L. J. P. Ng, "Dissecting molecular network structures using a network subgraph approach," vol. 8, p. e9556, 2020.

C.-H. Huang, E. Zaenudin, J. J. Tsai, N. Kurubanjerdjit, and K.-L. J. P. Ng, "Network subgraph-based approach for analyzing and comparing molecular networks," vol. 10, p. e13137, 2022.

E. Zaenudin et al., "An Algorithm to Construct Network Motifs for Bioinformatics Study," (in English), Lecture Notes in Engineering and Computer Science: Proceedings of The International MultiConference of Engineers and Computer Scientists, 2019.

E. Zaenudin et al., "A parallel algorithm to generate connected network motifs IAENG," International Journal of Computer Science, vol. 46, no. 4, pp. 518-523, 2019.

F. Harary and E. Palmer, "Graphical enumeration, acad," Press, NY, 1973.

N. J. A. Sloane and S. Plouffe, "The Encyclopedia of Integer Sequences," Academic Press, San Diego, 587, 1995.