Research On Functional Module Detection Algorithms Based On Ant Colony Clustering Mechanism In PPI Networks

Protein-Protein Interaction (PPI) network is composed of proteins andinteractions between proteins in organisms and belongs to complex network, whichhas the features of small-world property, scale-free distribution and function modular.Functional module detection in PPI networks is one of the bioinformatics frontierresearch topics in the post-genomic era, and it gets the wide attention and furtherresearch of scholars both at home and abroad. Functional module detection in PPInetworks not only has important significance in understanding the organizations andfunctions of biological systems, but also is the foundation of understanding thebiological behavior, predicting protein function and designing drug. In the meantime,swarm intelligence algorithms have been widely applied to solve many complexproblems due to their strong global optimization ability. Recently, functional moduledetection algorithms based on swarm intelligence in PPI networks have emerged andbecome a new research hotspot in this field. This paper researches on functionalmodule detection algorithms based on ant colony clustering mechanism in PPInetworks and the main work includes:(1)In order to improve the qulity of functional module detection, we have madestudy of ant colony clustering model and information transmission mechanisim, andproposed a novel functional module detection algorithm in PPI networks. First thisalgorithm selects the set of seed nodes based on the node clustering coefficient;second it employs the picking and dropping operations, which are based onprobabilistic models, to cluster the nodes in PPI networks; third it updates thesimilarity function using the best clustering result of each generation and functionalsimilarity between nodes, in order to perform the information transmission betweendifferent ant generations; finally it uses the post-processing process to revise theinitial clustering results and improve the effect of clustering. Experimental resultswhich are compared with other detection algorithms demonstrate that this algorithmnot only can effectively detect the functional modules in PPI networks, but also has agood performance in different datasets of PPI networks.(2)To improve the time performance of detection algorithm which is based on antcolony clustering mechanism in solving large scale PPI networks, combining with theidea of multilevel algorithm in graph clustering, we have proposed the detection algorithm of ant colony clustering combined with multilevel framework. Firstly thisalgorithm uses a new matching strategy to coarsen the original large scale PPInetwork in order to reduce the size of PPI network, and gets a smaller scale PPInetwork; then it makes use of ant colony clustering algorithm proposed in the firstwork to cluster obtained network; finally it gets the clustering result of originalnetwork through de-coarsening, and uses refinement to avoid the result from fallinginto the local optimal. Experiments in some large scale datasets show that thedetecting speed of this algorithm has significantly improved in contrast to thealgorithm in the first work, and this algorithm can get better clustering result whilecompared with other functional module detection algorithms.This paper through the research on functional module detection algorithmsbased on ant colony clustering mechanism in PPI networks, on the one hand enrichesthe theoretical study of functional module detection in PPI networks, on the otherhand improves the ability of detection algorithm based on ant colony clusteringmechanism to solve the large scale PPI networks.