Research On Functional Module Detection From PPI Network Based On Ant Colony Optimization

As a biomolecular relationship network, Protein-Protein Interaction (PPI)network plays an important role in biological activities. Based on computationalapproaches, mining functional modules from a PPI network is currently a challengetopic in bioinformatics. According to the topology of PPI network and characteristicof functional module, researchers have proposed many different types of detectionmethods. Among them, the clustering method based on swarm intelligence, whichemerged in recent years, has become one research hot in the field of functionalmodule detection from PPI network. Ant colony optimization（ACO）is one of thetypical swarm intelligence algorithms, based on which some research work are carriedout from the following two aspects:(1) For the problem that PPI network has high noise, and the detection functionalmodules have low accuracy, a new detection algorithm is proposed which based onACO by incorporating proteins’ functional annotation information. Firstly, thealgorithm computes topological distance and functional similarity distance accordingto the topological structure of PPI network and proteins’ Gene Ontology（GO）information respectively, which are incorporated into a new heuristic function. Then,using this new heuristic function, ants build the touring path to find the optimal pathwhich can reflect topological features and functional information. Finally, the initialmodules are obtained by separating the optimization tour according to a cut-offthreshold, in order to improve the quality of detection modules, the initial modules aremerged according to the module consolidation strategy combined with functionalannotation information. Experimental results on four PPI networks show thatcompared with some other classical clustering algorithms, our algorithm representssuperior performance in several assessment metrics.(2) In order to overcome the shortcoming that the algorithm mentioned aboveeasily falls into local optima, a novel detection algorithm is proposed combined ACOwith multi-Agent evolution. The novel algorithm firstly employs ACO to construct theoptimal paths in each iteration. Then, the optimal paths are further optimized throughmulti-Agent’s three evolutionary operations. Afterwards, pheromone is updated on thecode path of each Agent, which can instruct ants to escape from local optima in thefollowing search. Finally, when the algorithm iterates over, the initial functionmodules are obtained by automatically decoding mechanism, and then the initialmodules are merged to get the final modules. Several experiments show that the newalgorithm can effectively overcome the shortcoming of falling into local optima, andhas obviously competitive compared with some other algorithms. This paper achieves two novel methods of functional module detection from PPInetwork, which not only expands the application fields of ant colony optimization, butalso provides useful reference for the research of other complex networks.