{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,2]],"date-time":"2026-07-02T06:53:16Z","timestamp":1782975196027,"version":"3.54.5"},"reference-count":34,"publisher":"Oxford University Press (OUP)","issue":"9","license":[{"start":{"date-parts":[[2017,12,11]],"date-time":"2017-12-11T00:00:00Z","timestamp":1512950400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/about_us\/legal\/notices"}],"funder":[{"DOI":"10.13039\/100000002","name":"NIH","doi-asserted-by":"publisher","award":["GM097188"],"award-info":[{"award-number":["GM097188"]}],"id":[{"id":"10.13039\/100000002","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100009612","name":"Oregon State University","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100009612","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018,5,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:sec>\n                    <jats:title>Motivation<\/jats:title>\n                    <jats:p>Genomic networks represent a complex map of molecular interactions which are descriptive of the biological processes occurring in living cells. Identifying the small over-represented circuitry patterns in these networks helps generate hypotheses about the functional basis of such complex processes. Network motif discovery is a systematic way of achieving this goal. However, a reliable network motif discovery outcome requires generating random background networks which are the result of a uniform and independent graph sampling method. To date, there has been no method to numerically evaluate whether any network motif discovery algorithm performs as intended on realistically sized datasets\u2014thus it was not possible to assess the validity of resulting network motifs.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Results<\/jats:title>\n                    <jats:p>In this work, we present IndeCut, the first method to date that characterizes network motif finding algorithm performance in terms of uniform sampling on realistically sized networks. We demonstrate that it is critical to use IndeCut prior to running any network motif finder for two reasons. First, IndeCut indicates the number of samples needed for a tool to produce an outcome that is both reproducible and accurate. Second, IndeCut allows users to choose the tool that generates samples in the most independent fashion for their network of interest among many available options.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Availability and implementation<\/jats:title>\n                    <jats:p>The open source software package is available at https:\/\/github.com\/megrawlab\/IndeCut.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Supplementary information<\/jats:title>\n                    <jats:p>Supplementary data are available at Bioinformatics online.<\/jats:p>\n                  <\/jats:sec>","DOI":"10.1093\/bioinformatics\/btx798","type":"journal-article","created":{"date-parts":[[2017,12,8]],"date-time":"2017-12-08T07:21:40Z","timestamp":1512717700000},"page":"1514-1521","source":"Crossref","is-referenced-by-count":8,"title":["IndeCut evaluates performance of network motif discovery algorithms"],"prefix":"10.1093","volume":"34","author":[{"given":"Mitra","family":"Ansariola","sequence":"first","affiliation":[{"name":"Center for Genome Research and Biocomputing, Oregon State University, Corvallis, OR, USA"},{"name":"Department of Botany and Plant Pathology, Oregon State University, Corvallis, OR, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Molly","family":"Megraw","sequence":"additional","affiliation":[{"name":"Center for Genome Research and Biocomputing, Oregon State University, Corvallis, OR, USA"},{"name":"Department of Botany and Plant Pathology, Oregon State University, Corvallis, OR, USA"},{"name":"Department of Computer Science, Oregon State University, Corvallis, OR, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"David","family":"Koslicki","sequence":"additional","affiliation":[{"name":"Center for Genome Research and Biocomputing, Oregon State University, Corvallis, OR, USA"},{"name":"Department of Mathematics, Oregon State University, Corvallis, OR, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"286","published-online":{"date-parts":[[2017,12,11]]},"reference":[{"key":"2023012713023591000_btx798-B1","doi-asserted-by":"crossref","first-page":"787","DOI":"10.1137\/S0097539704441629","article-title":"Approximating the cut-norm via grothendieck\u2019s inequality","volume":"35","author":"Alon","year":"2006","journal-title":"SIAM J. Comput"},{"key":"2023012713023591000_btx798-B2","doi-asserted-by":"crossref","first-page":"450","DOI":"10.1038\/nrg2102","article-title":"Network motifs: theory and experimental approaches","volume":"8","author":"Alon","year":"2007","journal-title":"Nat. Rev. Genet"},{"key":"2023012713023591000_btx798-B3","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":"2023012713023591000_btx798-B4","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1038\/nrg1272","article-title":"Network biology: understanding the cell\u2019s functional organization","volume":"5","author":"Barabasi","year":"2004","journal-title":"Nat. Rev. Genet"},{"key":"2023012713023591000_btx798-B5","doi-asserted-by":"crossref","first-page":"316","DOI":"10.1016\/j.aim.2009.12.001","article-title":"On the number of matrices and a random matrix with prescribed row and column sums and 0\u20131 entries","volume":"224","author":"Barvinok","year":"2010","journal-title":"Adv. Math"},{"key":"2023012713023591000_btx798-B6","doi-asserted-by":"crossref","first-page":"860","DOI":"10.1007\/s00453-009-9340-1","article-title":"A sequential algorithm for generating random graphs","volume":"58","author":"Bayati","year":"2010","journal-title":"Algorithmica"},{"key":"2023012713023591000_btx798-B7","doi-asserted-by":"crossref","first-page":"168","DOI":"10.1002\/rsa.20155","article-title":"Sampling binary contingency tables with a greedy start","volume":"30","author":"Bez\u00e1kov\u00e1","year":"2007","journal-title":"Random Struct. Algorithms"},{"key":"2023012713023591000_btx798-B8","doi-asserted-by":"crossref","first-page":"489","DOI":"10.1080\/15427951.2010.557277","article-title":"A sequential importance sampling algorithm for generating random graphs with prescribed degrees","volume":"6","author":"Blitzstein","year":"2011","journal-title":"Internet Math"},{"key":"2023012713023591000_btx798-B9","doi-asserted-by":"crossref","first-page":"1400","DOI":"10.1214\/10-AAP728","article-title":"Random graphs with a given degree sequence","volume":"21","author":"Chatterjee","year":"2011","journal-title":"Ann. Appl. Probab"},{"key":"2023012713023591000_btx798-B10","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1198\/016214504000001303","article-title":"Sequential monte carlo methods for statistical analysis of tables","volume":"100","author":"Chen","year":"2005","journal-title":"J. Am. Stat. Assoc"},{"key":"2023012713023591000_btx798-B11","article-title":"Configuring random graph models with fixed degree sequences","author":"Fosdick","year":"2016","journal-title":"arXiv Preprint arXiv"},{"key":"2023012713023591000_btx798-B12","doi-asserted-by":"crossref","first-page":"3388","DOI":"10.1093\/bioinformatics\/btm454","article-title":"Dia-mcis: an importance sampling network randomizer for network motif discovery and other topological observables in transcription networks","volume":"23","author":"Fusco","year":"2007","journal-title":"Bioinformatics"},{"key":"2023012713023591000_btx798-B13","doi-asserted-by":"crossref","first-page":"575","DOI":"10.1146\/annurev-arplant-043015-112205","article-title":"Mapping transcriptional networks in plants: Data-driven discovery of novel biological mechanisms","volume":"67","author":"Gaudinier","year":"2016","journal-title":"Annual Review of Plant Biology"},{"key":"2023012713023591000_btx798-B14","first-page":"1564","volume-title":"Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Greenhill","year":"2015"},{"key":"2023012713023591000_btx798-B15","first-page":"92","volume-title":"Annual International Conference on Research in Computational Molecular Biology","author":"Grochow","year":"2007"},{"key":"2023012713023591000_btx798-B16","doi-asserted-by":"crossref","first-page":"026127.","DOI":"10.1103\/PhysRevE.68.026127","article-title":"Subgraphs in random networks","volume":"68","author":"Itzkovitz","year":"2003","journal-title":"Phys. Rev. E"},{"key":"2023012713023591000_btx798-B17","doi-asserted-by":"crossref","first-page":"469","DOI":"10.1109\/TST.2013.6616521","article-title":"Network motif detection: algorithms, parallel and cloud computing, and related tools","volume":"18","author":"Kim","year":"2013","journal-title":"Tsinghua Sci. Technol"},{"key":"2023012713023591000_btx798-B18","doi-asserted-by":"crossref","first-page":"058101.","DOI":"10.1103\/PhysRevE.70.058101","article-title":"Comment on \u201csubgraphs in random networks\u201d","volume":"70","author":"King","year":"2004","journal-title":"Phys. Rev. E"},{"key":"2023012713023591000_btx798-B19","doi-asserted-by":"crossref","first-page":"2348","DOI":"10.1093\/bioinformatics\/btv159","article-title":"A novel motif-discovery algorithm to identify co-regulatory motifs in large transcription factor and microrna co-regulatory networks in human","volume":"31","author":"Liang","year":"2015","journal-title":"Bioinformatics"},{"key":"2023012713023591000_btx798-B20","doi-asserted-by":"crossref","first-page":"11980","DOI":"10.1073\/pnas.2133841100","article-title":"Structure and function of the feed-forward loop network motif","volume":"100","author":"Mangan","year":"2003","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"2023012713023591000_btx798-B21","doi-asserted-by":"crossref","first-page":"1.","DOI":"10.1186\/gb-2013-14-8-r85","article-title":"Sustained-input switches for transcription factors and micrornas are central building blocks of eukaryotic gene circuits","volume":"14","author":"Megraw","year":"2013","journal-title":"Genome Biol"},{"key":"2023012713023591000_btx798-B22","doi-asserted-by":"crossref","first-page":"P16","DOI":"10.37236\/3028","article-title":"Towards random uniform sampling of bipartite graphs with given degree sequence","volume":"20","author":"Mikl\u00f3s","year":"2013","journal-title":"Electronic J. Combinatorics"},{"key":"2023012713023591000_btx798-B23","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":"2023012713023591000_btx798-B24","author":"Milo","year":"2003"},{"key":"2023012713023591000_btx798-B25","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1109\/e-Science.2009.20","article-title":"Strategies for network motifs discovery","volume-title":"e-Science, 2009. e-Science'09. Fifth IEEE International Conference","author":"Ribeiro","year":"2009"},{"key":"2023012713023591000_btx798-B26","doi-asserted-by":"crossref","first-page":"1787","DOI":"10.1126\/science.1198374","article-title":"Identification of functional elements and regulatory circuits by drosophila modencode","volume":"330","author":"Roy","year":"2010","journal-title":"Science"},{"key":"2023012713023591000_btx798-B27","doi-asserted-by":"crossref","first-page":"64","DOI":"10.1038\/ng881","article-title":"Network motifs in the transcriptional regulation network of escherichia coli","volume":"31","author":"Shen-Orr","year":"2002","journal-title":"Nat. Genet"},{"key":"2023012713023591000_btx798-B28","doi-asserted-by":"crossref","first-page":"714","DOI":"10.1016\/j.cell.2015.04.014","article-title":"Making sense of transcription networks","volume":"161","author":"Sorrells","year":"2015","journal-title":"Cell"},{"key":"2023012713023591000_btx798-B29","doi-asserted-by":"crossref","first-page":"1.","DOI":"10.1186\/1479-7364-4-5-353","article-title":"A survey of current software for network analysis in molecular biology","volume":"4","author":"Thomas","year":"2010","journal-title":"Hum. Genomics"},{"key":"2023012713023591000_btx798-B30","doi-asserted-by":"crossref","first-page":"49.","DOI":"10.4137\/BBI.S23619","article-title":"Cross-disciplinary detection and analysis of network motifs","volume":"9","author":"Tran","year":"2015","journal-title":"Bioinf. Biol. Insights"},{"key":"2023012713023591000_btx798-B31","doi-asserted-by":"crossref","first-page":"312","DOI":"10.1109\/TBCAS.2014.2343620","article-title":"Duplication and divergence effect on network motifs in undirected bio-molecular networks","volume":"9","author":"Wang","year":"2015","journal-title":"IEEE Trans. Biomed. Circuits Syst"},{"key":"2023012713023591000_btx798-B32","doi-asserted-by":"crossref","first-page":"1152","DOI":"10.1093\/bioinformatics\/btl038","article-title":"Fanmod: a tool for fast network motif detection","volume":"22","author":"Wernicke","year":"2006","journal-title":"Bioinformatics"},{"key":"2023012713023591000_btx798-B33","doi-asserted-by":"crossref","first-page":"1.","DOI":"10.1186\/1752-0509-7-90","article-title":"Topology of molecular interaction networks","volume":"7","author":"Winterbach","year":"2013","journal-title":"BMC Syst. Biol"},{"key":"2023012713023591000_btx798-B34","first-page":"202","article-title":"Biological network motif detection: principles and practice","volume-title":"Brief. Bioinf.","author":"Wong","year":"2011"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/34\/9\/1514\/48916030\/bioinformatics_34_9_1514.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/34\/9\/1514\/48916030\/bioinformatics_34_9_1514.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,27]],"date-time":"2023-01-27T08:56:11Z","timestamp":1674809771000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/34\/9\/1514\/4721785"}},"subtitle":[],"editor":[{"given":"Jonathan","family":"Wren","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"editor"}]}],"short-title":[],"issued":{"date-parts":[[2017,12,11]]},"references-count":34,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2018,5,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btx798","relation":{"has-preprint":[{"id-type":"doi","id":"10.1101\/156836","asserted-by":"object"}]},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"value":"1367-4803","type":"print"},{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2018,5,1]]},"published":{"date-parts":[[2017,12,11]]}}}