关键词: 消息传递接口, 并行化, 马尔可夫聚类, Cannon算法, 大规模生物网络

Abstract: Markov Clustering Algorithm (MCL) is an effective method to find modules in large-scale biological networks. It can mine modules that have significant influence on network structure and function. The algorithm involves large-scale matrix calculations, so its complexity can reach cubic orders. For the problem of high complexity, a parallel algorithm of Markov clustering based on Message Passing Interface (MPI) was proposed to improve computational performance of algorithm. Firstly, a biological network was transformed into an adjacency matrix. Secondly, according to the characteristics of the algorithm, the matrix size was judged and a new matrix was regenerated to handle the calculation of non-square multiple matrix. Thirdly, the algorithm was calculated in parallel by means of block allocation, which could effectively implement the operation of matrix of any size. Finally, the loop was parallelized until the matrix was converged to obtain network clustering results. The experimental results on simulated network and real biological network datasets show that compared with Full-block Collective Communication (FCC) parallel method, the average parallel efficiency is improved by more than 10 percentage points, so the optimization algorithm can be applied in different types of large-scale biological networks.

Key words: Message Passing Interface (MPI), parallelization, Markov clustering, Cannon algorithm, large-scale biological network