Multi-Level DBSCAN: A Hierarchical Density-Based Clustering Method for Analyzing Molecular Dynamics Simulation Trajectories

Molecular Dynamic (MD) simulations have been extensively used as a powerful tool to investigate dynamics of biological molecules in recent decades. Generally, MD simulations generate high-dimensional data that is very hard to visualize and comprehend. As a result, clustering algorithms have been commonly used to reduce the dimensionality of MD data with the key benefit being their ability to reduce the dimensionality of MD data without prior knowledge of structural details or dynamic mechanisms. In this paper, we propose a new algorithm, the Multi-Level Density-Based Spatial Clustering of Applications with Noise (ML-DBSCAN), which combines the clustering results at different resolution of density levels to obtain the hierarchical structure of the free energy landscape and the metastable state assignment. At relatively low resolutions, the ML-DBSCAN can efficiently detect high population regions that contain all metastable states, while at higher resolutions, the ML-DBSCAN can find all metastable states and structural details of the free energy landscape. We demonstrate the powerfulness of the ML-DBSCAN in generating metastable states with a particle moving in a Mexican hat-like potential, and four peptide and protein examples are used to demonstrate how hierarchical structures of free energy landscapes can be found. Furthermore, we developed a GPU implementation of the ML-DBSCAN, which allows the algorithm to handle larger MD datasets and be up to two orders of magnitude faster than the CPU implementation. We demonstrate the power of the ML-DBSCAN on MD simulation datasets of five systems: a 2D-potential, alanine dipeptide, {beta}-hairpin Tryptophan Zipper 2 (Trpzip2), Human Islet Amyloid Polypeptide (hIAPP), and Maltose Binding Protein (MBP). Our code is available at https://github.com/liusong299/ML-DBSCAN.