{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,8]],"date-time":"2026-04-08T16:44:32Z","timestamp":1775666672247,"version":"3.50.1"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2016,10,6]],"date-time":"2016-10-06T00:00:00Z","timestamp":1475712000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2016,10,6]],"date-time":"2016-10-06T00:00:00Z","timestamp":1475712000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100007515","name":"National Youth Science Foundation","doi-asserted-by":"crossref","award":["1262451"],"award-info":[{"award-number":["1262451"]}],"id":[{"id":"10.13039\/100007515","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Bioinformatics"],"abstract":"<jats:title>Abstract<\/jats:title><jats:sec><jats:title>Background<\/jats:title><jats:p>Biological networks provide great potential to understand how cells function. Network motifs, frequent topological patterns, are key structures through which biological networks operate. Finding motifs in biological networks remains to be computationally challenging task as the size of the motif and the underlying network grow. Often, different copies of a given motif topology in a network share nodes or edges. Counting such overlapping copies introduces significant problems in motif identification.<\/jats:p><\/jats:sec><jats:sec><jats:title>Results<\/jats:title><jats:p>In this paper, we develop a scalable algorithm for finding network motifs. Unlike most of the existing studies, our algorithm counts independent copies of each motif topology. We introduce a set of small patterns and prove that we can construct any larger pattern by joining those patterns iteratively. By iteratively joining already identified motifs with those patterns, our algorithm avoids (i) constructing topologies which do not exist in the target network (ii) repeatedly counting the frequency of the motifs generated in subsequent iterations. Our experiments on real and synthetic networks demonstrate that our method is significantly faster and more accurate than the existing methods including SUBDUE and FSG.<\/jats:p><\/jats:sec><jats:sec><jats:title>Conclusions<\/jats:title><jats:p>We conclude that our method for finding network motifs is scalable and computationally feasible for large motif sizes and a broad range of networks with different sizes and densities. We proved that any motif with four or more edges can be constructed as a join of the small patterns.<\/jats:p><\/jats:sec>","DOI":"10.1186\/s12859-016-1271-7","type":"journal-article","created":{"date-parts":[[2016,10,6]],"date-time":"2016-10-06T04:11:38Z","timestamp":1475727098000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":23,"title":["Identification of large disjoint motifs in biological networks"],"prefix":"10.1186","volume":"17","author":[{"given":"Rasha","family":"Elhesha","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tamer","family":"Kahveci","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,10,6]]},"reference":[{"issue":"9","key":"1271_CR1","doi-asserted-by":"publisher","first-page":"1010","DOI":"10.1101\/gad.1528707","volume":"21","author":"X Zhu","year":"2007","unstructured":"Zhu X, Gerstein M, Snyder M. Getting connected: analysis and principles of biological networks. Genes Dev. 2007; 21(9):1010\u20131024.","journal-title":"Genes Dev"},{"issue":"5","key":"1271_CR2","doi-asserted-by":"publisher","first-page":"052708","DOI":"10.1103\/PhysRevE.89.052708","volume":"89","author":"DA Charlebois","year":"2014","unstructured":"Charlebois DA, Bal\u00e1zsi G, K\u00e6rn M. Coherent feedforward transcriptional regulatory motifs enhance drug resistance. Phys Rev E. 2014; 89(5):052708.","journal-title":"Phys Rev E"},{"issue":"3","key":"1271_CR3","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1089\/cmb.2010.0280","volume":"18","author":"F Ay","year":"2011","unstructured":"Ay F, Kellis M, Kahveci T. SubMAP: aligning metabolic pathways with subnetwork mappings. J Comput Biol. 2011; 18(3):219\u201335.","journal-title":"J Comput Biol"},{"issue":"1","key":"1271_CR4","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1016\/S0022-5193(03)00071-7","volume":"223","author":"S Wuchty","year":"2003","unstructured":"Wuchty S, Stadler PF. Centers of complex networks. J Theor Biol. 2003; 223(1):45\u201353.","journal-title":"J Theor Biol"},{"issue":"5594","key":"1271_CR5","doi-asserted-by":"publisher","first-page":"824","DOI":"10.1126\/science.298.5594.824","volume":"298","author":"R Milo","year":"2002","unstructured":"Milo R, Shen-Orr S, Itzkovitz S, Kashtan N, Chklovskii D, Alon U. Network motifs: simple building blocks of complex networks. Science. 2002; 298(5594):824\u20137.","journal-title":"Science"},{"issue":"1","key":"1271_CR6","doi-asserted-by":"publisher","first-page":"64","DOI":"10.1038\/ng881","volume":"31","author":"SS Shen-Orr","year":"2002","unstructured":"Shen-Orr SS, Milo R, Mangan S, Alon U. Network motifs in the transcriptional regulation network of escherichia coli. Nat Genet. 2002; 31(1):64\u20138.","journal-title":"Nat Genet"},{"issue":"8","key":"1271_CR7","doi-asserted-by":"publisher","first-page":"e106132","DOI":"10.1371\/journal.pone.0106132","volume":"9","author":"P Wang","year":"2014","unstructured":"Wang P, L\u00fc J, Yu X. Identification of important nodes in directed biological networks: A network motif approach. PLOS ONE. 2014; 9(8):e106132.","journal-title":"PLOS ONE"},{"issue":"2","key":"1271_CR8","doi-asserted-by":"publisher","first-page":"176","DOI":"10.1038\/ng1242","volume":"35","author":"S Wuchty","year":"2003","unstructured":"Wuchty S, Oltvai ZN, Barab\u00e1si AL. Evolutionary conservation of motif constituents in the yeast protein interaction network. Nat Genet. 2003; 35(2):176\u20139.","journal-title":"Nat Genet"},{"issue":"5","key":"1271_CR9","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1049\/iet-syb.2011.0011","volume":"6","author":"A Masoudi-Nejad","year":"2012","unstructured":"Masoudi-Nejad A, Schreiber F, Kashani Z. Building blocks of biological networks: a review on major network motif discovery algorithms. IET Syst Biol. 2012; 6(5):164\u201374.","journal-title":"IET Syst Biol"},{"issue":"1","key":"1271_CR10","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1186\/1471-2105-9-70","volume":"9","author":"T Milenkovi\u0107","year":"2008","unstructured":"Milenkovi\u0107 T, Lai J, Pr\u017eulj N. Graphcrunch: a tool for large network analyses. BMC Bioinformatics. 2008; 9(1):70.","journal-title":"BMC Bioinformatics"},{"issue":"8","key":"1271_CR11","doi-asserted-by":"publisher","first-page":"1036","DOI":"10.1109\/TKDE.2005.127","volume":"17","author":"M Deshpande","year":"2005","unstructured":"Deshpande M, Kuramochi M, Wale N, Karypis G. Frequent substructure-based approaches for classifying chemical compounds. IEEE Trans Knowl Data Eng. 2005; 17(8):1036\u201350.","journal-title":"IEEE Trans Knowl Data Eng"},{"issue":"7","key":"1271_CR12","doi-asserted-by":"publisher","first-page":"868","DOI":"10.1093\/bioinformatics\/btp090","volume":"25","author":"C Yanover","year":"2009","unstructured":"Yanover C, Singh M, Zaslavsky E. M are better than one: an ensemble-based motif finder and its application to regulatory element prediction. Bioinformatics. 2009; 25(7):868\u201374.","journal-title":"Bioinformatics"},{"key":"1271_CR13","unstructured":"Garey MR, Johnson DS. Computers and Intractability: A Guide to the Theory of NP-Completeness: WH Freeman New York; 1979."},{"key":"1271_CR14","doi-asserted-by":"crossref","unstructured":"Cook SA. The complexity of theorem-proving procedures. In: ACM Symposium on Theory of Computing. ACM: 1971. p. 151\u20138.","DOI":"10.1145\/800157.805047"},{"key":"1271_CR15","unstructured":"Holder LB, Cook DJ, Djoko S, et al. Substucture discovery in the subdue system. In: KDD Workshop. Workshop on Knowledge Discovery in Databases: 1994. p. 169\u201380."},{"key":"1271_CR16","doi-asserted-by":"crossref","unstructured":"Schreiber F, Schw\u00f6bbermeyer H. Frequency concepts and pattern detection for the analysis of motifs in networks. In: Transactions on Computational Systems Biology. Springer: 2005. p. 89\u2013104.","DOI":"10.1007\/11599128_7"},{"key":"1271_CR17","doi-asserted-by":"crossref","unstructured":"Vanetik N, Gudes E, Shimony SE. Computing frequent graph patterns from semistructured data. In: ICDM. IEEE: 2002. p. 458\u201365.","DOI":"10.1109\/ICDM.2002.1183988"},{"key":"1271_CR18","doi-asserted-by":"crossref","unstructured":"Yan X, Zhou X, Han J. Mining closed relational graphs with connectivity constraints. In: ACM SIGKDD. ACM: 2005. p. 324\u201333.","DOI":"10.1145\/1081870.1081908"},{"key":"1271_CR19","doi-asserted-by":"crossref","unstructured":"Grochow JA, Kellis M. Network motif discovery using subgraph enumeration and symmetry-breaking. In: Research in Computational Molecular Biology. Springer: 2007. p. 92\u2013106.","DOI":"10.1007\/978-3-540-71681-5_7"},{"issue":"11","key":"1271_CR20","doi-asserted-by":"publisher","first-page":"1746","DOI":"10.1093\/bioinformatics\/bth163","volume":"20","author":"N Kashtan","year":"2004","unstructured":"Kashtan N, Itzkovitz S, Milo R, Alon U. Efficient sampling algorithm for estimating subgraph concentrations and detecting network motifs. Bioinformatics. 2004; 20(11):1746\u201358.","journal-title":"Bioinformatics"},{"issue":"5","key":"1271_CR21","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1266\/ggs.84.385","volume":"84","author":"S Omidi","year":"2009","unstructured":"Omidi S, Schreiber F, Masoudi-Nejad A. Moda: an efficient algorithm for network motif discovery in biological networks. Genes Genet Syst. 2009; 84(5):385\u201395.","journal-title":"Genes Genet Syst."},{"issue":"4","key":"1271_CR22","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1109\/TCBB.2006.51","volume":"3","author":"S Wernicke","year":"2006","unstructured":"Wernicke S. Efficient detection of network motifs. IEEE\/ACM Trans Comput Biol Bioinformatics (TCBB). 2006; 3(4):347\u201359.","journal-title":"IEEE\/ACM Trans Comput Biol Bioinformatics (TCBB)"},{"key":"1271_CR23","doi-asserted-by":"crossref","unstructured":"Chen J, Hsu W, Lee ML, Ng SK. Nemofinder: Dissecting genome-wide protein-protein interactions with meso-scale network motifs. In: ACM SIGKDD. ACM: 2006. p. 106\u201315.","DOI":"10.1145\/1150402.1150418"},{"issue":"1","key":"1271_CR24","doi-asserted-by":"publisher","first-page":"318","DOI":"10.1186\/1471-2105-10-318","volume":"10","author":"ZR Kashani","year":"2009","unstructured":"Kashani ZR, Ahrabian H, Elahi E, Nowzari-Dalini A, Ansari ES, Asadi S, Mohammadi S, Schreiber F, Masoudi-Nejad A. Kavosh: a new algorithm for finding network motifs. BMC Bioinformatics. 2009; 10(1):318.","journal-title":"BMC Bioinformatics"},{"issue":"9","key":"1271_CR25","doi-asserted-by":"publisher","first-page":"1038","DOI":"10.1109\/TKDE.2004.33","volume":"16","author":"M Kuramochi","year":"2004","unstructured":"Kuramochi M, Karypis G. An efficient algorithm for discovering frequent subgraphs. IEEE Trans Knowl Data Eng. 2004; 16(9):1038\u20131051.","journal-title":"IEEE Trans Knowl Data Eng"},{"issue":"3","key":"1271_CR26","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1007\/s10618-005-0003-9","volume":"11","author":"M Kuramochi","year":"2005","unstructured":"Kuramochi M, Karypis G. Finding frequent patterns in a large sparse graph. Data Mining Knowl Discov. 2005; 11(3):243\u201371.","journal-title":"Data Mining Knowl Discov"},{"key":"1271_CR27","doi-asserted-by":"crossref","unstructured":"Babai L, Luks EM. Canonical labeling of graphs. In: ACM Symposium on Theory of Computing. ACM: 1983. p. 171\u201383.","DOI":"10.1145\/800061.808746"},{"issue":"5439","key":"1271_CR28","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1126\/science.286.5439.509","volume":"286","author":"AL Barab\u00e1si","year":"1999","unstructured":"Barab\u00e1si AL, Albert R. Emergence of scaling in random networks. Science. 1999; 286(5439):509\u201312.","journal-title":"Science"},{"key":"1271_CR29","doi-asserted-by":"publisher","first-page":"051903","DOI":"10.1103\/PhysRevE.74.051903","volume":"74","author":"K Baskerville","year":"2006","unstructured":"Baskerville K, Paczuski M. Subgraph ensembles and motif discovery using a new heuristic for graph isomorphism. Phys Rev E. 2006; 74:051903.","journal-title":"Phys Rev E"},{"issue":"suppl 1","key":"1271_CR30","doi-asserted-by":"publisher","first-page":"572","DOI":"10.1093\/nar\/gkl950","volume":"35","author":"A Chatr-Aryamontri","year":"2007","unstructured":"Chatr-Aryamontri A, Ceol A, Palazzi LM, Nardelli G, Schneider MV, Castagnoli L, Cesareni G. MINT: the Molecular INTeraction database. Nucleic Acids Res. 2007; 35(suppl 1):572\u20134.","journal-title":"Nucleic Acids Res"},{"issue":"21","key":"1271_CR31","doi-asserted-by":"publisher","first-page":"4633","DOI":"10.1103\/PhysRevLett.85.4633","volume":"85","author":"SN Dorogovtsev","year":"2000","unstructured":"Dorogovtsev SN, Mendes JFF, Samukhin AN. Structure of growing networks with preferential linking. Phys Rev Lett. 2000; 85(21):4633.","journal-title":"Phys Rev Lett"},{"issue":"6804","key":"1271_CR32","doi-asserted-by":"publisher","first-page":"651","DOI":"10.1038\/35036627","volume":"407","author":"H Jeong","year":"2000","unstructured":"Jeong H, Tombor B, Albert R, Oltvai ZN, Barab\u00e1si AL. The large-scale organization of metabolic networks. Nature. 2000; 407(6804):651\u20134.","journal-title":"Nature"},{"issue":"2","key":"1271_CR33","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1007\/s100510050359","volume":"4","author":"S Redner","year":"1998","unstructured":"Redner S. How popular is your paper? an empirical study of the citation distribution. Eur Phys J B-Condensed Matter Complex Syst. 1998; 4(2):131\u20134.","journal-title":"Eur Phys J B-Condensed Matter Complex Syst"},{"issue":"1","key":"1271_CR34","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1038\/msb.2008.52","volume":"4","author":"RD Leclerc","year":"2008","unstructured":"Leclerc RD. Survival of the sparsest: robust gene networks are parsimonious. Mol Syst Biol. 2008; 4(1):213.","journal-title":"Mol Syst Biol"},{"key":"1271_CR35","unstructured":"Milo R, Kashtan N, Itzkovitz S, Newman ME, Alon U. On the uniform generation of random graphs with prescribed degree sequences. 2003. arXiv preprint cond-mat\/0312028."},{"issue":"2","key":"1271_CR36","doi-asserted-by":"publisher","first-page":"1073","DOI":"10.2140\/pjm.1957.7.1073","volume":"7","author":"D Gale","year":"1957","unstructured":"Gale D, et al. A theorem on flows in networks. Pacific J Math. 1957; 7(2):1073\u201382.","journal-title":"Pacific J Math"},{"issue":"1","key":"1271_CR37","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1038\/75556","volume":"25","author":"M Ashburner","year":"2000","unstructured":"Ashburner M, Ball CA, et al. Gene ontology: tool for the unification of biology. Nat Genet. 2000; 25(1):25\u20139.","journal-title":"Nat Genet"},{"issue":"2","key":"1271_CR38","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1002\/(SICI)1099-1654(199707)7:2<107::AID-RMV191>3.0.CO;2-M","volume":"7","author":"FL Homa","year":"1997","unstructured":"Homa FL, Brown JC. Capsid assembly and dna packaging in herpes simplex virus. Rev Med Virol. 1997; 7(2):107.","journal-title":"Rev Med Virol"}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s12859-016-1271-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1186\/s12859-016-1271-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s12859-016-1271-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,11]],"date-time":"2025-06-11T01:23:21Z","timestamp":1749605001000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/s12859-016-1271-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,10,6]]},"references-count":38,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2016,12]]}},"alternative-id":["1271"],"URL":"https:\/\/doi.org\/10.1186\/s12859-016-1271-7","relation":{},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,10,6]]},"assertion":[{"value":"6 April 2016","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 September 2016","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 October 2016","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"408"}}