Research On Group Intelligence Optimization Algorithm And Its Application And Evaluation In PPI Network

With the completion of human genome project and development of biological information technology and the rapid growth of huge amounts of biological data, the research topic of protein-protein international networks arises at the historic moment.It is well known that protein is the material basis of life, is the important component of the cell. But the protein is not isolated, it performs various functions through closely connection with each other. The research of clustering based on protein-protein interaction networks can predict proteins unknown protein at the molecular level, to further reveal the law of activities such as the growth, metabolism of cells and the nature of many problems in the process of life. In addition, the clustering based on protein-protein interaction networks is helpful to the diagnosis of the disease and pathological study, at the same time to promote the research and development of a variety of subjects such as biology, medical and bioinformatics.While tradition clustering methods are mature, they have advantages and disadvantages. For example the clustering based on partitioning is simple and efficient, easy to implement, but it requires determining the number of clusters beforehand. Because the number of cluster modules is actually is unknown, so the number directly affect the cluster results. The clustering based on hierarchy can mine module of any shape, and can make the whole network present a clear hierarchy structure, but it is sensitive to noise. Local search algorithm based on density is able to identify relatively dense subgraph,and the algorithm conforms to the characteristics that it’s closely linked to each other in the module. It allows modules to overlap, but can’t mine the sparse subgraph in the protein-protein interaction networks.In recent years many researchers have proposed a variety of swarm intelligence optimization algorithm, and apply them to different areas, but they also have their limitations. Such as artificial fish algorithm has not much requirements for the initial value and parameter, and has the parallel processing ability and the global optimization ability. But as the number of artificial fish grows, the need for storage space and calculation is more, and can only get the satisfied solution domain of system. And the method based on the function data flow can effectively solve the problem of clustering for PPI network, but its accuracy is low, time complexity is high. The cuckoo search algorithm not only has the advantages of simple, less parameters, easy to implement, at the same time, its two critical components, that is Levy flights random walk and preferences random walk, has significant efficiency. So this paper applied the cuckoo search algorithm to protein-protein interaction networks, and evaluation methods of the clustering results were studied.First of all, the cuckoo search algorithm was applied to the protein interaction network. This paper proposed a new similarity measure function on the basis of commonly used protein similarity function, introduced the basic algorithm of the cuckoo, a detailed description of experimental steps of the algorithm applied to the PPI network was given. Experiments on PPI data showed that the algorithm can effectively apply to protein-protein interaction networks, and the accuracy of clustering results and f-measure algorithm was better than that of artificial fish and function data flow.Then this paper studied the protein-protein interaction network clustering evaluation method. First the four typical methods evaluating clusters of PPI (protein-protein interaction) network were introduced and analyzed in this paper, which are p-value, matching statistics,f-measure based on recall and precision and hF-measure based on hierarchical structure. Besides, considering the similarity between the main error classification and the cluster predicted, a new penalty function and the new Sf-measure evaluation method was put forward lately. The simulation results showed that the features of various evaluation methods and the rationality and effectivity of Sf-measure method.