acc-Motif : accelerated network motif detection
Luis A. A. Meira, Vinícius R. Maximo, Álvaro L. Fazenda, Arlindo F. da Conceição
ARTIGO
Inglês
Agradecimentos: This research was partially supported by the State of São Paulo Research Foundation (FAPESP Grant 2013/00836-1)
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....
Ver mais
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
Ver menos
FUNDAÇÃO DE AMPARO À PESQUISA DO ESTADO DE SÃO PAULO - FAPESP
2013/00836-1
Fechado
DOI: https://doi.org/10.1109/TCBB.2014.2321150
Texto completo: https://ieeexplore.ieee.org/document/6808514
acc-Motif : accelerated network motif detection
Luis A. A. Meira, Vinícius R. Maximo, Álvaro L. Fazenda, Arlindo F. da Conceição
acc-Motif : accelerated network motif detection
Luis A. A. Meira, Vinícius R. Maximo, Álvaro L. Fazenda, Arlindo F. da Conceição
Fontes
|
IEEE/ACM transactions on computational biology and bioinformatics v. 11, n. 5, p. 853-862, Sept./Oct. 2014 |