Addressing the embeddability problem in transition rate estimation from Markov state models

by Moradi, M.; Losey, J.; Goolsby, C.; Xu, Y. C.; Matteson, D.

Markov State Models (MSM) and related techniques have gained significant traction as a tool for analyzing and guiding molecular dynamics (MD) simulations due to their ability to extract structural, thermodynamic, and kinetic information from computationally feasible MD simulations of proteins.The MSM analysis may rely on spectral decomposition of empirically generated transition matrices. An alternative approach for extracting thermodynamic and kinetic information is to use the so-called rate/generator matrix rather than the transition matrix. Although the rate matrix itself is built from the empirical transition matrix, it provides an alternative approach for estimating both thermodynamic and kinetic quantities, particularly in diffusive processes. A fundamental issue with this approach, however, is the embeddability problem. The embeddability problem is found in taking the matrix logarithm of a time-dependent transition probability matrix in order to determine the rate/generator matrix. In theory, the lag-time dependent transition probability matrix should only have positive eigenvalues; however, in practice, insufficient sampling can result in the presence of negative eigenvalues. The key contribution of our study is the introduction of a novel method to address the embeddability problem that relies on the common eigenvector structure of the rate matrix and the transition matrix. The proposed method circumvents the spectral decomposition and provides a reasonable estimate for the rate matrix from the transition matrix that does not have the embeddability problem. The novel algorithm along with other known algorithms are tested on data from a one-dimensional toy model to show the workings of these methods and discuss the robustness of each method in dependence of lag time and trajectory length. This work presents a novel approach to analyze MSMs that is robust and computationally feasible.