Study On Density-based Algorithm For Module Decomposition In PPI Networks

Since we entered the post-genomic era, the focus of bioinformatical study has been transformed from revealing genetic information to exploring genic function on the molecular level. With increasing amount of data becoming available by high-throughout methods, protein-protein interaction (PPI) network has been paid more attention which can explicitly reflect the function of genes. Accumulating evidence suggests that biological systems are composed of interacting, separable functional modules-groups of vertices within which connections are dense but between which they are sparse. Indentifying these modules is essential to understand the organization of biological systems. However, the most existing algorithms, for example, Molecular Complex Detection (MCODE), Clique Percolation Method (CPM), Markov Clustering (MCL) and so on, only find "dense" clusters. Actually, the modules are of different sizes, densities and arbitrary shapes. In this paper, we take into account the diversity of module topological structure and propose an hybrid algorithm based on the notion of density and spectral theory which could be applied to PPI networks. Firstly, Clustering objects can be mapped into eigenspace by graph laplacian matrix. Secondly, measuring similarity is to construct affinity matrix. Finally, objects can be clustered correctly by DBSCAN. Our method can not only obtain the complete information from partial information, but also detect the function modules of the arbitrary shape in PPI networks where there exists noise. We test our algorithm in yeast PPI networks. The result suggests that most of modules available have good biological significance in the function annotation and prediction, which outperforms other classical algorithms in two aspects-gene matches and p-value. Further, we also test our method in artificial networks and social networks, whose results demonstrate that our algorithm has good reliability and robustness.