ISSN 1000-1239 CN 11-1777/TP

Journal of Computer Research and Development ›› 2014, Vol. 51 ›› Issue (10): 2178-2186.doi: 10.7544/issn1000-1239.2014.20130538

Previous Articles     Next Articles

On Protein Complexes Identifying Algorithm Based on the Novel Modularity Function

Guo Maozu, Dai Qiguo, Xu Liqiu, Liu Xiaoyan   

  1. (School of Computer Science and Technology, Harbin Institute of Technology, Harbin 150001)
  • Online:2014-10-01

Abstract: Proteins often interact with each other to form complexes. It is very significant for understanding the activities in cell to carry out their biological functions. In recent years, with the rapid development of new biological experiment technologies, a large amount of protein-protein interaction (PPI) networks are generated. Identifying protein complexes by clustering proteins in PPI networks is hot spot in current bioinformatics research. Many clustering methods, which are mainly based on graph partition or the technologies of community detection in social network, have been proposed to recognize the protein complexes in PPI networks in last decade. However, the performances of most of previous developed detecting methods are not ideal. They cannot identify the overlapping complexes, but according to the biological study found, protein complexes are often overlapping. Therefore, in this paper, a protein complexes modularity function (Q function), namely PQ function, is proposed to identify the overlapping complexes from PPI networks. Based on PQ, a new algorithm for identifying protein complexes BMM (the algorithm based on protein complexes modularity function for merging modules). Firstly, BMM algorithm finds some dense sub-graphs as initial modules. Then, these initial modules are merged by maximizing the modularity function PQ. Finally, several high-quality protein complexes are found. Comparing these protein complexes with two known protein complexes datasets, the results suggest that the performance of BMM is excellent. In addition, compared with other latest algorithms, BMM is more accurate.

Key words: protein complex, protein-protein interaction (PPI), protein complexes modularity function, initial module, based on protein complexes modularity function for merging modules (BMM) algorithm

CLC Number: