{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,20]],"date-time":"2026-04-20T10:27:02Z","timestamp":1776680822237,"version":"3.51.2"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"1","content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Bioinformatics"],"published-print":{"date-parts":[[2009,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:sec>\n            <jats:title>Background<\/jats:title>\n            <jats:p>Complex networks are studied across many fields of science and are particularly important to understand biological processes. Motifs in networks are small connected sub-graphs that occur significantly in higher frequencies than in random networks. They have recently gathered much attention as a useful concept to uncover structural design principles of complex networks. Existing algorithms for finding network motifs are extremely costly in CPU time and memory consumption and have practically restrictions on the size of motifs.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Results<\/jats:title>\n            <jats:p>We present a new algorithm (Kavosh), for finding k-size network motifs with less memory and CPU time in comparison to other existing algorithms. Our algorithm is based on counting all k-size sub-graphs of a given graph (directed or undirected). We evaluated our algorithm on biological networks of <jats:italic>E. coli<\/jats:italic> and <jats:italic>S. cereviciae<\/jats:italic>, and also on non-biological networks: a social and an electronic network.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Conclusion<\/jats:title>\n            <jats:p>The efficiency of our algorithm is demonstrated by comparing the obtained results with three well-known motif finding tools. For comparison, the CPU time, memory usage and the similarities of obtained motifs are considered. Besides, Kavosh can be employed for finding motifs of size greater than eight, while most of the other algorithms have restriction on motifs with size greater than eight. The Kavosh source code and help files are freely available at: <jats:ext-link xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"http:\/\/Lbb.ut.ac.ir\/Download\/LBBsoft\/Kavosh\/\" ext-link-type=\"uri\">http:\/\/Lbb.ut.ac.ir\/Download\/LBBsoft\/Kavosh\/<\/jats:ext-link>.<\/jats:p>\n          <\/jats:sec>","DOI":"10.1186\/1471-2105-10-318","type":"journal-article","created":{"date-parts":[[2009,10,6]],"date-time":"2009-10-06T06:14:18Z","timestamp":1254809658000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":184,"title":["Kavosh: a new algorithm for finding network motifs"],"prefix":"10.1186","volume":"10","author":[{"given":"Zahra Razaghi Moghadam","family":"Kashani","sequence":"first","affiliation":[]},{"given":"Hayedeh","family":"Ahrabian","sequence":"additional","affiliation":[]},{"given":"Elahe","family":"Elahi","sequence":"additional","affiliation":[]},{"given":"Abbas","family":"Nowzari-Dalini","sequence":"additional","affiliation":[]},{"given":"Elnaz Saberi","family":"Ansari","sequence":"additional","affiliation":[]},{"given":"Sahar","family":"Asadi","sequence":"additional","affiliation":[]},{"given":"Shahin","family":"Mohammadi","sequence":"additional","affiliation":[]},{"given":"Falk","family":"Schreiber","sequence":"additional","affiliation":[]},{"given":"Ali","family":"Masoudi-Nejad","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2009,10,4]]},"reference":[{"issue":"6995","key":"3048_CR1","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1038\/nature02555","volume":"430","author":"JD Han","year":"2004","unstructured":"Han JD, Bertin N, Hao T, Goldberg D, Berriz G, Zhang L, Dupuy D, Walhout A, Cusick M, Roth F, Vidal M: Evidence for dynamically organized modularity in the yeast protein-protein interaction network. Nature 2004, 430(6995):88\u201393. 10.1038\/nature02555","journal-title":"Nature"},{"key":"3048_CR2","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1089\/cmb.2006.13.145","volume":"13","author":"A Jaimovich","year":"2006","unstructured":"Jaimovich A, Elidan G, Margalit H, Friedman N: Towards an integrated protein-protein interaction network: a relational markov network approach. J Comp Bio 2006, 13: 145\u2013164. 10.1089\/cmb.2006.13.145","journal-title":"J Comp Bio"},{"key":"3048_CR3","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1038\/35075138","volume":"411","author":"H Jeong","year":"2001","unstructured":"Jeong H, Mason S, Barabasi AL, Oltvai Z: Centrality and lethality of protein networks. Nature 2001, 411: 41\u201342. 10.1038\/35075138","journal-title":"Nature"},{"key":"3048_CR4","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 Z, Barabasi AL: The large-scale organization of metabolic networks. Nature 2000, 407: 651\u2013654. 10.1038\/35036627","journal-title":"Nature"},{"key":"3048_CR5","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 sub-graph concentrations and detecting network motifs. Bioinformatics 2004, 20: 1746\u20131758. 10.1093\/bioinformatics\/bth163","journal-title":"Bioinformatics"},{"key":"3048_CR6","first-page":"77","volume":"2265","author":"V Batagelj","year":"2003","unstructured":"Batagelj V, Mrvar A: Pajek-analysis and visualization of large networks. Springer-Verlag 2003, 2265: 77\u2013103.","journal-title":"Springer-Verlag"},{"key":"3048_CR7","doi-asserted-by":"publisher","first-page":"3572","DOI":"10.1093\/bioinformatics\/bti556","volume":"21","author":"F Schreiber","year":"2005","unstructured":"Schreiber F, Schw\u00f6bbermeyer H: Mavisto: a tool for the exploration of network motifs. Bioinformatics 2005, 21: 3572\u20133574. 10.1093\/bioinformatics\/bti556","journal-title":"Bioinformatics"},{"key":"3048_CR8","doi-asserted-by":"publisher","first-page":"1152","DOI":"10.1093\/bioinformatics\/btl038","volume":"22","author":"S Wernicke","year":"2006","unstructured":"Wernicke S, Rasche F: FANMOD: a tool for fast network motif detection. Bioinformatics 2006, 22: 1152\u20131153. 10.1093\/bioinformatics\/btl038","journal-title":"Bioinformatics"},{"key":"3048_CR9","doi-asserted-by":"publisher","first-page":"106","DOI":"10.1145\/1150402.1150418","volume-title":"Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, New York, NY","author":"J Chen","year":"2006","unstructured":"Chen J, Hsu W, Lee ML, Ng SK: NeMoFinder: Dissecting genome-wide protein-protein interactions with meso-scale network motifs. Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, New York, NY 2006, 106\u2013115."},{"key":"3048_CR10","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1186\/1471-2105-4-2","volume":"4","author":"GD Bader","year":"2003","unstructured":"Bader GD, Hogue CW: An automated method for finding molecular complexes in large protein interaction networks. BMC Bioinformatics. 2003, 4: 2.","journal-title":"BMC Bioinformatics."},{"issue":"9","key":"3048_CR11","doi-asserted-by":"publisher","first-page":"1124","DOI":"10.1093\/bioinformatics\/btm064","volume":"23","author":"B Andreopoulos","year":"2007","unstructured":"Andreopoulos B, An A, Wang X, Faloutsos M, Schroeder M: Clustering by common friends finds locally significant proteins mediating modules. Bioinformatics 2007, 23(9):1124\u20131131. 10.1093\/bioinformatics\/btm064","journal-title":"Bioinformatics"},{"key":"3048_CR12","doi-asserted-by":"crossref","unstructured":"Royer L, Reimann M, Andreopoulos B, Schroeder M: Unraveling Protein Networks with Power Graph Analysis. PLoS Computational Biology 2008., 4(7): 10.1371\/journal.pcbi.1000108","DOI":"10.1371\/journal.pcbi.1000108"},{"key":"3048_CR13","unstructured":"The E. coli Database[http:\/\/www.kegg.com\/]"},{"key":"3048_CR14","unstructured":"The S. cerevisiae Database[http:\/\/www.weizmann.ac.il\/mcb\/UriAlon\/]"},{"key":"3048_CR15","volume-title":"Combinatorial algorithms: Generation, Enumeration and Search","author":"D Kreher","year":"1998","unstructured":"Kreher D, Stinson D: Combinatorial algorithms: Generation, Enumeration and Search. Florida: CRC Press LTC; 1998."},{"key":"3048_CR16","first-page":"45","volume":"30","author":"B McKay","year":"1981","unstructured":"McKay B: Practical graph isomorphism. Congr Numer 1981, 30: 45\u201387.","journal-title":"Congr Numer"},{"issue":"5569","key":"3048_CR17","doi-asserted-by":"publisher","first-page":"910","DOI":"10.1126\/science.1065103","volume":"296","author":"S Maslov","year":"2002","unstructured":"Maslov S, Sneppen K: Specificity and Stability in Topology of Protein Networks. Science 2002, 296(5569):910\u2013913. 10.1126\/science.1065103","journal-title":"Science"},{"key":"3048_CR18","volume-title":"On the uniform generation of random graphs with prescribed degree sequences","author":"R Milo","year":"2004","unstructured":"Milo R, Kashtan N, Itzkovitz S, Newman ME, Alon U: On the uniform generation of random graphs with prescribed degree sequences.2004. [http:\/\/arxiv.org\/abs\/cond-mat\/0312028]"},{"key":"3048_CR19","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1126\/science.286.5439.509","volume":"286","author":"AL Barabasi","year":"1999","unstructured":"Barabasi AL, Albert R: Emergence of scaling in random networks. Science 1999, 286: 509\u2013512. 10.1126\/science.286.5439.509","journal-title":"Science"},{"issue":"6","key":"3048_CR20","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1145\/1273442.1250746","volume":"42","author":"N Nethercote","year":"2007","unstructured":"Nethercote N, Seward J: Valgrind: a framework for heavyweight dynamic binary instrumentation. SIGPLAN Not 2007, 42(6):89\u2013100. 10.1145\/1273442.1250746","journal-title":"SIGPLAN Not"},{"key":"3048_CR21","unstructured":"The Homo sapiens Database[http:\/\/csbi.ltdk.helsinki.fi\/pina\/interactome.stat.do]"},{"key":"3048_CR22","unstructured":"The Drosophila melanogaster Database[http:\/\/csbi.ltdk.helsinki.fi\/pina\/interactome.stat.do]"}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/1471-2105-10-318.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,8,31]],"date-time":"2021-08-31T21:37:56Z","timestamp":1630445876000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/1471-2105-10-318"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,10,4]]},"references-count":22,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2009,12]]}},"alternative-id":["3048"],"URL":"https:\/\/doi.org\/10.1186\/1471-2105-10-318","relation":{},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,10,4]]},"assertion":[{"value":"17 March 2009","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 October 2009","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 October 2009","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"318"}}