2021
1.
Al-Thaedan, Abbas; Carvalho, Marco; Nembhard, Fitzroy
A Fast and Exact Motif Enumeration Algorithm for Dynamic Networks Proceedings Article
In: Arai, Kohei (Ed.): Advances in Information and Communication, pp. 123–141, Springer International Publishing, Cham, 2021, ISBN: 978-3-030-73103-8.
Abstract | BibTeX | Tags: algorithms, bioinformatics, databases, dynamic networks, graphs, motifs, nauty, networks, protein interaction, transcription networks
@inproceedings{MotifEnumeration,
title = {A Fast and Exact Motif Enumeration Algorithm for Dynamic Networks},
author = {Abbas Al-Thaedan and Marco Carvalho and Fitzroy Nembhard},
editor = {Kohei Arai},
isbn = {978-3-030-73103-8},
year = {2021},
date = {2021-04-16},
urldate = {2021-04-16},
booktitle = {Advances in Information and Communication},
pages = {123--141},
publisher = {Springer International Publishing},
address = {Cham},
abstract = {Network motifs have been widely used in the analysis of various biological networks, including protein-protein interaction (PPI) networks, transcription regulation networks (TRNs), and metabolic networks. Counting network motif involves expensive enumeration of sub-patterns and graph isomorphism. Many protein-protein interaction databases are readily available online and are constantly updated over a period of time by either adding or removing proteins and the respective interactions between them. There exists many motif enumeration algorithms that can be applied to protein-protein interaction databases.
However, most existing algorithms run enumeration over the entire network every time a change is made to the network. This is not only computationally expensive but also highly inefficient as the size of the network and motif increases. In this work, we propose an exact and efficient algorithm for enumerating network motifs by utilizing only updated edges and vertices in a network. We demonstrate how our algorithm can quickly and robustly update the frequency of different sizes of network motifs in
dynamic networks. Experimental results show that our approach is successful in reducing the computational time by eliminating overlapped subgraphs. Runtime monitoring of network motif distributions is very
important in numerous practical domains where large networks are subject to localized changes, which is efficiently provided by the proposed algorithm.},
keywords = {algorithms, bioinformatics, databases, dynamic networks, graphs, motifs, nauty, networks, protein interaction, transcription networks},
pubstate = {published},
tppubtype = {inproceedings}
}
Network motifs have been widely used in the analysis of various biological networks, including protein-protein interaction (PPI) networks, transcription regulation networks (TRNs), and metabolic networks. Counting network motif involves expensive enumeration of sub-patterns and graph isomorphism. Many protein-protein interaction databases are readily available online and are constantly updated over a period of time by either adding or removing proteins and the respective interactions between them. There exists many motif enumeration algorithms that can be applied to protein-protein interaction databases.
However, most existing algorithms run enumeration over the entire network every time a change is made to the network. This is not only computationally expensive but also highly inefficient as the size of the network and motif increases. In this work, we propose an exact and efficient algorithm for enumerating network motifs by utilizing only updated edges and vertices in a network. We demonstrate how our algorithm can quickly and robustly update the frequency of different sizes of network motifs in
dynamic networks. Experimental results show that our approach is successful in reducing the computational time by eliminating overlapped subgraphs. Runtime monitoring of network motif distributions is very
important in numerous practical domains where large networks are subject to localized changes, which is efficiently provided by the proposed algorithm.
However, most existing algorithms run enumeration over the entire network every time a change is made to the network. This is not only computationally expensive but also highly inefficient as the size of the network and motif increases. In this work, we propose an exact and efficient algorithm for enumerating network motifs by utilizing only updated edges and vertices in a network. We demonstrate how our algorithm can quickly and robustly update the frequency of different sizes of network motifs in
dynamic networks. Experimental results show that our approach is successful in reducing the computational time by eliminating overlapped subgraphs. Runtime monitoring of network motif distributions is very
important in numerous practical domains where large networks are subject to localized changes, which is efficiently provided by the proposed algorithm.