Markov state models

Here we introduce several types of markov state models as well as analysis tools related to them. At the very core, markov state models are a stochastic model describing chains of events where the state of one particular point in time only depends on the state prior to it, i.e., considering the chain of events \((\ldots,X_{t-2}, X_{t-1}, X_t)\) with a set of possible states \(S\), the probability of encountering a particular state \(X_{t+1}\in S\) is a conditional probability on \(X_t\in S\).

A great deal is written about MSMs in the literature, so we omit many crucial discussions here. The 2018 review by Husic and Pande [1] is a good place to start for a high-level discussion of Markov state models and a chronology of their development in the context of molecular kinetics. Figure 3 is particularly helpful for understanding the many “flavors” of MSM analyses developed. A comprehensive overview of the mathematics was presented by Prinz et al [2], including the MLE estimator used in Maximum Likelihood MSMs. This content is also covered in Chapter 4 of a useful book on Markov state models [3], which is a valuable resource for many aspects of Markov state modeling (see book Figure 1.1).

The standard formulation - which is also employed here - assumes that \(S\) is discrete and of finite cardinality. This means that when related back to continuous-space processes, these discrete states represent a Voronoi tessellation of state space and can be obtained via indicator functions.

These conditional probabilities are often described as so-called transition matrix \(P\in \mathbb{R}^{n\times n}\), where \(n = |S|\), the number of states. Assuming that \(S\) is represented by the enumeration \(\{1,\ldots,n\}\), it is

\[P_{ij} = \mathbb{P}(X_{t+1}=j \mid X_t = i)\quad\forall t, \]

i.e., the probability of transitioning to state \(i\) given one is currently in state \(j\). This also means that \(P\) is a row-stochastic matrix

\[\sum_{j=1}^n P_{ij} = 1 \quad\forall i=1,\ldots,n. \]

If a markov state model is available, interesting dynamical quantities can be computed, e.g., mean first passage times and fluxes between (sets of) states [4], timescales, metastable decompositions of markov states [5].

The goal of the deeptime.markov package is to provide tools to estimate and analyze markov state models from discrete-state timeseries data. If the data’s domain is not discrete, clustering can be employed to assign each frame to a state.

In the following, we introduce the core object, the MarkovStateModel, as well as a variety of estimators.

When estimating a MSM from time series data, it is important to collect statistics over the encountered state transitions. This is covered in transition counting.

• Transition counting
• Maximum-likelihood MSMs
• Coarse-graining with PCCA+
• Transition path theory

Furthermore, deeptime implements Augmented Markov models [6] which can be used when experimental data is available, as well as Observable Operator Model MSMs [7] which is an unbiased estimator for the MSM transition matrix that corrects for the effect of starting out of equilibrium, even when short lag times are used.

Multiensemble MSMs

Deeptime offers the TRAM method [8] for estimating multiensemble MSMs. These are collections of MSMs based on simulations that are governed by biased dynamics (i.e., replica exchange simulations and umbrella sampling).

• TRAM

References

[1]

Brooke E Husic and Vijay S Pande. Markov state models: from an art to a science. Journal of the American Chemical Society, 140(7):2386–2396, 2018.

[2]

Jan-Hendrik Prinz, Hao Wu, Marco Sarich, Bettina Keller, Martin Senne, Martin Held, John D Chodera, Christof Schütte, and Frank Noé. Markov models of molecular kinetics: generation and validation. The Journal of chemical physics, 134(17):174105, 2011.

[3]

Gregory R Bowman, Vijay S Pande, and Frank Noé. An introduction to Markov state models and their application to long timescale molecular simulation. Volume 797. Springer Science & Business Media, 2013.

[4]

Philipp Metzner, Christof Schütte, and Eric Vanden-Eijnden. Transition path theory for markov jump processes. Multiscale Modeling & Simulation, 7(3):1192–1219, 2009.

[5]

Susanna Röblitz and Marcus Weber. Fuzzy spectral clustering by pcca+: application to markov state models and data classification. Advances in Data Analysis and Classification, 7(2):147–179, 2013.

[6]

Simon Olsson, Hao Wu, Fabian Paul, Cecilia Clementi, and Frank Noé. Combining experimental and simulation data of molecular processes via augmented markov models. Proceedings of the National Academy of Sciences, 114(31):8265–8270, 2017.

[7]

Feliks Nüske, Hao Wu, Jan-Hendrik Prinz, Christoph Wehmeyer, Cecilia Clementi, and Frank Noé. Markov state models from short non-equilibrium simulations—analysis and correction of estimation bias. The Journal of Chemical Physics, 146(9):094104, 2017.

[8]

Hao Wu, Fabian Paul, Christoph Wehmeyer, and Frank Noé. Multiensemble markov models of molecular thermodynamics and kinetics. Proceedings of the National Academy of Sciences, 113(23):E3221–E3230, 2016.