Path factorization approach to stochastic simulations

An encompassed representation of timescale hierarchies in first-order reaction network

Complex networks are pervasive in various fields such as chemistry, biology, and sociology. In chemistry, first-order reaction networks are represented by a set of first-order differential equations, which can be constructed from the underlying energy landscape. However, as the number of nodes increases, it becomes more challenging to understand complex kinetics across different timescales. Hence, how to construct an interpretable, coarse-graining scheme that preserves the underlying timescales of overall reactions is of crucial importance. Here, we develop a scheme to capture the underlying hierarchical subsets of nodes, and a series of coarse-grained (reduced-dimensional) rate equations between the subsets as a function of time resolution from the original reaction network. Each of the coarse-grained representations guarantees to preserve the underlying slow characteristic timescales in the original network. The crux is the construction of a lumping scheme incorporating a similarity measure in deciphering the underlying timescale hierarchy, which does not rely on the assumption of equilibrium. As an illustrative example, we apply the scheme to four-state Markovian models and Claisen rearrangement of allyl vinyl ether (AVE), and demonstrate that the reduced-dimensional representation accurately reproduces not only the slowest but also the faster timescales of overall reactions although other reduction schemes based on equilibrium assumption well reproduce the slowest timescale but fail to reproduce the second-to-fourth slowest timescales with the same accuracy. Our scheme can be applied not only to the reaction networks but also to networks in other fields, which helps us encompass their hierarchical structures of the complex kinetics over timescales.

100 Years of the Lennard-Jones Potential

It is now 100 years since Lennard-Jones published his first paper introducing the now famous potential that bears his name. It is therefore timely to reflect on the many achievements, as well as the limitations, of this potential in the theory of atomic and molecular interactions, where applications range from descriptions of intermolecular forces to molecules, clusters, and condensed matter.

Analysis and interpretation of first passage time distributions featuring rare events

In this contribution we consider theory and associated computational tools to treat the kinetics associated with competing pathways on multifunnel energy landscapes. Multifunnel landscapes are associated with molecular switches and multifunctional materials, and are expected to exhibit multiple relaxation time scales and associated thermodynamic signatures in the heat capacity. Our focus here is on the first passage time distribution, which is encoded in a kinetic transition network containing all the locally stable states and the pathways between them. This network can be renormalised to reduce the dimensionality, while exactly conserving the mean first passage time and approximately conserving the full distribution. The structure of the reduced network can be visualised using disconnectivity graphs. We show how features in the first passage time distribution can be associated with specific kinetic traps, and how the appearance of competing relaxation time scales depends on the starting conditions. The theory is tested for two model landscapes and applied to an atomic cluster and a disordered peptide. Our most important contribution is probably the reconstruction of the full distribution for long time scales, where numerical problems prevent direct calculations. Here we combine accurate treatment of the mean first passage time with the reliable part of the distribution corresponding to faster time scales. Hence we now have a fundamental understanding of both thermodynamic and kinetic signatures of multifunnel landscapes.

Analysing ill-conditioned Markov chains

Discrete state Markov chains in discrete or continuous time are widely used to model phenomena in the social, physical and life sciences. In many cases, the model can feature a large state space, with extreme differences between the fastest and slowest transition timescales. Analysis of such ill-conditioned models is often intractable with finite precision linear algebra techniques. In this contribution, we propose a solution to this problem, namely partial graph transformation, to iteratively eliminate and renormalize states, producing a low-rank Markov chain from an ill-conditioned initial model. We show that the error induced by this procedure can be minimized by retaining both the renormalized nodes that represent metastable superbasins, and those through which reactive pathways concentrate, i.e. the dividing surface in the discrete state space. This procedure typically returns a much lower rank model, where trajectories can be efficiently generated with kinetic path sampling. We apply this approach to an ill-conditioned Markov chain for a model multi-community system, measuring the accuracy by direct comparison with trajectories and transition statistics. This article is part of a discussion meeting issue 'Supercomputing simulations of advanced materials'.

Stochastic paths controlling speed and dissipation

Natural processes occur in a finite amount of time and dissipate energy, entropy, and matter. Near equilibrium, thermodynamic intuition suggests that fast irreversible processes will dissipate more energy and entropy than slow quasistatic processes connecting the same initial and final states. For small systems, recently discovered thermodynamic speed limits suggest that faster processes will dissipate more than slower processes. Here, we test the hypothesis that this relationship between speed and dissipation holds for stochastic paths far from equilibrium. To analyze stochastic paths on finite timescales, we derive an exact expression for the path probabilities of continuous-time Markov chains from the path summation solution to the master equation. We present a minimal model for a driven system in which relative energies of the initial and target states control the speed, and the nonequilibrium currents of a cycle control the dissipation. Although the hypothesis holds near equilibrium, we find that faster processes can dissipate less under far-from-equilibrium conditions because of strong currents. This model serves as a minimal prototype for designing kinetics to sculpt the nonequilibrium path space so that faster paths produce less dissipation.

Dynamical Signatures of Multifunnel Energy Landscapes

Multifunctional systems, such as molecular switches, exhibit multifunnel energy landscapes associated with the alternative functional states. In this contribution the multifunnel organization is decoded from dynamical signatures in the first passage time distribution between reactants and products. Characteristic relaxation rates are revealed by analyzing the kinetics as a function of the observation time scale, which scans the underlying distribution. Extracting the corresponding dynamical signatures provides direct insight into the organization of the molecular energy landscape, which will facilitate a rational design of target functionality. Examples are illustrated for multifunnel landscapes in biomolecular systems and an atomic cluster.

The Energy Landscape Perspective: Encoding Structure and Function for Biomolecules

The energy landscape perspective is outlined with particular reference to biomolecules that perform multiple functions. We associate these multifunctional molecules with multifunnel energy landscapes, illustrated by some selected examples, where understanding the organisation of the landscape has provided new insight into function. Conformational selection and induced fit may provide alternative routes to realisation of multifunctionality, exploiting the possibility of environmental control and distinct binding modes.

Nearly reducible finite Markov chains: Theory and algorithms

Finite Markov chains, memoryless random walks on complex networks, appear commonly as models for stochastic dynamics in condensed matter physics, biophysics, ecology, epidemiology, economics, and elsewhere. Here, we review exact numerical methods for the analysis of arbitrary discrete- and continuous-time Markovian networks. We focus on numerically stable methods that are required to treat nearly reducible Markov chains, which exhibit a separation of characteristic timescales and are therefore ill-conditioned. In this metastable regime, dense linear algebra methods are afflicted by propagation of error in the finite precision arithmetic, and the kinetic Monte Carlo algorithm to simulate paths is unfeasibly inefficient. Furthermore, iterative eigendecomposition methods fail to converge without the use of nontrivial and system-specific preconditioning techniques. An alternative approach is provided by state reduction procedures, which do not require additional a priori knowledge of the Markov chain. Macroscopic dynamical quantities, such as moments of the first passage time distribution for a transition to an absorbing state, and microscopic properties, such as the stationary, committor, and visitation probabilities for nodes, can be computed robustly using state reduction algorithms. The related kinetic path sampling algorithm allows for efficient sampling of trajectories on a nearly reducible Markov chain. Thus, all of the information required to determine the kinetically relevant transition mechanisms, and to identify the states that have a dominant effect on the global dynamics, can be computed reliably even for computationally challenging models. Rare events are a ubiquitous feature of realistic dynamical systems, and so the methods described herein are valuable in many practical applications.

Numerical analysis of first-passage processes in finite Markov chains exhibiting metastability

We describe state-reduction algorithms for the analysis of first-passage processes in discrete- and continuous-time finite Markov chains. We present a formulation of the graph transformation algorithm that allows for the evaluation of exact mean first-passage times, stationary probabilities, and committor probabilities for all nonabsorbing nodes of a Markov chain in a single computation. Calculation of the committor probabilities within the state-reduction formalism is readily generalizable to the first hitting problem for any number of alternative target states. We then show that a state-reduction algorithm can be formulated to compute the expected number of times that each node is visited along a first-passage path. Hence, all properties required to analyze the first-passage path ensemble (FPPE) at both a microscopic and macroscopic level of detail, including the mean and variance of the first-passage time distribution, can be computed using state-reduction methods. In particular, we derive expressions for the probability that a node is visited along a direct transition path, which proceeds without returning to the initial state, considering both the nonequilibrium and equilibrium (steady-state) FPPEs. The reactive visitation probability provides a rigorous metric to quantify the dynamical importance of a node for the productive transition between two endpoint states and thus allows the local states that facilitate the dominant transition mechanisms to be readily identified. The state-reduction procedures remain numerically stable even for Markov chains exhibiting metastability, which can be severely ill-conditioned. The rare event regime is frequently encountered in realistic models of dynamical processes, and our methodology therefore provides valuable tools for the analysis of Markov chains in practical applications. We illustrate our approach with numerical results for a kinetic network representing a structural transition in an atomic cluster.

