{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,2]],"date-time":"2025-12-02T15:17:58Z","timestamp":1764688678180},"reference-count":35,"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":[[2008,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:sec><jats:title>Background<\/jats:title><jats:p>The recent explosion in biological and other real-world network data has created the need for improved tools for large network analyses. In addition to well established<jats:italic>global<\/jats:italic>network properties, several new mathematical techniques for analyzing<jats:italic>local<\/jats:italic>structural properties of large networks have been developed. Small over-represented subgraphs, called network<jats:italic>motifs<\/jats:italic>, have been introduced to identify simple building blocks of complex networks. Small induced subgraphs, called<jats:italic>graphlets<\/jats:italic>, have been used to develop \"network signatures\" that summarize network topologies. Based on these network signatures, two new highly sensitive measures of network local structural similarities were designed: the<jats:italic>relative graphlet frequency distance<\/jats:italic>(<jats:italic>RGF-distance<\/jats:italic>) and the<jats:italic>graphlet degree distribution agreement<\/jats:italic>(<jats:italic>GDD-agreement<\/jats:italic>).<\/jats:p><jats:p>Finding adequate null-models for biological networks is important in many research domains. Network properties are used to assess the fit of network models to the data. Various network models have been proposed. To date, there does not exist a software tool that measures the above mentioned local network properties. Moreover, none of the existing tools compare real-world networks against a series of network models with respect to these local as well as a multitude of global network properties.<\/jats:p><\/jats:sec><jats:sec><jats:title>Results<\/jats:title><jats:p>Thus, we introduce GraphCrunch, a software tool that finds well-fitting network models by comparing large real-world networks against random graph models according to various network structural similarity measures. It has unique capabilities of finding computationally expensive RGF-distance and GDD-agreement measures. In addition, it computes several standard global network measures and thus supports the largest variety of network measures thus far. Also, it is the first software tool that compares real-world networks against a series of network models and that has built-in parallel computing capabilities allowing for a user specified list of machines on which to perform compute intensive searches for local network properties. Furthermore, GraphCrunch is easily extendible to include additional network measures and models.<\/jats:p><\/jats:sec><jats:sec><jats:title>Conclusion<\/jats:title><jats:p>GraphCrunch is a software tool that implements the latest research on biological network models and properties: it compares real-world networks against a series of random graph models with respect to a multitude of local and global network properties. We present GraphCrunch as a comprehensive, parallelizable, and easily extendible software tool for analyzing and modeling large biological networks. The software is open-source and freely available at<jats:ext-link xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"http:\/\/www.ics.uci.edu\/~bio-nets\/graphcrunch\/\" ext-link-type=\"uri\">http:\/\/www.ics.uci.edu\/~bio-nets\/graphcrunch\/<\/jats:ext-link>. It runs under Linux, MacOS, and Windows Cygwin. In addition, it has an easy to use on-line web user interface that is available from the above web page.<\/jats:p><\/jats:sec>","DOI":"10.1186\/1471-2105-9-70","type":"journal-article","created":{"date-parts":[[2008,1,30]],"date-time":"2008-01-30T07:14:02Z","timestamp":1201677242000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":81,"title":["GraphCrunch: A tool for large network analyses"],"prefix":"10.1186","volume":"9","author":[{"given":"Tijana","family":"Milenkovi\u0107","sequence":"first","affiliation":[]},{"given":"Jason","family":"Lai","sequence":"additional","affiliation":[]},{"given":"Nata\u0161a","family":"Pr\u017eulj","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2008,1,30]]},"reference":[{"key":"2055_CR1","first-page":"151","volume-title":"Proc 3rd Ann ACM Symp on Theory of Computing: 1971","author":"S Cook","year":"1971","unstructured":"Cook S: The complexity of theorem-proving procedures. In Proc 3rd Ann ACM Symp on Theory of Computing: 1971. New York, Association for Computing Machinery; 1971:151\u2013158."},{"issue":"2","key":"2055_CR2","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1137\/S003614450342480","volume":"45","author":"MEJ Newman","year":"2003","unstructured":"Newman MEJ: The structure and function of complex networks. SIAM Review 2003, 45(2):167\u2013256.","journal-title":"SIAM Review"},{"key":"2055_CR3","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 SS, Itzkovitz S, Kashtan N, Chklovskii D, Alon U: Network motifs: simple building blocks of complex networks. Science 2002, 298: 824\u2013827.","journal-title":"Science"},{"key":"2055_CR4","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. Nature Genetics 2002, 31: 64\u201368.","journal-title":"Nature Genetics"},{"key":"2055_CR5","doi-asserted-by":"publisher","first-page":"1538","DOI":"10.1126\/science.1089167","volume":"303","author":"R Milo","year":"2004","unstructured":"Milo R, Itzkovitz S, Kashtan N, Levitt R, Shen-Orr S, Ayzenshtat I, Sheffer M, Alon U: Superfamilies of Evolved and Designed Networks. Science 2004, 303: 1538\u20131542.","journal-title":"Science"},{"issue":"18","key":"2055_CR6","doi-asserted-by":"publisher","first-page":"3508","DOI":"10.1093\/bioinformatics\/bth436","volume":"20","author":"N Pr\u017eulj","year":"2004","unstructured":"Pr\u017eulj N, Corneil DG, Jurisica I: Modeling Interactome: Scale-Free or Geometric? Bioinformatics 2004, 20(18):3508\u20133515.","journal-title":"Bioinformatics"},{"key":"2055_CR7","doi-asserted-by":"publisher","first-page":"e177","DOI":"10.1093\/bioinformatics\/btl301","volume":"23","author":"N Pr\u017eulj","year":"2006","unstructured":"Pr\u017eulj N: Biological Network Comparison Using Graphlet Degree Distribution. Bioinformatics 2006, 23: e177-e183.","journal-title":"Bioinformatics"},{"key":"2055_CR8","doi-asserted-by":"crossref","first-page":"290","DOI":"10.5486\/PMD.1959.6.3-4.12","volume":"6","author":"P Erd\u00f6s","year":"1959","unstructured":"Erd\u00f6s P, R\u00e9nyi A: On random graphs. Publicationes Mathematicae 1959, 6: 290\u2013297.","journal-title":"Publicationes Mathematicae"},{"key":"2055_CR9","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1002\/rsa.3240060204","volume":"6","author":"M Molloy","year":"1995","unstructured":"Molloy M, Reed B: A critical point of random graphs with a given degree sequence. Random Structures and Algorithms 1995, 6: 161\u2013180.","journal-title":"Random Structures and Algorithms"},{"issue":"5439","key":"2055_CR10","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\u2013512.","journal-title":"Science"},{"key":"2055_CR11","doi-asserted-by":"publisher","first-page":"440","DOI":"10.1038\/30918","volume":"393","author":"DJ Watts","year":"1998","unstructured":"Watts DJ, Strogatz SH: Collective dynamics of 'small-world' networks. Nature 1998, 393: 440\u2013442.","journal-title":"Nature"},{"key":"2055_CR12","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198506263.001.0001","volume-title":"Geometric Random Graphs","author":"M Penrose","year":"2003","unstructured":"Penrose M: Geometric Random Graphs. Oxford University Press; 2003."},{"issue":"10","key":"2055_CR13","doi-asserted-by":"publisher","first-page":"711","DOI":"10.1098\/rsif.2006.0147","volume":"3","author":"N Pr\u017eulj","year":"2006","unstructured":"Pr\u017eulj N, Higham D: Modelling protein-protein interaction networks via a stickiness index. Journal of the Royal Society Interface 2006, 3(10):711\u2013716.","journal-title":"Journal of the Royal Society Interface"},{"key":"2055_CR14","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: 1746\u20131758.","journal-title":"Bioinformatics"},{"key":"2055_CR15","doi-asserted-by":"publisher","first-page":"3572","DOI":"10.1093\/bioinformatics\/bti556","volume":"21","author":"F Schreiber","year":"2005","unstructured":"Schreiber F, Schwobbermeyer H: MAVisto: a tool for the exploration of network motifs. Bioinformatics 2005, 21: 3572\u20133574.","journal-title":"Bioinformatics"},{"key":"2055_CR16","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.","journal-title":"Bioinformatics"},{"key":"2055_CR17","volume-title":"Leda: A platform for combinatorial and geometric computing","author":"K Mehlhorn","year":"1999","unstructured":"Mehlhorn K, Naher S: Leda: A platform for combinatorial and geometric computing. Cambridge University Press; 1999."},{"key":"2055_CR18","doi-asserted-by":"publisher","first-page":"1107c","DOI":"10.1126\/science.1099334","volume":"305","author":"Y Artzy-Randrup","year":"2004","unstructured":"Artzy-Randrup Y, Fleishman SJ, Ben-Tal N, Stone L: Comment on \"Network Motifs: Simple Building Blocks of Complex Networks\" and \"Superfamilies of Evolved and Designed Networks\". Science 2004, 305: 1107c.","journal-title":"Science"},{"key":"2055_CR19","doi-asserted-by":"publisher","first-page":"1107d","DOI":"10.1126\/science.1100519","volume":"305","author":"R Milo","year":"2004","unstructured":"Milo R, Itzkovitz S, Kashtan N, Levitt R, Alon U: Response to Comment on \"Network Motifs: Simple Building Blocks of Complex Networks\" and \"Superfamilies of Evolved and Designed Networks\". Science 2004, 305: 1107d.","journal-title":"Science"},{"key":"2055_CR20","doi-asserted-by":"publisher","first-page":"98","DOI":"10.1038\/nbt921","volume":"22","author":"M Lappe","year":"2004","unstructured":"Lappe M, Holm L: Unraveling protein interaction networks with near-optimal efficiency. Nature Biotechnology 2004, 22: 98\u2013103.","journal-title":"Nature Biotechnology"},{"issue":"6887","key":"2055_CR21","doi-asserted-by":"publisher","first-page":"399","DOI":"10.1038\/nature750","volume":"417","author":"C von Mering","year":"2002","unstructured":"von Mering C, Krause R, Snel B, Cornell M, Oliver SG, Fields S, Bork P: Comparative assessment of large-scale data sets of protein-protein interactions. Nature 2002, 417(6887):399\u2013403.","journal-title":"Nature"},{"issue":"5651","key":"2055_CR22","doi-asserted-by":"publisher","first-page":"1727","DOI":"10.1126\/science.1090289","volume":"302","author":"L Giot","year":"2003","unstructured":"Giot L, Bader J, Brouwer C, Chaudhuri A, Kuang B, Li Y, Hao Y, Ooi C, Godwin B, Vitols E, Vijayadamodar G, Pochart P, Machineni H, Welsh M, Kong Y, Zerhusen B, Malcolm R, Varrone Z, Collis A, Minto M, Burgess S, McDaniel L, Stimpson E, Spriggs F, Williams J, Neurath K, Ioime N, Agee M, Voss E, Furtak K, Renzulli R, Aanensen N, Carrolla S, Bickelhaupt E, Lazovatsky Y, DaSilva A, Zhong J, Stanyon C, Finley RJ, White K, Braverman M, Jarvie T, Gold S, Leach M, Knight J, Shimkets R, McKenna M, Chant J, Rothberg J: A protein interaction map of Drosophila melanogaster. Science 2003, 302(5651):1727\u20131736.","journal-title":"Science"},{"key":"2055_CR23","doi-asserted-by":"publisher","first-page":"540","DOI":"10.1126\/science.1091403","volume":"303","author":"S Li","year":"2004","unstructured":"Li S, Armstrong C, Bertin N, Ge H, Milstein S, Boxem M, Vidalain PO, Han JD, Chesneau A, Hao T, Goldberg N, Li DS, Martinez M, Rual JF, Lamesch P, Xu L, Tewari M, Wong S, Zhang L, Berriz G, Jacotot L, Vaglio P, Reboul J, Hirozane-Kishikawa T, Li Q, Gabel H, Elewa A, Baumgartner B, Rose D, Yu H, Bosak S, Sequerra R, Fraser A, Mango S, Saxton W, Strome S, van den Heuvel S, Piano F, Vandenhaute J, Sardet C, Gerstein M, Doucette-Stamm L, Gunsalus K, Harper J, Cusick M, Roth F, Hill D, Vidal M: A Map of the Interactome Network of the Metazoan C. elegans. Science 2004, 303: 540\u2013543.","journal-title":"Science"},{"key":"2055_CR24","doi-asserted-by":"publisher","first-page":"957","DOI":"10.1016\/j.cell.2005.08.029","volume":"122","author":"U Stelzl","year":"2005","unstructured":"Stelzl U, Worm U, Lalowski M, Haenig C, Brembeck F, Goehler H, Stroedicke M, Zenkner M, Schoenherr A, Koeppen S, Timm J, Mintzlaff S, Abraham C, Bock N, Kietzmann S, Goedde A, Toksoz E, Droege A, Krobitsch S, Korn B, Birchmeier W, Lehrach H, Wanker E: A Human Protein-Protein Interaction Network: A Resource for Annotating the Proteome. Cell 2005, 122: 957\u2013968.","journal-title":"Cell"},{"key":"2055_CR25","doi-asserted-by":"publisher","first-page":"4221","DOI":"10.1073\/pnas.0501179102","volume":"102","author":"MPH Stumpf","year":"2005","unstructured":"Stumpf MPH, Wiuf C, May RM: Subnets of scale-free networks are not scale-free: Sampling properties of networks. Proceedings of the National Academy of Sciences 2005, 102: 4221\u20134224.","journal-title":"Proceedings of the National Academy of Sciences"},{"key":"2055_CR26","doi-asserted-by":"publisher","first-page":"839","DOI":"10.1038\/nbt1116","volume":"23","author":"JDH Han","year":"2005","unstructured":"Han JDH, Dupuy D, Bertin N, Cusick ME, M V: Effect of sampling on topology predictions of protein-protein interaction networks. Nature Biotechnology 2005, 23: 839\u2013844.","journal-title":"Nature Biotechnology"},{"key":"2055_CR27","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1093\/nar\/30.1.303","volume":"30","author":"I Xenarios","year":"2002","unstructured":"Xenarios I, Salwinski L, Duan J, Higney P, Kim S, Eisenberg D: DIP, the Database of Interacting Proteins: a research tool for studying cellular networks of protein interactions. Nucleic Acids Research 2002, 30: 303\u2013305.","journal-title":"Nucleic Acids Research"},{"key":"2055_CR28","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1074\/mcp.M100037-MCP200","volume":"1","author":"C Deane","year":"2002","unstructured":"Deane C, Salwinski L, Xenarios I, Eisenberg D: Protein interactions: two methods for assessment of the reliability of high throughput observations. Molecular and Cellular Proteomics 2002, 1: 349\u2013356.","journal-title":"Molecular and Cellular Proteomics"},{"key":"2055_CR29","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1093\/nar\/30.1.31","volume":"30","author":"HW Mewes","year":"2002","unstructured":"Mewes HW, Frishman D, Guldener U, Mannhaupt G, Mayer K, Mokrejs M, Morgenstern B, Munsterkotter M, Rudd S, Weil B: MIPS: a database for genomes and protein sequences. Nucleic Acids Research 2002, 30: 31\u201334.","journal-title":"Nucleic Acids Research"},{"issue":"8","key":"2055_CR30","doi-asserted-by":"publisher","first-page":"974","DOI":"10.1093\/bioinformatics\/btl030","volume":"22","author":"N Pr\u017eulj","year":"2006","unstructured":"Pr\u017eulj N, Corneil DG, Jurisica I: Efficient Estimation of Graphlet Frequency Distributions in Protein-Protein Interaction Networks. Bioinformatics 2006, 22(8):974\u2013980.","journal-title":"Bioinformatics"},{"key":"2055_CR31","doi-asserted-by":"publisher","first-page":"1621","DOI":"10.1126\/science.1105776","volume":"307","author":"M Barrios-Rodiles","year":"2005","unstructured":"Barrios-Rodiles M, Brown KR, Ozdamar B, Liu Z, Donovan RS, Shinjo F, Liu Y, Bose R, Dembowy J, Taylor IW, Luga V, Przulj N, Robinson M, Suzuki H, Hayashizaki Y, Jurisica I, Wrana JL: High-Throughput Mapping of a Dynamic Signaling Network in Mammalian Cells. Science 2005, 307: 1621\u20131625.","journal-title":"Science"},{"key":"2055_CR32","unstructured":"Hormozdiari F, Berenbrink P, Pr\u017eulj N, Sahinalp C: Not All Scale Free Networks are Born Equal: the Role of the Seed Graph in PPI Netwok Emulation. PLoS Computational Biology, in press."},{"key":"2055_CR33","doi-asserted-by":"publisher","first-page":"328","DOI":"10.1093\/nar\/gkh164","volume":"32","author":"H Yu","year":"2004","unstructured":"Yu H, Zhu X, Greenbaum D, Karro J, Gerstein M: TopNet: a tool for comparing biological subnetworks, correlating protein properties with topological statistics. Nucleic Acids Research 2004, 32: 328\u2013337.","journal-title":"Nucleic Acids Research"},{"key":"2055_CR34","doi-asserted-by":"publisher","first-page":"2968","DOI":"10.1093\/bioinformatics\/btl488","volume":"22","author":"K Yip","year":"2006","unstructured":"Yip K, Yu H, Kim P, Schultz M, Gerstein M: The tYNA platform for comparative interactomics: a web tool for managing, comparing and mining multiple networks. Bioinformatics 2006, 22: 2968\u20132970.","journal-title":"Bioinformatics"},{"key":"2055_CR35","first-page":"242","volume-title":"Timeshift -The World in Twenty-Five Years: Ars Electronica","author":"V Batagelj","year":"2004","unstructured":"Batagelj V, Mrvar A: Pajek \u2013 Program for Analysis and Visualization of Large Networks. Timeshift -The World in Twenty-Five Years: Ars Electronica 2004, 242\u2013251."}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/1471-2105-9-70.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,16]],"date-time":"2023-05-16T04:50:54Z","timestamp":1684212654000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/1471-2105-9-70"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,1,30]]},"references-count":35,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2008,12]]}},"alternative-id":["2055"],"URL":"https:\/\/doi.org\/10.1186\/1471-2105-9-70","relation":{},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,1,30]]},"assertion":[{"value":"3 June 2007","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 January 2008","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 January 2008","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"70"}}