{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,12]],"date-time":"2026-06-12T03:42:12Z","timestamp":1781235732729,"version":"3.54.1"},"reference-count":13,"publisher":"Oxford University Press (OUP)","issue":"8","license":[{"start":{"date-parts":[[2017,11,24]],"date-time":"2017-11-24T00:00:00Z","timestamp":1511481600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/about_us\/legal\/notices"}],"funder":[{"DOI":"10.13039\/501100004385","name":"Universiteit Gent","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100004385","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018,4,15]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:sec><jats:title>Motivation<\/jats:title><jats:p>Graphlets are a useful tool to determine a graph\u2019s small-scale structure. Finding them is exponentially hard with respect to the number of nodes in each graphlet. Therefore, equations can be used to reduce the size of graphlets that need to be enumerated to calculate the number of each graphlet touching each node. Ho\u010devar and Dem\u0161ar first introduced such equations, which were derived manually, and an algorithm that uses them, but only graphlets with four or five nodes can be counted this way.<\/jats:p><\/jats:sec><jats:sec><jats:title>Results<\/jats:title><jats:p>We present a new algorithm for orbit counting, which is applicable to graphlets of any order. This algorithm uses a tree structure to simplify finding orbits, and stabilizers and symmetry-breaking constraints to ensure correctness. This method gives a significant speedup compared to a brute force counting method and can count orbits beyond the capacity of other available tools.<\/jats:p><\/jats:sec><jats:sec><jats:title>Availability and implementation<\/jats:title><jats:p>An implementation of the algorithm can be found at https:\/\/github.com\/biointec\/jesse.<\/jats:p><\/jats:sec>","DOI":"10.1093\/bioinformatics\/btx758","type":"journal-article","created":{"date-parts":[[2017,11,23]],"date-time":"2017-11-23T20:16:26Z","timestamp":1511468186000},"page":"1372-1380","source":"Crossref","is-referenced-by-count":24,"title":["Efficiently counting all orbits of graphlets of any order in a graph using autogenerated equations"],"prefix":"10.1093","volume":"34","author":[{"given":"Ine","family":"Melckenbeeck","sequence":"first","affiliation":[{"name":"IDLab, Ghent University - Imec, Ghent, Belgium"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pieter","family":"Audenaert","sequence":"additional","affiliation":[{"name":"IDLab, Ghent University - Imec, Ghent, Belgium"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Didier","family":"Colle","sequence":"additional","affiliation":[{"name":"IDLab, Ghent University - Imec, Ghent, Belgium"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mario","family":"Pickavet","sequence":"additional","affiliation":[{"name":"IDLab, Ghent University - Imec, Ghent, Belgium"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"286","published-online":{"date-parts":[[2017,11,24]]},"reference":[{"key":"2023012713011677400_btx758-B1","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1016\/S0378-4371(99)00291-5","article-title":"Mean-field theory for scale-free random networks","volume":"272","author":"Barab\u00e1si","year":"1999","journal-title":"Physica A: Stat. Mech. Appl"},{"key":"2023012713011677400_btx758-B2","doi-asserted-by":"crossref","first-page":"1043","DOI":"10.1126\/science.1176495","article-title":"A global protein kinase and phosphatase interaction network in yeast","volume":"328","author":"Breitkreutz","year":"2010","journal-title":"Science"},{"key":"2023012713011677400_btx758-B3","first-page":"290","article-title":"On random graphs","volume":"6","author":"Erdos","year":"1959","journal-title":"Publ. Math"},{"key":"2023012713011677400_btx758-B4","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1103\/PhysRevE.82.011921","article-title":"Network motifs come in sets: correlations in the randomization process","volume":"82","author":"Ginoza","year":"2010","journal-title":"Phys. Rev. E"},{"key":"2023012713011677400_btx758-B5","first-page":"559","article-title":"A combinatorial approach to graphlet counting","volume":"30","author":"Ho\u010devar","year":"2014","journal-title":"Bioinformatics (Oxford, England)"},{"key":"2023012713011677400_btx758-B6","doi-asserted-by":"crossref","first-page":"e97896","DOI":"10.1371\/journal.pone.0097896","article-title":"The Index-based Subgraph Matching Algorithm with General Symmetries (ISMAGS): exploiting symmetry for faster subgraph enumeration","volume":"9","author":"Houbraken","year":"2014","journal-title":"PLOS One"},{"key":"2023012713011677400_btx758-B7","first-page":"831","author":"Lin","year":"2015"},{"key":"2023012713011677400_btx758-B8","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1371\/journal.pone.0147078","article-title":"An algorithm to automatically generate the combinatorial orbit counting equations","volume":"11","author":"Melckenbeeck","year":"2016","journal-title":"PLoS One"},{"key":"2023012713011677400_btx758-B9","doi-asserted-by":"crossref","first-page":"824","DOI":"10.1126\/science.298.5594.824","article-title":"Network motifs: simple building blocks of complex networks","volume":"298","author":"Milo","year":"2002","journal-title":"Science (New York, N.Y.)"},{"key":"2023012713011677400_btx758-B10","doi-asserted-by":"crossref","first-page":"e177","DOI":"10.1093\/bioinformatics\/btl301","article-title":"Biological network comparison using graphlet degree distribution","volume":"23","author":"Przulj","year":"2007","journal-title":"Bioinformatics (Oxford, England)"},{"key":"2023012713011677400_btx758-B11","first-page":"3508","article-title":"Modeling interactome: scale-free or geometric?","volume":"20","author":"Przulj","year":"2004","journal-title":"Bioinformatics (Oxford, England)"},{"key":"2023012713011677400_btx758-B12","doi-asserted-by":"crossref","first-page":"511","DOI":"10.1007\/s10115-013-0673-3","article-title":"GUISE: a uniform sampler for constructing frequency histogram of graphlets","volume":"38","author":"Rahman","year":"2014","journal-title":"Knowledge Inform Syst"},{"key":"2023012713011677400_btx758-B13","doi-asserted-by":"crossref","first-page":"461.","DOI":"10.1093\/bioinformatics\/btw626","article-title":"A Cytoscape app for motif enumeration with ISMAGS","volume":"33","author":"Van Parys","year":"2017","journal-title":"Bioinformatics"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/34\/8\/1372\/48915964\/bioinformatics_34_8_1372.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/34\/8\/1372\/48915964\/bioinformatics_34_8_1372.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,29]],"date-time":"2023-08-29T01:06:37Z","timestamp":1693271197000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/34\/8\/1372\/4657074"}},"subtitle":[],"editor":[{"given":"Jonathan","family":"Wren","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"editor"}]}],"short-title":[],"issued":{"date-parts":[[2017,11,24]]},"references-count":13,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2018,4,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btx758","relation":{},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"value":"1367-4803","type":"print"},{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2018,4,15]]},"published":{"date-parts":[[2017,11,24]]}}}