Parallel clustering algorithm for large-scale biological data sets

Abstract

Backgrounds: Recent explosion of biological data brings a great challenge for the traditional clustering algorithms. With increasing scale of data sets, much larger memory and longer runtime are required for the cluster identification problems. The affinity propagation algorithm outperforms many other classical clustering algorithms and is widely applied into the biological researches. However, the time and space complexity become a great bottleneck when handling the large-scale data sets. Moreover, the similarity matrix, whose constructing procedure takes long runtime, is required before running the affinity propagation algorithm, since the algorithm clusters data sets based on the similarities between data pairs.

Methods: Two types of parallel architectures are proposed in this paper to accelerate the similarity matrix constructing procedure and the affinity propagation algorithm. The memory-shared architecture is used to construct the similarity matrix, and the distributed system is taken for the affinity propagation algorithm, because of its large memory size and great computing capacity. An appropriate way of data partition and reduction is designed in our method, in order to minimize the global communication cost among processes.

Result: A speedup of 100 is gained with 128 cores. The runtime is reduced from serval hours to a few seconds, which indicates that parallel algorithm is capable of handling large-scale data sets effectively. The parallel affinity propagation also achieves a good performance when clustering large-scale gene data (microarray) and detecting families in large protein superfamilies.

Figure 1. Runtime and speedup of constructing similarity matrix for different data partition ways.

The axis represents the number of cores, and the axis represents the runtime and speedup.

Figure 2. Runtime and speedup of parallel affinity propagation algorithm.

(a) shows the runtime of the five biological data sets. (b) shows the speedup of cd40 and enolase data sets.

Figure 3. The F-Measure score of some large clusters on two protein data sets.

The F-measure score, recall score and precision score are calculated. The axis and axis represent the cluster and its corresponding best score value, respectively. Some tiny and singleton clusters are not considered in the figure.

Figure 4. Partition of the input biological matrix.

Rows of the input matrix are assigned to different cores to calculate the similarities with others (each row represents a data point; and represent the row number of the input matrix and the dimension of each row, respectively; represents the similarity between data point and ; represents the number of available cores).

Figure 5. The computing load on cores for different data partition ways.

(a) The computing load of whole data set on one core. The computing loads on the cores which are assigned the upper rows of input matrix are much more than that on the cores which are assigned the lower rows. (b) The computing load on cores when the input matrix is partitioned by the sequence partition. (c) The computing load on cores when the input matrix is partitioned by the shutter partition.

Figure 6. Partition of three information matrices.

All three matrices are partitioned by the row. For a matrix with rows and a computing cluster with machine nodes, each node is assigned about rows of each information matrix. In each node, the rows are processed by cores concurrently.

Figure 7. The procedure of computing availability messages.

There are processes , and each process is assigned about rows of the availability messages matrix after partitioning. In each row, there are column. In order to reduce the communication cost, each process computes the local summation of the columns and stores the intermediate values in the Local Summation Array firstly, and then these local values in all processes are gathered and scattered to compute the global summation of the columns.