关键词: 蛋白质互作用网络, 遗传算法, 图聚类, 蛋白质复合物

Abstract: The protein interaction network is a typical complex network that presents a distinct community structure. The communities in the network correspond to functional modules and are often considered as protein complexes.    Protein complex recognition plays an important role in predicting protein function and explaining specific biological processes. The clustering method based on seed node expansion is widely used in protein complex recognition. Aiming at the problems that the final result of this algorithm is influenced by seed nodes, and the search space is limited in the process of cluster formation, this paper presents a protein complex recognition algorithm GAGC (genetic algorithm based graph clustering), where the individual represents the clustering result (there may be overlapping nodes between categories), and the F-measure value is used as the objective function of population evolution. The algorithm uses the IPCA (improvement development clustering algorithm) to generate the initial population; for the initial population, chromosome alignment is designed to cross the operation to produce the next generation population. Comparing with the classical algorithms such as DPClus, MCODE, IPCA, ClusterOne, HC-PIN and CFinder, GAGC algorithm can expand the search space of graph clustering algorithm, improve the diversity of solution, and then improve the performance of protein complex detection.

Key words: protein-protein interaction (PPI) network, genetic algorithm, graph clustering, protein complex