arge-scale experiments and integration of published data (1) have provided maps of several biological networks such as metabolic networks (2, 3), protein-protein (4, 5) and protein-DNA interactions (6, 7), etc. Although incomplete and, perhaps, inaccurate (8-11), these maps became a focal point of a search for the general principles that govern the organization of molecular networks (12-16). Important statistical characteristics of such networks include power-law distribution (P(k) ϳ k Ϫ␥ ) (e.g., refs. 16 and 17) or a similar distribution of the node degree k (i.e., the number of edges of a node); the small-world property (11, 13, 16) (i.e., a high clustering coefficient and a small shortest path between every pair of nodes); anticorrelation in the node degree of connected nodes (15) (i.e., highly interacting nodes tend to be connected to low-interacting ones); and other properties. These properties become evident when hundreds or thousands of molecules and their interactions are studied together. Recently discovered motifs (7, 18) that consist of three to four nodes constitute the other end of the spectrum. Large-scale characteristics are usually attributed to massive evolutionary processes that shape the network (6, 14), whereas many small-scale motifs represent feedback and feed-forward loops in cellular regulation (18, 19) . However, most important biological processes such as signal transduction, cell-fate regulation, transcription, and translation involve more than four but much fewer than hundreds of proteins. Most relevant processes in biological networks correspond to the mesoscale (5-25 genes͞proteins). Meso-scale properties of biological networks have been mostly elusive because of computational difficulties in enumerating midsize subnetworks (e.g., a network of 1,000 nodes contains 1 ϫ 10 23 possible 10-node sets). Here, we present an in-depth exploration of molecular networks on the meso-scale level. We focused on multibody interactions and searched for sets of proteins having many more interactions among themselves than with the rest of the network (clusters). We have developed several algorithms to find such clusters in an arbitrary network. We analyzed a yeast network of protein-protein interactions (20) and found Ͼ50 known and previously uncharacterized protein clusters. We analyzed functional annotation of these clusters and found that most of identified clusters correspond to either of the two types of cellular modules: protein complexes or functional modules (see Discussion). Protein complexes are groups of proteins that interact with each other at the same time and place, forming a single multimolecular machine. Examples of identified protein complexes include several large transcription factor complexes, the anaphase-promoting complex, RNA splicing and polyadenylation machinery, protein export and transport complexes, etc. Functional modules, in contrast, consist of proteins that participate in a particular cellular process while binding each other at a different time and place (different conditions or phases of the cell cycle, in different cellular compartments, etc). Examples of identified functional modules include the CDK͞cyclin module responsible for cell-cycle progression, the yeast pheromone response pathway, MAP signaling cascades, etc. The discovered complexes and modules have high statistical significance and consistent functional annotation (when available), and match very well to experimentally obtained protein complexes (21, 22) . Importantly, by relying on multibody interactions, our method is robust to false-positive interactions present in the network. The network of protein interactions (20) was represented as an undirected graph with proteins as nodes and protein interactions as undirected edges. The key idea of our analysis was to identify highly connected subgraphs (clusters) that have more interactions within themselves and fewer with the rest of the graph. A fully connected subgraph, or clique, that is not a part of any other clique is an example of such a cluster. In general, we did not require clusters to be fully connected; instead, the density of connections in the cluster was measured by the parameter Q ϭ 2m͞(n(n Ϫ 1)), where n is the number of proteins in the cluster and m is the number of interactions between them. We developed algorithms that can identify clusters of sufficiently high Q in an arbitrary graph. Note that, despite some similarity, the problem of dense subgraphs is not identical to the problem of clustering objects in a metric space and cannot be solved by traditional clustering techniques. Identification of Highly Connected Sets. Our first approach was to identify all fully connected subgraphs (cliques) by complete enumeration. Because the graph is very sparse, this could be This paper was submitted directly (Track II) to the PNAS office.
In the maximal clique approach, clustering is reduced to identifying fully connected subgraphs in the graph REF .
Protein complexes and functional modules in molecular networks
Proceedings of the National Academy of Sciences of the United States of America
Proceedings of the National Academy of Sciences of the United States of America
Biology Medicine