{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,4]],"date-time":"2026-05-04T23:25:12Z","timestamp":1777937112194,"version":"3.51.4"},"reference-count":22,"publisher":"Oxford University Press (OUP)","issue":"13","license":[{"start":{"date-parts":[[2016,10,2]],"date-time":"2016-10-02T00:00:00Z","timestamp":1475366400000},"content-version":"vor","delay-in-days":3015,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc\/2.0\/uk\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008,7,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Protein\u2013protein interaction (PPI) networks of many organisms share global topological features such as degree distribution, k-hop reachability, betweenness and closeness. Yet, some of these networks can differ significantly from the others in terms of local structures: e.g. the number of specific network motifs can vary significantly among PPI networks.<\/jats:p>\n               <jats:p>Counting the number of network motifs provides a major challenge to compare biomolecular networks. Recently developed algorithms have been able to count the number of induced occurrences of subgraphs with k\u2264 7 vertices. Yet no practical algorithm exists for counting non-induced occurrences, or counting subgraphs with k\u2265 8 vertices. Counting non-induced occurrences of network motifs is not only challenging but also quite desirable as available PPI networks include several false interactions and miss many others.<\/jats:p>\n               <jats:p>In this article, we show how to apply the \u2018color coding\u2019 technique for counting non-induced occurrences of subgraph topologies in the form of trees and bounded treewidth subgraphs. Our algorithm can count all occurrences of motif G\u2032 with k vertices in a network G with n vertices in time polynomial with n, provided k=O(log n). We use our algorithm to obtain \u2018treelet\u2019 distributions for k\u2264 10 of available PPI networks of unicellular organisms (Saccharomyces cerevisiae Escherichia coli and Helicobacter Pyloris), which are all quite similar, and a multicellular organism (Caenorhabditis elegans) which is significantly different. Furthermore, the treelet distribution of the unicellular organisms are similar to that obtained by the \u2018duplication model\u2019 but are quite different from that of the \u2018preferential attachment model\u2019. The treelet distribution is robust w.r.t. sparsification with bait\/edge coverage of 70% but differences can be observed when bait\/edge coverage drops to 50%.<\/jats:p>\n               <jats:p>Contact: \u00a0cenk@cs.sfu.ca<\/jats:p>","DOI":"10.1093\/bioinformatics\/btn163","type":"journal-article","created":{"date-parts":[[2008,6,27]],"date-time":"2008-06-27T07:43:13Z","timestamp":1214552593000},"page":"i241-i249","source":"Crossref","is-referenced-by-count":166,"title":["Biomolecular network motif counting and discovery by color coding"],"prefix":"10.1093","volume":"24","author":[{"given":"Noga","family":"Alon","sequence":"first","affiliation":[{"name":"1 Schools of Mathematical Sciences and Computer Science, Tel Aviv University, Ramat Aviv, Israel and 2School of Computing Science, Simon Fraser University, Burnaby, BC, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Phuong","family":"Dao","sequence":"additional","affiliation":[{"name":"1 Schools of Mathematical Sciences and Computer Science, Tel Aviv University, Ramat Aviv, Israel and 2School of Computing Science, Simon Fraser University, Burnaby, BC, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Iman","family":"Hajirasouliha","sequence":"additional","affiliation":[{"name":"1 Schools of Mathematical Sciences and Computer Science, Tel Aviv University, Ramat Aviv, Israel and 2School of Computing Science, Simon Fraser University, Burnaby, BC, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fereydoun","family":"Hormozdiari","sequence":"additional","affiliation":[{"name":"1 Schools of Mathematical Sciences and Computer Science, Tel Aviv University, Ramat Aviv, Israel and 2School of Computing Science, Simon Fraser University, Burnaby, BC, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"S. Cenk","family":"Sahinalp","sequence":"additional","affiliation":[{"name":"1 Schools of Mathematical Sciences and Computer Science, Tel Aviv University, Ramat Aviv, Israel and 2School of Computing Science, Simon Fraser University, Burnaby, BC, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2008,7,1]]},"reference":[{"key":"2023020210382269400_B1","first-page":"435","article-title":"Balanced families of perfect hash functions and their applications","volume-title":"Proc. ICALP","author":"Alon","year":"2007"},{"key":"2023020210382269400_B2","doi-asserted-by":"crossref","first-page":"844","DOI":"10.1145\/210332.210337","article-title":"Color-coding","volume":"42","author":"Alon","year":"1995","journal-title":"J. ACM"},{"key":"2023020210382269400_B3","first-page":"453","article-title":"Approximation algorithms for some parameterized counting problems","volume-title":"In Proceedings of the 13th International Symposium on Algorithms and Computation (ISAAC'02)","author":"Arvind","year":"2002"},{"key":"2023020210382269400_B4","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1126\/science.286.5439.509","article-title":"Emergence of scaling in random networks","volume":"286","author":"Barab\u00e1si","year":"1999","journal-title":"Science"},{"key":"2023020210382269400_B5","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1016\/j.tcs.2006.08.045","article-title":"The degree distribution of the generalized duplication model","volume":"369","author":"Bebek","year":"2006","journal-title":"Theor. Comput. Sci."},{"key":"2023020210382269400_B6","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1002\/rsa.1009","article-title":"The degree sequence of a scale-free random graph process","volume":"18","author":"Bollob\u00e1s","year":"2001","journal-title":"Random Struct. Algorithms"},{"key":"2023020210382269400_B7","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1080\/10586458.2001.10504428","article-title":"A random graph model for power law graphs","volume":"10","author":"Chung","year":"2001","journal-title":"Experimental Math."},{"key":"2023020210382269400_B8","doi-asserted-by":"crossref","first-page":"677","DOI":"10.1089\/106652703322539024","article-title":"Duplication models for biological networks","volume":"10","author":"Chung","year":"2003","journal-title":"J. Comput. Biol."},{"key":"2023020210382269400_B9","first-page":"1","article-title":"Qnet: a tool for querying protein interaction networks","volume-title":"RECOMB","author":"Dost","year":"2007"},{"key":"2023020210382269400_B10","doi-asserted-by":"crossref","DOI":"10.1103\/PhysRevLett.91.138701","article-title":"Preferential attachment in the protein network evolution","volume":"91","author":"Eisenberg","year":"2003","journal-title":"Phys. Rev. Lett."},{"key":"2023020210382269400_B11","doi-asserted-by":"crossref","first-page":"290","DOI":"10.5486\/PMD.1959.6.3-4.12","article-title":"On random graphs","volume":"6","author":"Erdos","year":"1959","journal-title":"Publicationes Mathematicae"},{"key":"2023020210382269400_B12","first-page":"92","article-title":"Network motif discovery using subgraph enumeration and symmetry-breaking","volume-title":"RECOMB","author":"Grochow","year":"2007"},{"key":"2023020210382269400_B13","doi-asserted-by":"crossref","first-page":"839","DOI":"10.1038\/nbt1116","article-title":"Effect of sampling on topology predictions of protein\u2013protein interaction networks","volume":"23","author":"Han","year":"2005","journal-title":"Nat. Biotech"},{"key":"2023020210382269400_B14","doi-asserted-by":"crossref","DOI":"10.1371\/journal.pcbi.0030118","article-title":"Not all scale-free networks are born equal: the role of the seed graph in ppi network evolution","volume":"3","author":"Hormozdiari","year":"2007","journal-title":"PLoS Comput. Biol"},{"key":"2023020210382269400_B15","first-page":"56","article-title":"Monte-carlo algorithms for enumeration and reliability problems","volume-title":"FOCS","author":"Karp","year":"1983"},{"key":"2023020210382269400_B16","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":"2023020210382269400_B17","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"},{"key":"2023020210382269400_B18","doi-asserted-by":"crossref","first-page":"3508","DOI":"10.1093\/bioinformatics\/bth436","article-title":"Modeling interactome: scale-free or geometric?","volume":"20","author":"Przulj","year":"2004","journal-title":"Bioinformatics"},{"key":"2023020210382269400_B19","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1089\/cmb.2006.13.133","article-title":"Efficient algorithms for detecting signaling pathways in protein interaction networks","volume":"13","author":"Scott","year":"2006","journal-title":"J. Comput. Biol"},{"key":"2023020210382269400_B20","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1186\/1471-2105-7-199","article-title":"Qpath: a method for querying pathways in a protein\u2013protein interaction network","volume":"7","author":"Shlomi","year":"2006","journal-title":"BMC Bioinformatics"},{"key":"2023020210382269400_B21","doi-asserted-by":"crossref","first-page":"38","DOI":"10.1159\/000067642","article-title":"Modelling of protein interaction networks","volume":"1","author":"V\u00e1zquez","year":"2003","journal-title":"Complexus"},{"key":"2023020210382269400_B22","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1093\/nar\/30.1.303","article-title":"Dip, the database of interacting proteins: a research tool for studying cellular networks of protein interactions","volume":"30","author":"Xenarios","year":"2002","journal-title":"Nucl. Acids Res."}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/24\/13\/i241\/49054100\/bioinformatics_24_13_i241.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/24\/13\/i241\/49054100\/bioinformatics_24_13_i241.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,2]],"date-time":"2023-02-02T12:20:02Z","timestamp":1675340402000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/24\/13\/i241\/232086"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,7,1]]},"references-count":22,"journal-issue":{"issue":"13","published-print":{"date-parts":[[2008,7,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btn163","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2008,7,1]]},"published":{"date-parts":[[2008,7,1]]}}}