Actas de congresos
Accelerated Motif Detection Using Combinatorial Techniques
Registro en:
9780769549118
8th International Conference On Signal Image Technology And Internet Based Systems, Sitis 2012r. , v. , n. , p. 744 - 753, 2012.
10.1109/SITIS.2012.113
2-s2.0-84874098490
Autor
Meira L.A.A.
Maximo V.R.
Fazenda A.L.
Da Conceicao A.F.
Institución
Resumen
Network motif algorithms have been a topic of research mainly after the 2002-seminal paper from Milo et al, that provided motifs as a way to uncover the basic building blocks of most networks. This article proposes new algorithms to exactly count isomorphic pattern motifs of size 3 and 4 in directed graphs. The algorithms are accelerated by combinatorial techniques. Let G(V,E) be a directed graph with m = |E|. We describe an O(m√m) time complexity algorithm to count isomorphic patterns of size 3. To counting isomorphic patterns of size 4, we propose an O(m2) algorithm. The new algorithms were implemented and compared with Fanmod motif detection tool. The experiments show that our algorithms are expressively faster than Fanmod. We also let our tool to detect motifs, the acc-MOTIF, available in the Internet. © 2012 IEEE.
744 753 Alon, U., (2012) Molecular Cell Biology Lab: Dataset, , http://www.weizmann.ac.il/mcb/UriAlon/groupNetworksData.html Barabasi, A.L., Crandall, R.E., Linked: The new science of networks (2003) American Journal of Physics, 71, p. 409 Batagelj, V., Mrvar, A., (2006) Pajek Datasets, , http://vlado.fmf.uni-lj.si/pub/networks/data/ Chen, J., Hsu, W., Lee, M.L., Ng, S.-K., Nemofinder: Dissecting genome-wide proteinprotein interactions with meso-scale network motifs (2006) Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '06, pp. 106-115. , New York, NY, USA. ACM Chiba, N., Nishizeki, T., Arboricity and subgraph listing algorithms (1985) SIAM J. Comput., 14 (1), pp. 210-223. , February Ciriello, G., Guerra, C., A review on models and algorithms for motif discovery in protein-protein interaction networks (2008) Briefings in Functional Genomics & Proteomics, 7 (2), pp. 147-156 Grochow, J.A., Kellis, M., Network motif discovery using subgraph enumeration and symmetry-breaking (2007) Proceedings of the 11th Annual International Conference on Research in Computational Molecular Biology, RECOMB'07, pp. 92-106. , Berlin, Heidelberg. Springer-Verlag Kashani, Z., Ahrabian, H., Elahi, E., Nowzari-Dalini, A., Ansari, E., Asadi, S., Mohammadi, S., Masoudi-Nejad, A., Kavosh: A new algorithm for finding network motifs (2009) BMC Bioinformatics, 10 (1), p. 318 Kashtan, N., Itzkovitz, S., Milo, R., Alon, U., Efficient sampling algorithm for estimating subgraph concentrations and detecting network motifs (2004) Bioinformatics, 20 (11), pp. 1746-1758. , July Lin, Z., Guanqun, Q., Li, Z., Clustering analysis of motif significance profile in software networks (2008) Proceedings of the 10th WSEAS International Conference on Mathematical Methods and Computational Techniques in Electrical Engineering, pp. 145-147. , Stevens Point, Wisconsin, USA. World Scientific and Engineering Academy and Society (WSEAS) Lones, M., Tyrrell, A., Regulatory motif discovery using a population clustering evolutionary algorithm (2007) IEEE/ACM Transactions on Computational Biology and Bioinformatics, 4, pp. 403-414 Marcus, D., Shavitt, Y., Efficient counting of network motifs (2010) Proceedings of the 2010 IEEE 30th International Conference on Distributed Computing Systems Workshops, ICDCSW '10, pp. 92-98. , Washington, DC, USA. IEEE Computer Society Marcus, D., Shavitt, Y., Rage - A rapid graphlet enumerator for large networks (2012) Computer Networks(COMNET Elsevier), , to appear., March Milo, R., Shen-Orr, S., Itzkovitz, S., Kashtan, N., Chklovskii, D., Alon, U., Network motifs: Simple building blocks of complex networks (2002) Science, 298, pp. 824-887 Kashtan, N., Itzkovitz, S., Milo, R., Alon, U., Network motif detection tool: Mfinder tool guide (2005) Technical Report, Department of Molecular Cell Biology and Computer Science and Applied Mathematics, , Weizman Institute of Science, Israel Nash-Williams, C.S.J.A., Decomposition of finite graphs into forests (1964) Journal of the London Mathematical Society, 1 (1), pp. 12-12 Omidi, S., Schreiber, F., Masoudi-Nejad, A., Moda: An efficient algorithm for network motif discovery in biological networks (2009) Genes Genet. Syst, 84, pp. 385-395 Ribeiro, P., Silva, F., Kaiser, M., Strategies for network motifs discovery (2009) Proceedings of the 2009 Fifth IEEE International Conference on E-Science, E-SCIENCE '09, pp. 80-87. , Washington, DC, USA. IEEE Computer Society Schreiber, F., Schwöbbermeyer, H., Mavisto: A tool for the exploration of network motifs (2005) Bioinformatics, 21 (17), pp. 3572-3574 Wernicke, S., Rasche, F., Fanmod: A tool for fast network motif detection (2006) Bioinformatics, 22 (9), pp. 1152-1153 Wong, E., Baur, B., Quader, S., Huang, C.-H., Biological network motif detection: Principles and practice (2011) Brief Bioinform Yang, K.-H., Chiou, K.-Y., Lee, H.-M., Ho, J.-M., Web appearance disambiguation of personal names based on network motif (2006) Proceedings of the 2006 IEEE/WIC/ACM International Conference on Web Intelligence, WI '06, pp. 386-389. , Washington, DC, USA. IEEE Computer Society