A structural approach for finding functional modules from large biological networks.
BACKGROUND
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.


RESULTS
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.


CONCLUSIONS
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.
Mete
Mutlu
M
Department of Applied Science, University of Arkansas at Little Rock, Little Rock, Arkansas, USA. mxmete@ualr.edu
Tang
Fusheng
F
Xu
Xiaowei
X
Yuruk
Nurcan
N
D000465:Algorithms; D016000:Cluster Analysis; D003198:Computer Simulation; D008954:Models, Biological; D005810:Multigene Family / Q000502:physiology*; D020543:Proteome / Q000378:metabolism*; D015398:Signal Transduction / Q000502:physiology*
D020543:Proteome
Bioinformatics. 2004 Feb 12;20(3):340-8
14960460
Science. 2004 Jan 23;303(5657):540-3
14704431
Nature. 1998 Jun 4;393(6684):440-2
9623998
Nature. 2005 Feb 24;433(7028):895-900
15729348
Phys Rev E Stat Nonlin Soft Matter Phys. 2004 Dec;70(6 Pt 2):066111
15697438
Nature. 2000 Feb 10;403(6770):623-7
10688190
Phys Rev E Stat Nonlin Soft Matter Phys. 2004 Feb;69(2 Pt 2):026113
14995526
Proteomics. 2004 Apr;4(4):928-42
15048975
Nat Genet. 2002 Jul;31(3):255-65
12089522
Nature. 2000 Oct 5;407(6804):651-4
11034217
Science. 2003 Dec 5;302(5651):1727-36
14605208
Bioinformatics. 2004 Nov 22;20(17):3013-20
15180928
Proc Natl Acad Sci U S A. 2001 Apr 10;98(8):4569-74
11283351
Nature. 2001 Mar 8;410(6825):268-76
11258382
Bioinformatics. 2005 Feb 1;21(3):364-78
15374873
Proc Biol Sci. 2001 Sep 7;268(1478):1803-10
11522199
Nat Rev Genet. 2004 Feb;5(2):101-13
14735121