Accelerated Motif Detection Using Combinatorial Techniques

dc.creatorMeira L.A.A.
dc.creatorMaximo V.R.
dc.creatorFazenda A.L.
dc.creatorDa Conceicao A.F.
dc.date2012
dc.date2015-06-25T20:27:19Z
dc.date2015-11-26T15:24:04Z
dc.date2015-06-25T20:27:19Z
dc.date2015-11-26T15:24:04Z
dc.date.accessioned2018-03-28T22:32:56Z
dc.date.available2018-03-28T22:32:56Z
dc.identifier9780769549118
dc.identifier8th International Conference On Signal Image Technology And Internet Based Systems, Sitis 2012r. , v. , n. , p. 744 - 753, 2012.
dc.identifier
dc.identifier10.1109/SITIS.2012.113
dc.identifierhttp://www.scopus.com/inward/record.url?eid=2-s2.0-84874098490&partnerID=40&md5=1792ffc43abef5bbe65ddd82d7725975
dc.identifierhttp://www.repositorio.unicamp.br/handle/REPOSIP/90719
dc.identifierhttp://repositorio.unicamp.br/jspui/handle/REPOSIP/90719
dc.identifier2-s2.0-84874098490
dc.identifier.urihttp://repositorioslatinoamericanos.uchile.cl/handle/2250/1260593
dc.descriptionNetwork 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.
dc.description
dc.description
dc.description744
dc.description753
dc.descriptionAlon, U., (2012) Molecular Cell Biology Lab: Dataset, , http://www.weizmann.ac.il/mcb/UriAlon/groupNetworksData.html
dc.descriptionBarabasi, A.L., Crandall, R.E., Linked: The new science of networks (2003) American Journal of Physics, 71, p. 409
dc.descriptionBatagelj, V., Mrvar, A., (2006) Pajek Datasets, , http://vlado.fmf.uni-lj.si/pub/networks/data/
dc.descriptionChen, 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
dc.descriptionChiba, N., Nishizeki, T., Arboricity and subgraph listing algorithms (1985) SIAM J. Comput., 14 (1), pp. 210-223. , February
dc.descriptionCiriello, 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
dc.descriptionGrochow, 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
dc.descriptionKashani, 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
dc.descriptionKashtan, 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
dc.descriptionLin, 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)
dc.descriptionLones, 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
dc.descriptionMarcus, 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
dc.descriptionMarcus, D., Shavitt, Y., Rage - A rapid graphlet enumerator for large networks (2012) Computer Networks(COMNET Elsevier), , to appear., March
dc.descriptionMilo, 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
dc.descriptionKashtan, 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
dc.descriptionNash-Williams, C.S.J.A., Decomposition of finite graphs into forests (1964) Journal of the London Mathematical Society, 1 (1), pp. 12-12
dc.descriptionOmidi, 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
dc.descriptionRibeiro, 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
dc.descriptionSchreiber, F., Schwöbbermeyer, H., Mavisto: A tool for the exploration of network motifs (2005) Bioinformatics, 21 (17), pp. 3572-3574
dc.descriptionWernicke, S., Rasche, F., Fanmod: A tool for fast network motif detection (2006) Bioinformatics, 22 (9), pp. 1152-1153
dc.descriptionWong, E., Baur, B., Quader, S., Huang, C.-H., Biological network motif detection: Principles and practice (2011) Brief Bioinform
dc.descriptionYang, 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
dc.languageen
dc.publisher
dc.relation8th International Conference on Signal Image Technology and Internet Based Systems, SITIS 2012r
dc.rightsfechado
dc.sourceScopus
dc.titleAccelerated Motif Detection Using Combinatorial Techniques
dc.typeActas de congresos


Este ítem pertenece a la siguiente institución