Graph transformation and shortest paths algorithms for finite Markov chains

The graph transformation (GT) algorithm robustly computes the mean first-passage time to an absorbing state in a finite Markov chain. Here we present a concise overview of the iterative and block formulations of the GT procedure and generalize the GT formalism to the case of any path property that is a sum of contributions from individual transitions. In particular, we examine the path action, which directly relates to the path probability, and analyze the first-passage path ensemble for a model Markov chain that is metastable and therefore numerically challenging. We compare the mean first-passage path action, obtained using GT, with the full path action probability distribution simulated efficiently using kinetic path sampling, and with values for the highest-probability paths determined by the recursive enumeration algorithm (REA). In Markov chains representing realistic dynamical processes, the probability distributions of first-passage path properties are typically fat-tailed and therefore difficult to converge by sampling, which motivates the use of exact and numerically stable approaches to compute the expectation. We find that the kinetic relevance of the set of highest-probability paths depends strongly on the metastability of the Markov chain, and so the properties of the dominant first-passage paths may be unrepresentative of the global dynamics. Use of a global measure for edge costs in the REA, based on net productive fluxes, allows the total reactive flux to be decomposed into a finite set of contributions from simple flux paths. By considering transition flux paths, a detailed quantitative analysis of the relative importance of competing dynamical processes is possible even in the metastable regime.

Enhanced sampling method with coarse graining of conformational space

The sampling of conformations in the molecular simulations for systems with complicated free energy landscapes is always difficult. Here, we report a method for enhanced sampling based on the coarse-graining of conformational space. In this method, the locally converged region of the conformational space is coarse-grained with its population characterized by the related average residence time and visiting number, and at the same time, the direct simulations inside it are eliminated. The detailed balance is satisfied by updating the visiting number and generating outgoing trajectories of this region. This kind of coarse-graining operation can be further carried out by merging all the neighboring regions which are already converged together. The global equilibrium is achieved when the local equilibrated regions cover all the interested areas of the landscape. We tested the method by applying it to two model potentials and one protein system with multiple-basin energy landscapes. The sampling efficiency is found to be enhanced by more than three orders of magnitude compared to conventional molecular simulations, and are comparable with other widely used enhanced sampling methods. In addition, the kinetic information can also be well captured. All these results demonstrate that our method can help to solve the sampling problems efficiently and precisely without applying high temperatures or biasing potentials.

Optimal dimensionality reduction of Markov chains using graph transformation

Markov chains can accurately model the state-to-state dynamics of a wide range of complex systems, but the underlying transition matrix is ill-conditioned when the dynamics feature a separation of timescales. Graph transformation (GT) provides a numerically stable method to compute exact mean first passage times (MFPTs) between states, which are the usual dynamical observables in continuous-time Markov chains (CTMCs). Here, we generalize the GT algorithm to discrete-time Markov chains (DTMCs), which are commonly estimated from simulation data, for example, in the Markov state model approach. We then consider the dimensionality reduction of CTMCs and DTMCs, which aids model interpretation and facilitates more expensive computations, including sampling of pathways. We perform a detailed numerical analysis of existing methods to compute the optimal reduced CTMC, given a partitioning of the network into metastable communities (macrostates) of nodes (microstates). We show that approaches based on linear algebra encounter numerical problems that arise from the requisite metastability. We propose an alternative approach using GT to compute the matrix of intermicrostate MFPTs in the original Markov chain, from which a matrix of weighted intermacrostate MFPTs can be obtained. We also propose an approximation to the weighted-MFPT matrix in the strongly metastable limit. Inversion of the weighted-MFPT matrix, which is better conditioned than the matrices that must be inverted in alternative dimensionality reduction schemes, then yields the optimal reduced Markov chain. The superior numerical stability of the GT approach therefore enables us to realize optimal Markovian coarse-graining of systems with rare event dynamics.

