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

Abstract

We present improved k-means clustering initialization strategies for molecular dynamics (MD) simulations, implemented as part of the N-ary Natural Initiation (NANI) method. Two new deterministic seeding strategies-strat_all and strat_reduced-extend the original NANI approaches and dramatically reduce the clustering runtime while preserving the quality of clustering results. These methods also preserve NANI's reproducible partitioning of well-separated and compact clusters while avoiding the costly iterative seed selection procedures of previous implementations. Testing on the β-heptapeptide and the HP35 systems shows that these new flavors achieved Calinski-Harabasz (CH) and Davies-Bouldin (DB) scores comparable to the previous NANI variant, indicating that the efficiency gains come with no quality decrease. We also show how this new variant can be used to greatly speed up our previously proposed Hierarchical Extended Linkage Method (HELM). These enhancements extend the reach of NANI to accelerate large-scale MD analysis both in stand-alone k-means clustering and as a component of hybrid workflows, and remove a key barrier to routine, scalable, and reproducible exploration of complex conformational ensembles. The improved NANI implementation is accessible through our MDANCE package: https://github.com/mqcomplab/MDANCE.

Figure 1:

Change in Calinski-Harabasz (A, B) and Davies-Bouldin (C, D) indices for A, C: β-heptapeptide and B, D: HP35 after k-means NANI screening from k = 5 to k = 30.

Figure 1:

Change in Calinski-Harabasz (A, B) and Davies-Bouldin (C, D) indices for A, C: β-heptapeptide and B, D: HP35 after k-means NANI screening from k = 5 to k = 30.

Figure 2:

Overlaps of best representative structures from the six clusters of β-heptapeptide after performing NANI with strat_reduced.

Figure 3:

Overlaps of best representative structures from the seven clusters of HP35 after performing NANI with strat_reduced. Helices 1, 2, and 3 are colored green, cyan, and yellow, respectively.

Figure 4:

Change in Calinski-Harabasz (A, B) and Davies-Bouldin (C, D) indices for the HP35 simulation after trimming (retaining clusters with MSD < 10) the initial NANI clusters using the inter merge (A, C) and the intra merge (B, D).

Figure 5:

Overlaps of best representative structures from the six clusters of HP35 after performing HELM from 60 NANI strat_reduced clusters using the intra merge with trimming.