title: A fast parallel clustering algorithm for molecular simulation trajectories.
abstract: 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.
authors.affiliation: Department of Chemistry, The Hong Kong University of Science and Technology, Clear Water Bay, Kowloon, Hong Kong.
authors.forename: Yutong
authors.initials: Y
authors.lastname: Zhao
authors.forename: Fu Kit
authors.initials: FK
authors.lastname: Sheong
authors.forename: Jian
authors.initials: J
authors.lastname: Sun
authors.forename: Pedro
authors.initials: P
authors.lastname: Sander
authors.forename: Xuhui
authors.initials: X
authors.lastname: Huang
mesh_terms: D000465:Algorithms; D016000:Cluster Analysis; D004151:Dipeptides / Q000737:chemistry; D004926:Escherichia coli / Q000737:chemistry; D029968:Escherichia coli Proteins / Q000737:chemistry; D058228:Islet Amyloid Polypeptide / Q000737:chemistry; D058619:Maltose-Binding Proteins / Q000737:chemistry; D056004:Molecular Dynamics Simulation; D011487:Protein Conformation; D011506:Proteins / Q000737:chemistry*
chemical_list: D004151:Dipeptides; D029968:Escherichia coli Proteins; D058228:Islet Amyloid Polypeptide; D058619:Maltose-Binding Proteins; D011506:Proteins; C539234:Trpzip2 protein; C002956:alanylalanine