{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,26]],"date-time":"2026-08-26T12:27:52Z","timestamp":1787747272516,"version":"build-2784847793"},"reference-count":25,"publisher":"Oxford University Press (OUP)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014,2,15]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: Small-induced subgraphs called graphlets are emerging as a possible tool for exploration of global and local structure of networks and for analysis of roles of individual nodes. One of the obstacles to their wider use is the computational complexity of algorithms for their discovery and counting.<\/jats:p>\n               <jats:p>Results: We propose a new combinatorial method for counting graphlets and orbit signatures of network nodes. The algorithm builds a system of equations that connect counts of orbits from graphlets with up to five nodes, which allows to compute all orbit counts by enumerating just a single one. This reduces its practical time complexity in sparse graphs by an order of magnitude as compared with the existing pure enumeration-based algorithms.<\/jats:p>\n               <jats:p>Availability and implementation: Source code is available freely at http:\/\/www.biolab.si\/supp\/orca\/orca.html.<\/jats:p>\n               <jats:p>Contact: \u00a0tomaz.hocevar@fri.uni-lj.si<\/jats:p>\n               <jats:p>Supplementary information: \u00a0Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btt717","type":"journal-article","created":{"date-parts":[[2013,12,13]],"date-time":"2013-12-13T02:10:14Z","timestamp":1386900614000},"page":"559-565","source":"Crossref","is-referenced-by-count":169,"title":["A combinatorial approach to graphlet counting"],"prefix":"10.1093","volume":"30","author":[{"given":"Toma\u017e","family":"Ho\u010devar","sequence":"first","affiliation":[{"name":"Faculty of Computer and Information Science, University of Ljubljana, SI-1000 Ljubljana, Slovenia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Janez","family":"Dem\u0161ar","sequence":"additional","affiliation":[{"name":"Faculty of Computer and Information Science, University of Ljubljana, SI-1000 Ljubljana, Slovenia"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"286","published-online":{"date-parts":[[2014,12,11]]},"reference":[{"key":"2023012710422817100_btt717-B1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1109\/FPT.2011.6132667","article-title":"A framework for FPGA acceleration of large graph problems: graphlet counting case study","volume-title":"2011 International Conference on Field-Programmable Technology","author":"Betkaoui","year":"2011"},{"key":"2023012710422817100_btt717-B2","doi-asserted-by":"crossref","first-page":"D816","DOI":"10.1093\/nar\/gks1158","article-title":"The BioGRID interaction database: 2013 update","volume":"41","author":"Chatr-Aryamontri","year":"2013","journal-title":"Nucleic Acids Res."},{"key":"2023012710422817100_btt717-B3","doi-asserted-by":"crossref","first-page":"483","DOI":"10.1093\/bioinformatics\/bts729","article-title":"Graphlet-based measures are suitable for biological network comparison","volume":"29","author":"Hayes","year":"2013","journal-title":"Bioinformatics (Oxford, England)"},{"key":"2023012710422817100_btt717-B4","doi-asserted-by":"crossref","first-page":"1746","DOI":"10.1093\/bioinformatics\/bth163","article-title":"Efficient sampling algorithm for estimating subgraph concentrations and detecting network motifs","volume":"20","author":"Kashtan","year":"2004","journal-title":"Bioinformatics"},{"key":"2023012710422817100_btt717-B5","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1016\/S0020-0190(00)00047-8","article-title":"Finding and counting small induced subgraphs efficiently","volume":"74","author":"Kloks","year":"2000","journal-title":"Inf. Process. Lett."},{"key":"2023012710422817100_btt717-B6","first-page":"1468","article-title":"Counting and detecting small subgraphs via equations and matrix multiplication","volume-title":"Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Kowaluk","year":"2011"},{"key":"2023012710422817100_btt717-B7","first-page":"1390","article-title":"Integrative network alignment reveals large regions of global network similarity in yeast and human","volume":"27","author":"Kuchaiev","year":"2011","journal-title":"Bioinformatics (Oxford, England)"},{"key":"2023012710422817100_btt717-B8","doi-asserted-by":"crossref","first-page":"1341","DOI":"10.1098\/rsif.2010.0063","article-title":"Topological network alignment uncovers biological function and phylogeny","volume":"7","author":"Kuchaiev","year":"2010","journal-title":"J. R. Soc. Interface"},{"key":"2023012710422817100_btt717-B9","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1186\/1471-2105-12-24","article-title":"GraphCrunch 2: software tool for network modeling, alignment and clustering","volume":"12","author":"Kuchaiev","year":"2011","journal-title":"BMC Bioinformatics"},{"key":"2023012710422817100_btt717-B10","doi-asserted-by":"crossref","first-page":"810","DOI":"10.1016\/j.comnet.2011.08.019","article-title":"RAGE - a rapid graphlet enumerator for large networks","volume":"56","author":"Marcus","year":"2012","journal-title":"Comput. Netw."},{"key":"2023012710422817100_btt717-B11","doi-asserted-by":"crossref","first-page":"257","DOI":"10.4137\/CIN.S680","article-title":"Uncovering biological network function via graphlet degree signatures","volume":"6","author":"Milenkovi\u0107","year":"2008","journal-title":"Cancer Inform."},{"key":"2023012710422817100_btt717-B12","doi-asserted-by":"crossref","first-page":"70","DOI":"10.1186\/1471-2105-9-70","article-title":"GraphCrunch: a tool for large network analyses","volume":"9","author":"Milenkovi\u0107","year":"2008","journal-title":"BMC Bioinformatics"},{"key":"2023012710422817100_btt717-B13","doi-asserted-by":"crossref","first-page":"121","DOI":"10.4137\/CIN.S4744","article-title":"Optimal network alignment with graphlet degree vectors","volume":"9","author":"Milenkovi\u0107","year":"2010","journal-title":"Cancer Inform."},{"key":"2023012710422817100_btt717-B14","first-page":"423","article-title":"Systems-level cancer gene identification from protein interaction network topology applied to melanogenesis-related functional genomics data","volume":"7","author":"Milenkovi\u0107","year":"2010","journal-title":"J. R. Soc."},{"key":"2023012710422817100_btt717-B15","doi-asserted-by":"crossref","first-page":"e23016","DOI":"10.1371\/journal.pone.0023016","article-title":"Dominating biological networks","volume":"6","author":"Milenkovi\u0107","year":"2011","journal-title":"PLoS One"},{"key":"2023012710422817100_btt717-B16","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1145\/2506583.2508968","article-title":"Global network alignment in the context of aging","volume-title":"Proceedings of the International Conference on Bioinformatics, Computational Biology and Biomedical Informatics","author":"Milenkovi\u0107","year":"2013"},{"key":"2023012710422817100_btt717-B17","doi-asserted-by":"crossref","first-page":"e177","DOI":"10.1093\/bioinformatics\/btl301","article-title":"Biological network comparison using graphlet degree distribution","volume":"23","author":"Pr\u017eulj","year":"2007","journal-title":"Bioinformatics (Oxford, England)"},{"key":"2023012710422817100_btt717-B18","first-page":"3508","article-title":"Modeling interactome: scale-free or geometric?","volume":"20","author":"Pr\u017eulj","year":"2004","journal-title":"Bioinformatics (Oxford, England)"},{"key":"2023012710422817100_btt717-B19","first-page":"974","article-title":"Efficient estimation of graphlet frequency distributions in protein-protein interaction networks","volume":"22","author":"Pr\u017eulj","year":"2006","journal-title":"Bioinformatics (Oxford, England)"},{"key":"2023012710422817100_btt717-B20","doi-asserted-by":"crossref","first-page":"D449","DOI":"10.1093\/nar\/gkh086","article-title":"The database of interacting proteins: 2004 update","volume":"32","author":"Salwinski","year":"2004","journal-title":"Nucleic Acids Res."},{"key":"2023012710422817100_btt717-B21","first-page":"i480","article-title":"Graphlet-based edge clustering reveals pathogen-interacting proteins","volume":"28","author":"Solava","year":"2012","journal-title":"Bioinformatics (Oxford, England)"},{"key":"2023012710422817100_btt717-B22","doi-asserted-by":"crossref","first-page":"26","DOI":"10.1109\/CSE.2009.225","article-title":"Structure of neighborhoods in a large social network","volume-title":"2009 International Conference on Computational Science and Engineering","author":"Stoica","year":"2009"},{"key":"2023012710422817100_btt717-B23","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1109\/TCBB.2006.51","article-title":"Efficient detection of network motifs","volume":"3","author":"Wernicke","year":"2006","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"key":"2023012710422817100_btt717-B24","first-page":"1152","article-title":"FANMOD: a tool for fast network motif detection","volume":"22","author":"Wernicke","year":"2006","journal-title":"Bioinformatics (Oxford, England)"},{"key":"2023012710422817100_btt717-B25","first-page":"290","article-title":"Computing graphlet signatures of network nodes and motifs in Cytoscape with GraphletCounter","volume":"28","author":"Whelan","year":"2012","journal-title":"Bioinformatics (Oxford, England)"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/30\/4\/559\/48917199\/bioinformatics_30_4_559.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/30\/4\/559\/48917199\/bioinformatics_30_4_559.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,27]],"date-time":"2023-01-27T10:58:35Z","timestamp":1674817115000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/30\/4\/559\/205331"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,2,15]]},"references-count":25,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2014,2,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btt717","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2014,2,15]]},"published":{"date-parts":[[2014,2,15]]}}}