Proteome-scale physical interaction data have become available for a large number of organisms, including human and most model organisms. Global analyses of the resulting protein interaction networks provide new opportunities for uncovering cellular organization and revealing protein functions and pathways. Beyond the basic characterization of these interaction networks with respect to their topological features (e.g. Barabási and Oltvai, 2004
), arguably the most widespread approach for analyzing biological networks is to cluster or partition them into subcomponents. Clustering of biological networks has revealed a modular organization (Hartwell et al.
), with highly connected groups of proteins taking part in the same biological process (BP) or protein complex (Bader and Hogue, 2003
; Pereira-Leal et al.
; Rives and Galitski, 2003
; Spirin and Mirny, 2003
). Indeed, dozens of papers for analyzing protein interaction networks have focused on finding clusters within them and novel network clustering methods continue to be developed (e.g. Adamcsek et al.
; Altaf-Ul-Amin et al.
; Arnau et al.
; Asthana et al.
; Brun et al.
; Chen and Yuan, 2006
; Dunn et al.
; Enright et al.
; King et al.
; Luo et al.
; Navlakha et al.
; Newman, 2006
; Poyatos and Hurst, 2004
; Radicchi et al.
; Samanta and Liang, 2003
; Schlitt et al.
; von Mering et al.
; Wang et al.
Most frequently, computationally derived clusters within physical interaction networks are used to uncover protein complexes and functional modules, as well as to predict protein function. Typically, a cluster is associated with a known complex or function by determining whether the number of proteins known to be part of the complex or annotated with the function is enriched, as judged by the hypergeometric distribution. Within a cluster, enriched functions, perhaps also required to annotate a suitable fraction of member proteins, can then be transferred to other member proteins. While these types of analysis are commonplace in interactomics, how effective are they for the tasks at hand?
Here, we focus on the task of utilizing network-derived clusters to uncover functional modules and predict protein functions. Evaluating how well clusters correspond to functional modules is a challenging task. Central to this is that while functional modules are commonly defined as groups of proteins that work together to accomplish a BP, there is no widely accepted formal definition of a module; many have been proposed, though typically based on topological features of the network (e.g. Radicchi et al.
). We utilize an external measure—the Gene Ontology (GO; Ashburner et al.
)—to derive functional modules. That is, for a GO BP or cellular component (CC) functional term, the corresponding module contains all the proteins that are annotated with that term. Since GO relates functions in a hierarchical fashion, the next challenge for evaluating clusters is to deal with this hierarchy. At first glance, it may appear that functions can be chosen at a particular resolution in the hierarchy. For example, it is possible to utilize the high-level GO ‘slim’ functional terms, and then clusters can be evaluated in how well they recapitulate these terms, using sensitivity and positive predictive value measures, as introduced in an influential quantitative assessment of how well clustering approaches can uncover known protein complexes (Brohée and van Helden, 2006
). However, for evaluating functional modules, this approach has the weakness that a clustering that finds many small tightly connected clusters corresponding to very specific BPs would be unfairly penalized.
Our main technical contribution is a series of measures that can be used to compare and evaluate network clustering algorithms with respect to how well they perform in uncovering known, potentially overlapping functional modules. We demonstrate the quality of our measures by using them on random networks, and on clusters derived from the annotations themselves (i.e. these two extremes represent the noisy versus ideal scenarios). With this evaluation framework in hand, in order to make general conclusions about the efficacy of network clustering-based approaches, we experiment with six available clustering algorithms on four different high-throughput derived Saccharomyces cerevisiae physical interaction networks. We find that clustering algorithms exhibit a wide range of performances in recapitulating functional modules, derived from either BP or CC GO terms, even when run on the same network, and that the relative performance of clustering algorithms varies depending on the network at hand. In particular, we find that topological features of the network should guide algorithm choice. Given the vast differences we find in how well clustering algorithms recapitulate functional modules, this is an important practical consideration. As a byproduct of our analysis, we can also make conclusions about individual clustering algorithms: overall, though there are some clustering approaches which clearly outperform others, there is no single network clustering approach that dominates the rest in all cases.
Since module finding in biological networks is often motivated by the task of function prediction, we also perform a comprehensive evaluation in this scenario. Surprisingly, we find that for S.cerevisiae, the common practice of annotating a protein with the overrepresented BP or CC terms in its cluster is less accurate than simple guilt-by-association approaches based on considering just the annotations of direct interaction partners. This is true regardless of which underlying clustering approach is used. Additionally, as annotations are removed from the network, the relative performance of clustering-based function prediction improves in comparison to the simple scheme that just considers the annotations of interacting proteins. This suggests that clustering-based methods are most useful in networks obtained for genomes with fewer protein annotations.
In addition to characterizing the utility of network-derived clusters in uncovering functional modules and predicting protein functions, a major contribution of our work is a framework that can be used in the future for evaluating how well a new clustering approach performs for these tasks. Importantly, our testing suggests that while clustering of networks is often motivated by the goal of predicting protein function, if new clustering approaches are evaluated with respect to function prediction, it is important to demonstrate how much, or in which circumstances, improvement is obtained over guilt-by-association approaches. Overall, we hope that our testing framework as well as our findings about the utility of interactome-based clustering will inform future methodological advances in clustering biological networks.