{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,23]],"date-time":"2026-01-23T11:39:18Z","timestamp":1769168358651,"version":"3.49.0"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"S9","content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Bioinformatics"],"published-print":{"date-parts":[[2008,8]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:sec><jats:title>Background<\/jats:title><jats:p>Biological systems can be modeled as complex network systems with many interactions between the components. These interactions give rise to the function and behavior of that system. For example, the protein-protein interaction network is the physical basis of multiple cellular functions. One goal of emerging systems biology is to analyze very large complex biological networks such as protein-protein interaction networks, metabolic networks, and regulatory networks to identify functional modules and assign functions to certain components of the system. Network modules do not occur by chance, so identification of modules is likely to capture the biologically meaningful interactions in large-scale PPI data. Unfortunately, existing computer-based clustering methods developed to find those modules are either not so accurate or too slow.<\/jats:p><\/jats:sec><jats:sec><jats:title>Results<\/jats:title><jats:p>We devised a new methodology called SCAN (Structural Clustering Algorithm for Networks) that can efficiently find clusters or functional modules in complex biological networks as well as hubs and outliers. More specifically, we demonstrated that we can find functional modules in complex networks and classify nodes into various roles based on their structures. In this study, we showed the effectiveness of our methodology using the budding yeast (Saccharomyces cerevisiae) protein-protein interaction network. To validate our clustering results, we compared our clusters with the known functions of each protein. Our predicted functional modules achieved very high purity comparing with state-of-the-art approaches. Additionally the theoretical and empirical analysis demonstrated a linear running-time of the algorithm, which is the fastest approach for networks.<\/jats:p><\/jats:sec><jats:sec><jats:title>Conclusion<\/jats:title><jats:p>We compare our algorithm with well-known modularity based clustering algorithm CNM. We successfully detect functional groups that are annotated with putative GO terms. Top-10 clusters with minimum p-value theoretically prove that newly proposed algorithm partitions network more accurately then CNM. Furthermore, manual interpretations of functional groups found by SCAN show superior performance over CNM.<\/jats:p><\/jats:sec>","DOI":"10.1186\/1471-2105-9-s9-s19","type":"journal-article","created":{"date-parts":[[2008,8,12]],"date-time":"2008-08-12T18:13:05Z","timestamp":1218564785000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":67,"title":["A structural approach for finding functional modules from large biological networks"],"prefix":"10.1186","volume":"9","author":[{"given":"Mutlu","family":"Mete","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fusheng","family":"Tang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiaowei","family":"Xu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nurcan","family":"Yuruk","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2008,8,12]]},"reference":[{"key":"2678_CR1","doi-asserted-by":"publisher","first-page":"623","DOI":"10.1038\/35001009","volume":"403","author":"P Uetz","year":"2000","unstructured":"Uetz P, Giot L, Cagney G, Mansfield TA, Judson RS, Knight JR, Lockshon D, Narayan V, Srinivasan M, Pochart P: Nature. 2000, 403: 623-627.","journal-title":"Nature"},{"key":"2678_CR2","doi-asserted-by":"publisher","first-page":"4569","DOI":"10.1073\/pnas.061034498","volume":"98","author":"T Ito","year":"2001","unstructured":"Ito T, Chiba T, Ozawa R, Yoshida M, Hattori M, Sakaki Y: Proc Natl Acad Sci USA. 2001, 98: 4569-4574.","journal-title":"Proc Natl Acad Sci USA"},{"key":"2678_CR3","doi-asserted-by":"publisher","first-page":"1727","DOI":"10.1126\/science.1090289","volume":"302","author":"L Giot","year":"2003","unstructured":"Giot L, Bader JS, Brouwer C, Chaudhuri A, Kuang B, Li Y, Hao YL, Ooi CE, Godwin B, Vitols E: Science. 2003, 302: 1727-1736.","journal-title":"Science"},{"key":"2678_CR4","doi-asserted-by":"publisher","first-page":"540","DOI":"10.1126\/science.1091403","volume":"303","author":"S Li","year":"2004","unstructured":"Li S, Armstrong CM, Bertin N, Ge H, Milstein S, Boxem M, Vidalain PO, Han JD, Chesneau A, Hao T: Science. 2004, 303: 540-543.","journal-title":"Science"},{"key":"2678_CR5","doi-asserted-by":"crossref","unstructured":"Steven H, Strogatz : \"Exploring complex networks\". Nature. 410: 268-276. (8 March 2001)","DOI":"10.1038\/35065725"},{"key":"2678_CR6","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1038\/nrg1272","volume":"5","author":"Barab\u00e1si Albert-L\u00e1szl\u00f3","year":"2004","unstructured":"Albert-L\u00e1szl\u00f3 Barab\u00e1si, Zolt\u00e1n N, Oltvai : Network Biology: Understanding The Cell's Functional Organization. Nature Reviews Genetics. 2004, 5: 101-113.","journal-title":"Nature Reviews Genetics"},{"key":"2678_CR7","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 A-L: The large-scale organization of metabolic networks. Nature. 2000, 407: 651-654.","journal-title":"Nature"},{"key":"2678_CR8","doi-asserted-by":"publisher","first-page":"1803","DOI":"10.1098\/rspb.2001.1711","volume":"268","author":"A Wagner","year":"2001","unstructured":"Wagner A, Fell DA: The small world inside large metabolic networks. Proc R Soc Lond B. 2001, 268: 1803-1810.","journal-title":"Proc R Soc Lond B"},{"key":"2678_CR9","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-442.","journal-title":"Nature"},{"key":"2678_CR10","doi-asserted-by":"publisher","first-page":"895","DOI":"10.1038\/nature03288","volume":"433","author":"R Guimera","year":"2005","unstructured":"Guimera R, Amaral LAN: \"Functional cartography of complex metabolic networks\". Nature. 2005, 433: 895-900.","journal-title":"Nature"},{"key":"2678_CR11","doi-asserted-by":"publisher","first-page":"026113","DOI":"10.1103\/PhysRevE.69.026113","volume":"69","author":"MEJ Newman","year":"2004","unstructured":"Newman MEJ, Girvan M: \"Finding and evaluating community structure in networks\". Phys Rev E. 2004, 69: 026113-","journal-title":"Phys Rev E"},{"key":"2678_CR12","doi-asserted-by":"publisher","first-page":"066111","DOI":"10.1103\/PhysRevE.70.066111","volume":"70","author":"A Clauset","year":"2004","unstructured":"Clauset A, Newman M, Moore C: Finding community structure in very large networks. Phys Rev E. 2004, 70: 066111-","journal-title":"Phys Rev E"},{"key":"2678_CR13","volume-title":"Proc of ICDM","author":"C Ding","year":"2001","unstructured":"Ding C, He X, Zha H, Gu M, Simon H: \"A min-max cut algorithm for graph partitioning and data clustering\". Proc of ICDM. 2001"},{"key":"2678_CR14","doi-asserted-by":"crossref","unstructured":"Shi J, Malik J: \"Normalized cuts and image segmentation\", IEEE Trans. On Pattern Analysis and Machine Intelligence. 2001, 22 (8):","DOI":"10.1109\/34.868688"},{"key":"2678_CR15","doi-asserted-by":"publisher","first-page":"824","DOI":"10.1145\/1281192.1281280","volume-title":"Proceedings of the 13th ACM SIGKDD international Conference on Knowledge Discovery and Data Mining (San Jose, California, USA, August 12 \u2013 15, 2007). KDD '07","author":"X Xu","year":"2007","unstructured":"Xu X, Yuruk N, Feng Z, Schweiger TA: SCAN: a structural clustering algorithm for networks. Proceedings of the 13th ACM SIGKDD international Conference on Knowledge Discovery and Data Mining (San Jose, California, USA, August 12 \u2013 15, 2007). KDD '07. 2007, ACM, New York, NY, 824-833. DOI= http:\/\/doi.acm.org\/10.1145\/1281192.1281280"},{"key":"2678_CR16","doi-asserted-by":"publisher","first-page":"928","DOI":"10.1002\/pmic.200300636","volume":"4","author":"SY Yook","year":"2004","unstructured":"Yook SY, Oltvai ZN, Barab\u00e1si A-L: Functional and topological characterization of protein interaction networks. Proteomics. 2004, 4: 928-942. Dgd","journal-title":"Proteomics"},{"issue":"3","key":"2678_CR17","doi-asserted-by":"publisher","first-page":"364","DOI":"10.1093\/bioinformatics\/bti021","volume":"21","author":"V Arnau","year":"2005","unstructured":"Arnau V, Mars S, Marin I: Iterative cluster analysis of protein interaction data. Bioinformatics. 2005, 21 (3): 364-378.","journal-title":"Bioinformatics"},{"key":"2678_CR18","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1038\/ng906","volume":"31","author":"LF Wu","year":"2002","unstructured":"Wu LF, Hughes TR, Davierwala AP, Robinson MD, Stoughton R, Altschuler SJ: Large-scale prediction of saccharomyces cerevisiae gene function using overlapping transcriptional clusters. Nature Genetics. 2002, 31: 255-265.","journal-title":"Nature Genetics"},{"key":"2678_CR19","unstructured":"[http:\/\/www.yeastgenome.org\/]"},{"issue":"17","key":"2678_CR20","doi-asserted-by":"publisher","first-page":"3013","DOI":"10.1093\/bioinformatics\/bth351","volume":"20","author":"AD King","year":"2004","unstructured":"King AD, Przulj N, Jurisica I: Protein complex prediction via cost based clustering. Bioinformatics. 2004, 20 (17): 3013-3020.","journal-title":"Bioinformatics"},{"issue":"3","key":"2678_CR21","doi-asserted-by":"publisher","first-page":"340","DOI":"10.1093\/bioinformatics\/btg415","volume":"20","author":"N Przulj","year":"2004","unstructured":"Przulj N, Wigle D, Jurisica I: Functional topology in a network of protein interactions. Bioinformatics. 2004, 20 (3): 340-348.","journal-title":"Bioinformatics"},{"key":"2678_CR22","volume-title":"PKDD","author":"D Ucar","year":"2006","unstructured":"Ucar D, Asur S, Catalyurek U, Parthasarathy S: Improving functional modularity in protein-protein interactions graphs using hub-induced subgraphs. PKDD. 2006"},{"key":"2678_CR23","first-page":"291","volume-title":"Proc. 2nd Int. Conf. on Knowledge Discovery and Data Mining (KDD'96), Portland, OR","author":"M Ester","year":"1996","unstructured":"Ester M, Kriegel H-P, Sander J, Xu X: \"A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise\". Proc. 2nd Int. Conf. on Knowledge Discovery and Data Mining (KDD'96), Portland, OR. 1996, AAAI Press, 291-316."},{"key":"2678_CR24","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-442.","journal-title":"Nature"},{"key":"2678_CR25","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: Publ Math (Debrecen). 1959, 6: 290-","journal-title":"Publ Math (Debrecen)"},{"key":"2678_CR26","volume-title":"SIGCOMM","author":"M Faloutsos","year":"1999","unstructured":"Faloutsos M, Faloutsos P, Faloutsos C: On Power-Law Relationships of the Internet Topology. SIGCOMM. 1999"}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/1471-2105-9-S9-S19.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,29]],"date-time":"2024-02-29T06:37:32Z","timestamp":1709188652000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/1471-2105-9-S9-S19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,8]]},"references-count":26,"journal-issue":{"issue":"S9","published-print":{"date-parts":[[2008,8]]}},"alternative-id":["2678"],"URL":"https:\/\/doi.org\/10.1186\/1471-2105-9-s9-s19","relation":{},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,8]]},"assertion":[{"value":"12 August 2008","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"S19"}}