Parallel clustering algorithm for large-scale biological data sets.
BACKGROUND
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.


RESULTS
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.
School of Computer Engineering and Science, Shanghai University, Shanghai, P.R.China.
Minchao
M
Wang
School of Computer Engineering and Science, Shanghai University, Shanghai, P.R.China; High Performance Computing Center, Shanghai University, Shanghai, P.R.China.
Wu
W
Zhang
School of Computer Engineering and Science, Shanghai University, Shanghai, P.R.China.
Wang
W
Ding
School of Computer Engineering and Science, Shanghai University, Shanghai, P.R.China.
Dongbo
D
Dai
School of Computer Engineering and Science, Shanghai University, Shanghai, P.R.China.
Huiran
H
Zhang
College of Stomatology, Wuhan University, Wuhan, P.R.China.
Hao
H
Xie
School of Computer Engineering and Science, Shanghai University, Shanghai, P.R.China; Key Laboratory of Systems Biology, Shanghai Institutes for Biological Sciences, Chinese Academy of Sciences, Shanghai, P.R.China.
Luonan
L
Chen
School of Computer Engineering and Science, Shanghai University, Shanghai, P.R.China; Department of Computing, Imperial College London, London, United Kingdom.
Yike
Y
Guo
School of Computer Engineering and Science, Shanghai University, Shanghai, P.R.China.
Jiang
J
Xie
D000465:Algorithms; D016000:Cluster Analysis; D019295:Computational Biology / Q000379:methods*; D030562:Databases, Protein / Q000706:statistics & numerical data; D066264:Datasets as Topic / Q000706:statistics & numerical data*; D020869:Gene Expression Profiling / Q000706:statistics & numerical data; D057166:High-Throughput Screening Assays / Q000706:statistics & numerical data; D006801:Humans; D046228:Microarray Analysis / Q000706:statistics & numerical data; D005810:Multigene Family; D011506:Proteins / Q000032:analysis / Q000378:metabolism; D040901:Proteomics
D011506:Proteins