acc-Motif: Accelerated Network Motif Detection

acc-Motif: Accelerated Network Motif Detection

Author Meira, Luis A. A. Google Scholar
Maximo, Vinicius R. Autor UNIFESP Google Scholar
Fazenda, Alvaro L. Autor UNIFESP Google Scholar
Conceicao, Arlindo F. da Autor UNIFESP Google Scholar
Institution Universidade Estadual de Campinas (UNICAMP)
Universidade Federal de São Paulo (UNIFESP)
Abstract Network motif algorithms have been a topic of research mainly after the 2002-seminal paper from Milo et al. [1], which provided motifs as a way to uncover the basic building blocks of most networks. Motifs have been mainly applied in Bioinformatics, regarding gene regulation networks. Motif detection is based on induced subgraph counting. This paper proposes an algorithm to count subgraphs of size k + 2 based on the set of induced subgraphs of size k. the general technique was applied to detect 3, 4 and 5-sized motifs in directed graphs. Such algorithms have time complexity O(a(G)m), O(m(2)) and O(nm(2)), respectively, where a(G) is the arboricity of G(V, E). the computational experiments in public data sets show that the proposed technique was one order of magnitude faster than Kavosh and FANMOD. When compared to NetMODE, acc-Motif had a slightly improved performance.
Keywords Network motifs
algorithm analysis
subgraph counting
Language English
Sponsor Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)
Grant number FAPESP: 2013/00836-1
Date 2014-09-01
Published in Ieee-acm Transactions On Computational Biology and Bioinformatics. Los Alamitos: Ieee Computer Soc, v. 11, n. 5, p. 853-862, 2014.
ISSN 1545-5963 (Sherpa/Romeo, impact factor)
Publisher Ieee Computer Soc
Extent 853-862
Access rights Closed access
Type Article
Web of Science ID WOS:000346629600008

Show full item record


File Size Format View

There are no files associated with this item.

This item appears in the following Collection(s)




My Account