Signal transduction model based functional module detection algorithm for protein-protein interaction network

Cellular functions are coordinately carried out by groups of genes and proteins forming functional modules. Detection of such functional modules from protein-protein interaction (PPI) networks is one of the most challenging and important problem in post genomic era. Moreover, the sparse connectivity of protein-protein interaction data sets makes identification of functional modules more challenging. After careful observations of the properties of functional modules in the PPI network, we have found that the actual topological shapes and properties, including the graph density and diameter, of the functional modules in the PPI network have exposed unexpected phenomena, e.g., low intraconnectivity and longish shapes. Many different clustering approaches have been proposed to extract functional modules from PPI networks. Most of them concentrated only on densely connected regions topologically and ignored biological characteristics of the network to be dealt with, even though they were working on biological networks. Therefore, they could find only the clusters with certain density, and failed to find effective functional modules which are biologically significant. Furthermore, they produced many small size clusters, which have less than 5 members or even singletons, and it resulted in discarding huge number of proteins during the clustering process. To conquer these problems effectively, we develop an algorithm, termed STM, which utilizes the degree of influence between proteins to determine the cluster representatives. Clusters can then be formulated by an iterative merging process. STM is compared to six competing approaches including the maximum clique, quasi-clique, minimum cut, betweeness cut and Markov Clustering(MCL) algorithms. The clusters obtained by each technique are compared for enrichment of biological function. Identified clusters by STM are shown to be enriched for biological function better than the clusters identified by other existing approaches. Topological evaluation of the identified clusters by our method demonstrated that our method can successfully identify arbitrary shape clusters with large size that the other methods cannot. In addition to the above, an important strength of our approach is that the percentage of proteins that are discarded to create clusters is much lower than the other approaches which have an average discard percentage of 59% on the yeast protein-protein interaction network. module detection.