Premium
A fast parallel clustering algorithm for molecular simulation trajectories
Author(s) -
Zhao Yutong,
Sheong Fu Kit,
Sun Jian,
Sander Pedro,
Huang Xuhui
Publication year - 2012
Publication title -
journal of computational chemistry
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.907
H-Index - 188
eISSN - 1096-987X
pISSN - 0192-8651
DOI - 10.1002/jcc.23110
Subject(s) - cluster analysis , molecular dynamics , computer science , cluster (spacecraft) , algorithm , dipeptide , ranging , metric (unit) , chemistry , computational chemistry , amino acid , artificial intelligence , telecommunications , biochemistry , programming language , operations management , economics
We implemented a GPU‐powered parallel k ‐centers algorithm to perform clustering on the conformations of molecular dynamics (MD) simulations. The algorithm is up to two orders of magnitude faster than the CPU implementation. We tested our algorithm on four protein MD simulation datasets ranging from the small Alanine Dipeptide to a 370‐residue Maltose Binding Protein (MBP). It is capable of grouping 250,000 conformations of the MBP into 4000 clusters within 40 seconds. To achieve this, we effectively parallelized the code on the GPU and utilize the triangle inequality of metric spaces. Furthermore, the algorithm's running time is linear with respect to the number of cluster centers. In addition, we found the triangle inequality to be less effective in higher dimensions and provide a mathematical rationale. Finally, using Alanine Dipeptide as an example, we show a strong correlation between cluster populations resulting from the k ‐centers algorithm and the underlying density. © 2012 Wiley Periodicals, Inc.