Hierarchical Nyström methods for constructing Markov state models for conformational dynamics

Yuan Yao, Raymond Z. Cui, Gregory R. Bowman, Daniel‐Adriano Silva, Jian Sun, Xuhui HuangThe Journal of Chemical Physics 2013 · DOI

TL;DR

This paper introduces a novel hierarchical approach, the Hierarchical Nyström Extension Graph (HNEG), for building Markov State Models (MSMs) from molecular dynamics simulations. HNEG effectively addresses the challenge of poorly sampled microstates, a common issue in MSM construction, by leveraging the Nyström method to robustly identify metastable states, leading to more accurate and interpretable models of molecular dynamics.

What Problem Does This Paper Address?

Understanding the complex conformational dynamics of biomolecules like proteins is crucial for fields ranging from drug discovery to materials science. Molecular Dynamics (MD) simulations generate vast amounts of data, and Markov State Models (MSMs) are a powerful tool for analyzing this data to reveal the underlying kinetic and thermodynamic landscape.

MSMs work by dividing the molecule's conformational space into many small "microstates" and then building a transition probability matrix that describes how likely the molecule is to move between these microstates over time. To make these models understandable, these microstates are then grouped into larger "macrostates" that represent more stable, long-lived configurations.

However, a significant challenge arises from finite sampling: MD simulations, even long ones, may not thoroughly explore all possible conformations. This leads to "poorly sampled microstates" where very few transitions into or out of them are observed. When these states are lumped into macrostates, they can be mistakenly identified as kinetically important because the limited observed transitions make them appear to be separated by large energy barriers. This can lead to inaccurate models and obscure the truly important dynamics.

This paper tackles this problem by proposing a new method that can robustly identify metastable states even in the presence of these noisy, poorly sampled microstates.

Methods

The core of the paper's contribution lies in the Hierarchical Nyström Extension Graph (HNEG) method. This approach builds upon the Nyström method, an algebraic technique for approximating matrices. Here's how it works:

  • Nyström Method for Matrix Approximation: The Nyström method is adapted to approximate the eigenvectors of the transition probability matrix. This is particularly useful because the leading eigenvectors of this matrix are key to identifying metastable states. The method focuses on a dominant submatrix (denoted 'A') of the transition matrix, assuming that the remaining parts ('B' and 'C') are smaller and less influential. This allows for a more stable approximation of the important eigenvectors, even when the full matrix is noisy due to poor sampling.
  • Hierarchical Structure: Instead of applying the Nyström method to the entire transition matrix at once, HNEG employs a hierarchical strategy. Microstates are first sorted by their population (how frequently they are visited). The method then progressively applies spectral clustering to subsets of microstates, starting with the most populated ones and moving to less populated ones. This "top-down" approach ensures that the spectral clustering is guided by the well-sampled regions of the conformational space, preventing it from being misled by sparsely populated, noisy states.
  • Graph Construction: The hierarchical clustering results are used to build a directed graph (the Hierarchical Nyström Extension Graph). Nodes in this graph represent clusters of microstates at different levels of the hierarchy, and edges represent transitions between these clusters. This graph visually represents the multiscale nature of the free energy landscape.
  • Lumping: Finally, the graph is used to lump microstates into metastable macrostates. Attraction nodes (nodes with no outgoing edges to lower levels) are identified as metastable states, and other states are assigned to these basins based on transition probabilities.

This hierarchical approach, combined with the Nyström method, is novel in its ability to systematically handle poorly sampled states and capture the multiscale nature of molecular dynamics.

Datasets

The authors validate their HNEG algorithm on two well-studied molecular systems:

  • Alanine Dipeptide: This dataset is taken from Chodera et al. [4] and consists of 975 simulations, resulting in 195,000 conformations. These conformations were initially clustered into 5000 microstates using a K-centers algorithm based on backbone root mean square deviation (RMSD).
  • Trpzip2 Peptide: This dataset is from Zhuang et al. [13] and comprises 830 simulations, yielding 415,000 conformations. These were clustered into 2000 microstates using a K-centers algorithm based on heavy atom RMSD.

These datasets are standard benchmarks in the field for testing methods related to conformational dynamics and MSM construction.

