Protein Complexes Are Identified In The PPI Network

A protein-protein interaction (PPI) network is a biomolecule relationship network that plays an important role in biological activities. Studies of functional modules in a PPI network contribute greatly to the understanding of the essence of life activities and mechanism of diseases. Studies show that proteins that tightly interact with each other correspond to functional module, so clustering analysis of PPI data has been widely studied for its effect to predict the function modules and protein complex. The main work are as follows:(1) Improving the performance of Newman fast algorithm to PPI networks. There are thousands of proteins and a number of interconnected large-scale complex networks in a PPI network. However, most of the functional module identification methods, which based on calculation method, have a high time cost. This makes their improve-ments and applications limited. Newman fast algorithm is a clustering algorithm based on cohesion hierarchical, which has two advantages of low time cost and easy operating. Therefore, the Newman fast algorithm is able to handle large-scale PPI data. The paper tries to change the cost function ?Q of cohesion hierarchical to improve the algorithm in the condition of retaining its advantages, and uses it to solve clustering problems in PPI networks. The paper proposes some different definitions of cost function ?Q and get a new cost function ?IQ by comparing the difference between them. The experi-ments show that the new cost function ?IQ gets better performance than the Newman fast algorithm did.(2) Preprocessing PPI networks according to the hierarchical model of network. Comparing with traditional clustering models, PPI network has two different character-istics:small world and scale free, for which traditional clustering methods do not per-form well in PPI network. The paper preprocess PPI networks based the hierarchical model of network proposed by Ravasz et al. The hierarchical model of network is simi-lar to traditional clustering model only when the edges that connect nodes with different grade are deleted. Therefore, the paper tries to cluster PPI network after deleting hier-archical edges. The experiments show that the results with preprocessing are better than the results without preprocessing.(3) Clustering PPI network by combining the firefly algorithm (FA) and the syn-chronization-based hierarchical clustering algorithm (SHC). The paper try to cluster PPI network in the use of the novel SHC algorithm. Firstly, the PPI data are preprocessed via spectral clustering which transforms the high-dimensional similarity matrix into a low dimension matrix. Then SHC algorithm is used to perform clustering. However, the SHC algorithm determines the optimal value of synchronous neighborhood radius by means of hierarchical search. The hierarchical search for the optimal value of synchro-nous neighborhood radius not only has low efficiency but also has other two shortcom-ings:first, the hierarchical search is very difficult to find the optimal value of synchro-nous neighborhood radius; second, the hierarchical incremental ?? needs to be adjust-ed according to the different object distributions. FA algorithm is a swarm intelligent optimization algorithm, which simulates the group behavior of fireflies. It has many advantages, such as fast search ability and easy operating. Therefore, the paper combine FA algorithm and SHC algorithm to cluster PPI network. Using the FA algorithm to find the optimal value of synchronous neighborhood radius will be more efficient and accurate than the basic hierarchical search do. The experiments show that the improved algorithm is excel to most of algorithms in precision, recall and f-measure.