NeMo: Network Module identification in Cytoscape

Abstract

Background: As the size of the known human interactome grows, biologists increasingly rely on computational tools to identify patterns that represent protein complexes and pathways. Previous studies have shown that densely connected network components frequently correspond to community structure and functionally related modules. In this work, we present a novel method to identify densely connected and bipartite network modules based on a log odds score for shared neighbours.

Results: To evaluate the performance of our method (NeMo), we compare it to other widely used tools for community detection including kMetis, MCODE, and spectral clustering. We test these methods on a collection of synthetically constructed networks and the set of MIPS human complexes. We apply our method to the CXC chemokine pathway and find a high scoring functional module of 12 disconnected phospholipase isoforms.

Conclusion: We present a novel method that combines a unique neighbour-sharing score with hierarchical agglomerative clustering to identify diverse network communities. The approach is unique in that we identify both dense network and dense bipartite network structures in a single approach. Our results suggest that the performance of NeMo is better than or competitive with leading approaches on both real and synthetic datasets. We minimize model complexity and generalization error in the Bayesian spirit by integrating out nuisance parameters. An implementation of our method is freely available for download as a plugin to Cytoscape through our website and through Cytoscape itself.

Figure 1

Community-finding algorithm performance on synthetic networks. Comparison of NeMo with single-linkage, complete-linkage, MCODE, kMetis, and spectral clustering measured in terms of the reconstruction fidelity of synthetic modules. The x-axis indicates reconstruction error between 0 and 1 with 0 indicating complete module reconstruction and 1 indicating that the algorithm did not identify the module. The figure shows the fraction of modules identified with a reconstruction error less than a given threshold.

Figure 2

Interactome-scale community-finding algorithm comparison. (a) ROC comparing NeMo with single-link, NeMo with complete-linkage, MCODE, kMetis, and spectral clustering for the identification of MIPS human complexes. (b) Precision and recall curves comparing NeMo with single-link, NeMo with complete-linkage, MCODE, kMetis, and spectral clustering for the identification of MIPS human complexes. Each algorithm produced a set of putative network modules embedded in the interactome. The putative network module set of each algorithm was used to rank a set of 380 MIPS complexes and 380 randomized networks by reconstruction fidelity (Jaccard coefficient).

Figure 3

A functional module of the CXC chemokine pathway uniquely identified by NeMo. A collection of 12 proteins from the glycine, serine and threonine metabolic pathway. The family of proteins can be identified visually, but is often missed by automatic network module identification algorithms because they form an independent set in the CXC chemokine pathway.