Protein Complex Prediction with RNSC

Graph theory analysis of biological networks, such as protein–protein interactions (PPIs), gene regulatory, metabolic, etc., has identified a strong relationship between topology of these networks and the underlying cellular function and biological processes (Sharan et al. Mol Syst Biol 3:88, 2007). We focus on PPI networks, in which nodes correspond to proteins and edges represent interactions among the proteins. The size of these networks is ever growing, and thus efficient identification of various network motifs and dense sub-networks has become necessary. Predicting highly connected sub-graphs in a PPI network is important to biologists as it may help to identify biologically meaningful protein complexes, and with further integrative analysis may lead to identifying dynamic assembly of individual subunits in these complexes. In this chapter, we describe one method for predicting protein complexes in two steps. The first step is to partition the nodes of a PPI network (i.e. proteins) into highly connected groups or clusters using the Restricted Neighbourhood Search Clustering algorithm. This provides a set of clusters that represent candidate complexes. The second step of the method is to filter the candidate complexes based on three criteria: minimum cluster size, minimum interaction density, and minimum functional homogeneity , which reflects the extent to which the proteins of the candidate cluster operate in the same functional group. Candidate complexes passing all three criteria are then put forward as predicted protein complexes. The effectiveness of this method is investigated in the previous studies (King et al. Bioinformatics 20:3013–3020, 2004; Brohee and van Helden BMC Bioinformatics 7:488, 2006; and Moschopoulos et al. BMC Bioinformatics 10(Suppl 6):S11, 2009).