Rare events and first passage time statistics from the energy landscape

We analyze the probability distribution of rare first passage times corresponding to transitions between product and reactant states in a kinetic transition network. The mean first passage times and the corresponding rate constants are analyzed in detail for two model landscapes and the double funnel landscape corresponding to an atomic cluster. Evaluation schemes based on eigendecomposition and kinetic path sampling, which both allow access to the first passage time distribution, are benchmarked against mean first passage times calculated using graph transformation. Numerical precision issues severely limit the useful temperature range for eigendecomposition, but kinetic path sampling is capable of extending the first passage time analysis to lower temperatures, where the kinetics of interest constitute rare events. We then investigate the influence of free energy based state regrouping schemes for the underlying network. Alternative formulations of the effective transition rates for a given regrouping are compared in detail to determine their numerical stability and capability to reproduce the true kinetics, including recent coarse-graining approaches that preserve occupancy cross correlation functions. We find that appropriate regrouping of states under the simplest local equilibrium approximation can provide reduced transition networks with useful accuracy at somewhat lower temperatures. Finally, a method is provided to systematically interpolate between the local equilibrium approximation and exact intergroup dynamics. Spectral analysis is applied to each grouping of states, employing a moment-based mode selection criterion to produce a reduced state space, which does not require any spectral gap to exist, but reduces to gap-based coarse graining as a special case. Implementations of the developed methods are freely available online.

Defining, Calculating, and Converging Observables of a Kinetic Transition Network

Kinetic transition networks (KTNs) of local minima and transition states are able to capture the dynamics of numerous systems in chemistry, biology, and materials science. However, extracting observables is numerically challenging for large networks and generally will be sensitive to additional computational discovery. To have any measure of convergence for observables, these sensitivities must be regularly calculated. We present a matrix formulation of the discrete path sampling framework for KTNs, deriving expressions for branching probabilities, transition rates, and waiting times. Using the concept of the quasi-stationary distribution, a clear hierarchy of expressions for network observables is established, from exact results to steady-state approximations. We use these results in combination with the graph transformation method to derive the sensitivity, with respect to perturbations of the known KTN, giving explicit terms for the pairwise sensitivity and discussing the pathwise sensitivity. These results provide guidelines for converging the network, with respect to additional sampling, focusing on the estimates obtained for the overall rate coefficients between product and reactant states. We demonstrate this procedure for transitions in the double-funnel landscape of the 38-atom Lennard-Jones cluster.

Estimating thermodynamic expectations and free energies in expanded ensemble simulations: Systematic variance reduction through conditioning

Markov chain Monte Carlo methods are primarily used for sampling from a given probability distribution and estimating multi-dimensional integrals based on the information contained in the generated samples. Whenever it is possible, more accurate estimates are obtained by combining Monte Carlo integration and integration by numerical quadrature along particular coordinates. We show that this variance reduction technique, referred to as conditioning in probability theory, can be advantageously implemented in expanded ensemble simulations. These simulations aim at estimating thermodynamic expectations as a function of an external parameter that is sampled like an additional coordinate. Conditioning therein entails integrating along the external coordinate by numerical quadrature. We prove variance reduction with respect to alternative standard estimators and demonstrate the practical efficiency of the technique by estimating free energies and characterizing a structural phase transition between two solid phases.

Using Bayes formula to estimate rates of rare events in transition path sampling simulations

Transition path sampling is a method for estimating the rates of rare events in molecular systems based on the gradual transformation of a path distribution containing a small fraction of reactive trajectories into a biased distribution in which these rare trajectories have become frequent. Then, a multistate reweighting scheme is implemented to postprocess data collected from the staged simulations. Herein, we show how Bayes formula allows to directly construct a biased sample containing an enhanced fraction of reactive trajectories and to concomitantly estimate the transition rate from this sample. The approach can remediate the convergence issues encountered in free energy perturbation or umbrella sampling simulations when the transformed distribution insufficiently overlaps with the reference distribution.