Research On Functional Module Detection On PPI Networks Based On Ant Colony Clustering Algorithm And Its Parallel Mechanism

Protein-protein interactions(PPI) network is one of the most important biological molecules relation network within the organism. One of the main purpose of research and analysis for PPI network is to detect the functional module. It can help people to understand the cell functions and mechanisms, systematic unders tanding of biological processes. In recent years, the method which based machine learning and data mining became an effective way to detect functional module. New computational methods are constantly being proposed. However, with detailed research towards biological, available PPI data has become more and more abundant, either the amount of protein or the number of interactions has present a trend of increasing. In this trend, existing module detection methods face enormous challenges. Therefore, how to efficiently use clustering methods detect functional modules in the PPI network is an important research topic in bioinformatics. In this paper, we make a more in-depth research on Ant Colony Clustering for Functional Module Detection(ACC-FMD), and carry out the following two aspects of research:(1) In a clustering process, ACC-FMD requires substantial operation of merge, filter, pick-up and drop-down, which resulting in lower time performance. Aiming at the problem, we develop A Fast algorithm which fusion gene expression information based on Ant Colony Clustering(FACC-FMD). The FACC-FMD use the gene expression information to compute the essential of proteins and extract the core proteins group. FACC-FMD make use of the essential of proteins to do more stringent constraints on operation of pick-up and drop-down, reducing the times of pick-up and drop-down, accelerating the process of clustering. Experiments on three PPI networks show that the FACC-FMD can greatly improve the time performance of ACC-FMD. Moreover, FACC-FMD compared with ACC-FMD and some classical algorithms in recent years, FACC-FMD also has some advantages on detection quality.(2) To take full advantage of parallelism of Ant Colony clustering algorithm, we proposed a parallel Ant Colony Clustering algorithm in PPI network based on Map Reduce framework. The MRACC-FMD use Map Reduce computation model enable multiple Ant Colony Clustering to processing in parallel, thus shorten solution time. Multiple ant colonies search the candidate solutions, then put every best individual in all colony into elite evolutionary environment. Through the elite evolutionary environment achieve the information exchange between colonies. MRACC-FMD uses the evolution in colony and co-evolution between different colonies to prevent the algorithm into a local optimum, improving the global convergence of the solution. In experiments on the virtual cluster environment, MRACC-FMD has superior time performance, especially on large-scale PPI networks.