Scaling k-Means for Multi-Million Frames: A Stratified NANI Approach for Large-Scale MD Simulations

Area of Science:

• Computational chemistry
• Biophysics
• Data science

Background:

• Molecular dynamics (MD) simulations generate vast datasets requiring efficient analysis.
• K-means clustering is a common technique for analyzing MD data, but initialization can be computationally expensive.
• Existing N-ary Natural Initiation (NANI) methods offer reproducible clustering but can be slow.

Purpose of the Study:

• To develop and implement faster, deterministic k-means clustering initialization strategies for MD simulations.
• To maintain or improve the quality of clustering results compared to existing methods.
• To accelerate the analysis of large-scale conformational ensembles.

Main Methods:

• Introduction of two new deterministic seeding strategies: strat_all and strat_reduced, as extensions to the NANI method.
• Implementation of these strategies within the MDANCE package.
• Evaluation using benchmark systems (β-heptapeptide and HP35) and assessment via Calinski-Harabasz and Davies-Bouldin scores.
• Demonstration of accelerated performance when integrated with the Hierarchical Extended Linkage Method (HELM).

Main Results:

• The new strat_all and strat_reduced strategies significantly reduce clustering runtime compared to previous NANI variants.
• Clustering quality, as measured by Calinski-Harabasz and Davies-Bouldin scores, remains comparable to established NANI methods.
• The enhanced NANI strategies successfully accelerate the HELM method.
• Reproducible partitioning of well-separated and compact clusters is preserved.

Conclusions:

• The improved NANI initialization strategies offer a substantial speed-up for k-means clustering in MD analysis without compromising accuracy.
• These advancements remove a significant barrier to routine, scalable, and reproducible exploration of complex molecular conformations.
• The MDANCE package provides an accessible implementation for researchers to leverage these performance enhancements.