Parallel Matrix Multiplication Algorithms Acquire Connected Network Motifs
Keywords:Molecular Networks, Graph theory, Digraphs, Network Motifs, Parallel Algorithm, Matrix Multiplication
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
"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.
How to Cite
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
The proposed policy for journals that offer open access
Authors who publish with this journal agree to the following terms:
- Copyright on any article is retained by the author(s).
- Author grant the journal, right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work’s authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal’s published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.
- The article and any associated published material is distributed under the Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License