Key Insights and Ideas

  • Poorly Sampled States are a Major Bottleneck: The paper clearly articulates how insufficient sampling can lead to spurious macrostates, distorting the kinetic picture of molecular dynamics.
  • Nyström Method as a Robust Estimator: The Nyström method provides a mathematically grounded way to approximate the important parts of the transition matrix, making it resilient to noise from sparse data.
  • Hierarchy is Key for Multiscale Dynamics: By processing microstates from high to low population, the HNEG method naturally captures the multiscale nature of free energy landscapes, revealing both fast and slow dynamics.
  • Focusing on the Dominant Submatrix: The core idea of the Nyström method – focusing on a well-sampled submatrix – is crucial for filtering out noise and identifying true metastable states.
  • HNEG Outperforms Traditional Methods: The results strongly suggest that HNEG provides a more accurate and robust way to identify metastable states compared to established methods like PCCA, especially when dealing with limited sampling.

Key Results

The paper demonstrates the effectiveness of HNEG through comparisons with the popular Perron Cluster Cluster Analysis (PCCA) method on both alanine dipeptide and trpzip2 peptide systems.

  • Alanine Dipeptide:
    • HNEG successfully identified 6 metastable states, consistent with previous studies.
  • Bayesian comparison showed that HNEG models had a significantly higher posterior probability (ln B > 100) than PCCA models, indicating a better lumping.
  • The Hierarchical Nyström Extension Graph (HNEG) provided a hierarchical representation of the free energy landscape, with attraction nodes corresponding to deep free energy basins.
  • Trpzip2 Peptide:
    • HNEG models consistently achieved higher posterior probabilities than PCCA models (ln B ∈ [250, 500]).
  • The optimal lumping for trpzip2 identified 13 metastable macrostates, with macrostate 3 (a folded hairpin structure) being the most populated (38.5%).
  • HNEG efficiently captured highly populated metastable regions, whereas PCCA tended to identify sparsely populated states first.
  • HNEG identified 9 large macrostates (> 2% population) with a total of less than 20 macrostates, while PCCA required nearly 80 states to achieve a similar identification.
  • The method showed robustness, consistently identifying large macrostates even when excluding up to 50% of the least populated microstates.
  • Pairwise mutual information calculations showed that HNEG-generated lumpings were significantly more similar to the optimal lumping than those generated by PCCA.

Limitations and Future Work

  • Parameter Selection: The paper acknowledges that the choice of level sets (i.e., how to divide microstates into population-based subsets) is a crucial parameter. While they used a Bayes factor approach to select optimal level sets, this remains an area for further refinement.
  • Computational Cost: While HNEG is presented as efficient, the initial clustering and sorting of microstates can still be computationally intensive for very large systems.
  • Future Work: The authors suggest that the Nyström method's algebraic framework could be extended to other areas of coarse-graining and multiscale analysis. Further exploration of optimal parameter selection strategies for the hierarchical decomposition is also implied. The robustness of the method to different choices of submatrix 'A' and its impact on recovering original Markov chains is also a key area of ongoing research.

Summary updated

Abstract

Markov state models (MSMs) have become a popular approach for investigating the conformational dynamics of proteins and other biomolecules. MSMs are typically built from numerous molecular dynamics simulations by dividing the sampled configurations into a large number of microstates based on geometric criteria. The resulting microstate model can then be coarse-grained into a more understandable macrostate model by lumping together rapidly mixing microstates into larger, metastable aggregates. However, finite sampling often results in the creation of many poorly sampled microstates. During coarse-graining, these states are mistakenly identified as being kinetically important because transitions to/from them appear to be slow. In this paper, we propose a formalism based on an algebraic principle for matrix approximation, i.e., the Nyström method, to deal with such poorly sampled microstates. Our scheme builds a hierarchy of microstates from high to low populations and progressively applies spectral clustering on sets of microstates within each level of the hierarchy. It helps spectral clustering identify metastable aggregates with highly populated microstates rather than being distracted by lowly populated states. We demonstrate the ability of this algorithm to discover the major metastable states on two model systems, the alanine dipeptide and trpzip2 peptide.
BibTeX
@article{yao2013hierarchical,
  author = {Yuan Yao and Raymond Z. Cui and Gregory R. Bowman and Daniel‐Adriano Silva and Jian Sun and Xuhui Huang},
  title = {{Hierarchical Nyström methods for constructing Markov state models for conformational dynamics}},
  journal = {The Journal of Chemical Physics},
  year = {2013},
  doi = {10.1063/1.4802007},
}
Figure