Optimizing the sampling and staging for simulations of rare events via forward flux sampling schemes

In this work, we present an adaptive algorithm to optimize the phase space sampling for simulations of rare events in complex systems via forward flux sampling (FFS) schemes. In FFS, interfaces are used to partition the phase space along an order parameter lambda connecting the initial and final regions of interest. Since the kinetic "bottleneck" regions along the order parameter are not usually known beforehand, an adaptive procedure is used that first finds these regions by estimating the rate constants associated with reaching subsequent interfaces; thereafter, the FFS simulation is reset to concentrate the sampling on those bottlenecks. The approach can optimize for either the number and position of the interfaces (i.e., optimized lambda phase staging) or the number M of fired trial runs per interface (i.e., the {M(i)} set) to minimize the statistical error in the rate constant estimation per simulation period. For example, the optimization of the lambda staging leads to a net constant flux of partial trajectories between interfaces and hence a constant flux of connected paths throughout the region between the two end states. The method is demonstrated for several test systems, including the folding of a lattice protein. It is shown that the proposed approach leads to an optimized lambda staging and {M(i)} set which increase the computational efficiency of the sampling algorithm.     

Simulating rare events in equilibrium or nonequilibrium stochastic systems

We present three algorithms for calculating rate constants and sampling transition paths for rare events in simulations with stochastic dynamics. The methods do not require a priori knowledge of the phase-space density and are suitable for equilibrium or nonequilibrium systems in stationary state. All the methods use a series of interfaces in phase space, between the initial and final states, to generate transition paths as chains of connected partial paths, in a ratchetlike manner. No assumptions are made about the distribution of paths at the interfaces. The three methods differ in the way that the transition path ensemble is generated. We apply the algorithms to kinetic Monte Carlo simulations of a genetic switch and to Langevin dynamics simulations of intermittently driven polymer translocation through a pore. We find that the three methods are all of comparable efficiency, and that all the methods are much more efficient than brute-force simulation.     

Sampling diffusive transition paths

The authors address the problem of sampling double-ended diffusive paths. The ensemble of paths is expressed using a symmetric version of the Onsager-Machlup formula, which only requires evaluation of the force field and which, upon direct time discretization, gives rise to a symmetric integrator that is accurate to second order. Efficiently sampling this ensemble requires avoiding the well-known stiffness problem associated with the sampling of infinitesimal Brownian increments of the path, as well as a different type of stiffness associated with the sampling of the coarse features of long paths. The fine-feature sampling stiffness is eliminated with the use of the fast sampling algorithm, and the coarse-feature sampling stiffness is avoided by introducing the sliding and sampling (S&S) algorithm. A key feature of the S&S algorithm is that it enables massively parallel computers to sample diffusive trajectories that are long in time. The authors use the algorithm to sample the transition path ensemble for the structural interconversion of the 38-atom Lennard-Jones cluster at low temperature.     

Finding pathways between distant local minima

We report a new algorithm for constructing pathways between local minima that involve a large number of intervening transition states on the potential energy surface. A significant improvement in efficiency has been achieved by changing the strategy for choosing successive pairs of local minima that serve as endpoints for the next search. We employ Dijkstra's algorithm [E. W. Dijkstra, Numer. Math. 1, 269 (1959)] to identify the "shortest" path corresponding to missing connections within an evolving database of local minima and the transition states that connect them. The metric employed to determine the shortest missing connection is a function of the minimized Euclidean distance. We present applications to the formation of buckminsterfullerene and to the folding of various biomolecules: the B1 domain of protein G, tryptophan zippers, and the villin headpiece subdomain. The corresponding pathways contain up to 163 transition states and will be used in future discrete path sampling calculations.     

Conformational transition free energy profiles of an adsorbed, lattice model protein by multicanonical Monte Carlo simulation

Proteins often undergo changes in internal conformation upon interacting with a surface. We investigate the thermodynamics of surface induced conformational change in a lattice model protein using a multicanonical Monte Carlo method. The protein is a linear heteropolymer of 27 segments (of types A and B) confined to a cubic lattice. The segmental order and nearest neighbor contact energies are chosen to yield, in the absence of an adsorbing surface, a unique 3x3x3 folded structure. The surface is a plane of sites interacting either equally with A and B segments (equal affinity surface) or more strongly with the A segments (A affinity surface). We use a multicanonical Monte Carlo algorithm, with configuration bias and jump walking moves, featuring an iteratively updated sampling function that converges to the reciprocal of the density of states 1/Omega(E), E being the potential energy. We find inflection points in the configurational entropy, S(E)=k ln Omega(E), for all but a strongly adsorbing equal affinity surface, indicating the presence of free energy barriers to transition. When protein-surface interactions are weak, the free energy profiles F(E)=E-TS(E) qualitatively resemble those of a protein in the absence of a surface: a free energy barrier separates a folded, lowest energy state from globular, higher energy states. The surface acts in this case to stabilize the globular states relative to the folded state. When the protein surface interactions are stronger, the situation differs markedly: the folded state no longer occurs at the lowest energy and free energy barriers may be absent altogether.     

An efficient self-optimized sampling method for rare events in nonequilibrium systems

Rare events such as nucleation processes are of ubiquitous importance in real systems.The most popular method for nonequilibrium systems,forward flux sampling(FFS),samples rare events by using interfaces to partition the whole transition process into sequence of steps along an order parameter connecting the initial and final states.FFS usually suffers from two main difficulties:low computational efficiency due to bad interface locations and even being not applicable when trapping into unknown intermediate metastable states.In the present work,we propose an approach to overcome these difficulties,by self-adaptively locating the interfaces on the fly in an optimized manner.Contrary to the conventional FFS which set the interfaces with equal distance of the order parameter,our approach determines the interfaces with equal transition probability which is shown to satisfy the optimization condition.This is done by firstly running long local trajectories starting from the current interface i to get the conditional probability distribution Pc(>i|i),and then determining i+1by equaling Pc(i+1|i)to a give value p0.With these optimized interfaces,FFS can be run in a much more efficient way.In addition,our approach can conveniently find the intermediate metastable states by monitoring some special long trajectories that neither end at the initial state nor reach the next interface,the number of which will increase sharply from zero if such metastable states are encountered.We apply our approach to a two-state model system and a two-dimensional lattice gas Ising model.Our approach is shown to be much more efficient than the conventional FFS method without losing accuracy,and it can also well reproduce the two-step nucleation scenario of the Ising model with easy identification of the intermediate metastable state.     

Rate constants for diffusive processes by partial path sampling

We introduce a path sampling method for the computation of rate constants for complex systems with a highly diffusive character. Based on the recently developed transition interface sampling (TIS) algorithm this procedure increases the efficiency by sampling only parts of complete transition trajectories. The algorithm assumes the loss of memory for diffusive progression along the reaction coordinate. We compare the new partial path technique to the TIS method for a simple diatomic system and show that the computational effort of the new method scales linearly, instead of quadratically, with the width of the diffusive barrier. The validity of the memory loss assumption is also discussed.     

Efficient methods for finding transition states in chemical reactions: comparison of improved dimer method and partitioned rational function optimization method

A combination of interpolation methods and local saddle-point search algorithms is probably the most efficient way of finding transition states in chemical reactions. Interpolation methods such as the growing-string method and the nudged-elastic band are able to find an approximation to the minimum-energy pathway and thereby provide a good initial guess for a transition state and imaginary mode connecting both reactant and product states. Since interpolation methods employ usually just a small number of configurations and converge slowly close to the minimum-energy pathway, local methods such as partitioned rational function optimization methods using either exact or approximate Hessians or minimum-mode-following methods such as the dimer or the Lanczos method have to be used to converge to the transition state. A modification to the original dimer method proposed by [Henkelman and Jonnson J. Chem. Phys. 111, 7010 (1999)] is presented, reducing the number of gradient calculations per cycle from six to four gradients or three gradients and one energy, and significantly improves the overall performance of the algorithm on quantum-chemical potential-energy surfaces, where forces are subject to numerical noise. A comparison is made between the dimer methods and the well-established partitioned rational function optimization methods for finding transition states after the use of interpolation methods. Results for 24 different small- to medium-sized chemical reactions covering a wide range of structural types demonstrate that the improved dimer method is an efficient alternative saddle-point search algorithm on medium-sized to large systems and is often even able to find transition states when partitioned rational function optimization methods fail to converge.     

Computation of nucleation at a nonequilibrium first-order phase transition using a rare-event algorithm

We introduce a new forward flux sampling in time algorithm to efficiently measure transition times in rare-event processes in nonequilibrium systems and apply it to study the first-order (discontinuous) kinetic transition in the Ziff-Gulari-Barshad model of catalytic surface reaction. The average time for the transition to take place, as well as both the spinodal and transition points, is efficiently found by this method.     

Monte Carlo sampling algorithm for searching a scale-transformed energy space of polypeptides

A Monte Carlo sampling algorithm for searching a scale-transformed conformational energy space of polypeptides is presented. This algorithm is based on the assumption that energy barriers can be overcome by a uniform sampling of the logarithmically transformed energy space. This algorithm is tested with Met-enkephalin. For comparison, the entropy sampling Monte Carlo (ESMC) simulation is performed. First, the global minimum is easily found by the optimization of a scale-transformed energy space. With a new Monte Carlo sampling, energy barriers of 3000 kcal/mol are frequently overcome, and low-energy conformations are sampled more efficiently than with ESMC simulations. Several thermodynamic quantities are calculated with good accuracy.     

Biomolecular free energy profiles by a shooting/umbrella sampling protocol, "BOLAS"

We develop an efficient technique for computing free energies corresponding to conformational transitions in complex systems by combining a Monte Carlo ensemble of trajectories generated by the shooting algorithm with umbrella sampling. Motivated by the transition path sampling method, our scheme "BOLAS" (named after a cowboy's lasso) preserves microscopic reversibility and leads to the correct equilibrium distribution. This makes possible computation of free energy profiles along complex reaction coordinates for biomolecular systems with a lower systematic error compared to traditional, force-biased umbrella sampling protocols. We demonstrate the validity of BOLAS for a bistable potential, and illustrate the method's scope with an application to the sugar repuckering transition in a solvated deoxyadenosine molecule.     

Error analysis and efficient sampling in Markovian state models for molecular dynamics

In previous work, we described a Markovian state model (MSM) for analyzing molecular-dynamics trajectories, which involved grouping conformations into states and estimating the transition probabilities between states. In this paper, we analyze the errors in this model caused by finite sampling. We give different methods with various approximations to determine the precision of the reported mean first passage times. These approximations are validated on an 87 state toy Markovian system. In addition, we propose an efficient and practical sampling algorithm that uses these error calculations to build a MSM that has the same precision in mean first passage time values but requires an order of magnitude fewer samples. We also show how these methods can be scaled to large systems using sparse matrix methods.     

Simulated tempering based on global balance or detailed balance conditions: Suwa–Todo,heat bath,and Metropolis algorithms

Simulated tempering (ST) is a useful method to enhance sampling of molecular simulations. When ST is used, the Metropolis algorithm, which satisfies the detailed balance condition, is usually applied to calculate the transition probability. Recently, an alternative method that satisfies the global balance condition instead of the detailed balance condition has been proposed by Suwa and Todo. In this study, ST method with the Suwa–Todo algorithm is proposed. Molecular dynamics simulations with ST are performed with three algorithms (the Metropolis, heat bath, and Suwa–Todo algorithms) to calculate the transition probability. Among the three algorithms, the Suwa–Todo algorithm yields the highest acceptance ratio and the shortest autocorrelation time. These suggest that sampling by a ST simulation with the Suwa–Todo algorithm is most efficient. In addition, because the acceptance ratio of the Suwa–Todo algorithm is higher than that of the Metropolis algorithm, the number of temperature states can be reduced by 25% for the Suwa–Todo algorithm when compared with the Metropolis algorithm. © 2015 Wiley Periodicals, Inc.     

Using bonding to guide transition state optimization

Optimization of a transition state typically requires both a good initial guess of the molecular structure and one or more computationally demanding Hessian calculations to converge reliably. Often, the transition state being optimized corresponds to the barrier in a chemical reaction where bonds are being broken and formed. Utilizing the geometries and bonding information for reactants and products, an algorithm is outlined to reliably interpolate an initial guess for the transition state geometry. Additionally, the change in bonding is also used to increase the reliability of transition state optimizations that utilize approximate and updated Hessian information. These methods are described and compared against standard transition state optimization methods. © 2015 Wiley Periodicals, Inc.     

Adaptive importance sampling Monte Carlo simulation of rare transition events

We develop a general theoretical framework for the recently proposed importance sampling method for enhancing the efficiency of rare-event simulations [W. Cai, M. H. Kalos, M. de Koning, and V. V. Bulatov, Phys. Rev. E 66, 046703 (2002)], and discuss practical aspects of its application. We define the success/fail ensemble of all possible successful and failed transition paths of any duration and demonstrate that in this formulation the rare-event problem can be interpreted as a "hit-or-miss" Monte Carlo quadrature calculation of a path integral. The fact that the integrand contributes significantly only for a very tiny fraction of all possible paths then naturally leads to a "standard" importance sampling approach to Monte Carlo (MC) quadrature and the existence of an optimal importance function. In addition to showing that the approach is general and expected to be applicable beyond the realm of Markovian path simulations, for which the method was originally proposed, the formulation reveals a conceptual analogy with the variational MC (VMC) method. The search for the optimal importance function in the former is analogous to finding the ground-state wave function in the latter. In two model problems we discuss practical aspects of finding a suitable approximation for the optimal importance function. For this purpose we follow the strategy that is typically adopted in VMC calculations: the selection of a trial functional form for the optimal importance function, followed by the optimization of its adjustable parameters. The latter is accomplished by means of an adaptive optimization procedure based on a combination of steepest-descent and genetic algorithms.     

Conformational transition pathway of polymerase beta/DNA upon binding correct incoming substrate

The closing conformational transition of wild-type polymerase beta bound to DNA template/primer before the chemical step (nucleotidyl transfer reaction) is simulated using the stochastic difference equation (in length version, "SDEL") algorithm that approximates long-time dynamics. The order of the events and the intermediate states during pol beta's closing pathway are identified and compared to a separate study of pol beta using transition path sampling (TPS) (Radhakrishnan, R.; Schlick, T. Proc. Natl. Acad. Sci. USA 2004, 101, 5970-5975). Results highlight the cooperative and subtle conformational changes in the pol beta active site upon binding the correct substrate that may help explain DNA replication and repair fidelity. These changes involve key residues that differentiate the open from the closed conformation (Asp192, Arg258, Phe272), as well as residues contacting the DNA template/primer strand near the active site (Tyr271, Arg283, Thr292, Tyr296) and residues contacting the beta and gamma phosphates of the incoming nucleotide (Ser180, Arg183, Gly189). This study compliments experimental observations by providing detailed atomistic views of the intermediates along the polymerase closing pathway and by suggesting additional key residues that regulate events prior to or during the chemical reaction. We also show general agreement between two sampling methods (the stochastic difference equation and transition path sampling) and identify methodological challenges involved in the former method relevant to large-scale biomolecular applications. Specifically, SDEL is very quick relative to TPS for obtaining an approximate path of medium resolution and providing qualitative information on the sequence of events; however, associated free energies are likely very costly to obtain because this will require both successful further refinement of the path segments close to the bottlenecks and large computational time.     

Atomistic in situ investigation of the morphogenesis of grains during pressure-induced phase transitions: molecular dynamics simulations of the B1-B2 transformation of RbCl

The mechanistic details of the pressure-induced B1-B2 phase transition of rubidium chloride are investigated in a series of transition path sampling molecular dynamics simulations. The B2→B1 transformation proceeds by nucleation and growth involving several, initially separated, nucleation centers. We show how independent and partially correlated nucleation events can function within a global mechanism and explore the evolution of phase domains during the transition. From this, the mechanisms of grain boundary formation are elaborated. The atomic structure of the domain-domain interfaces fully support the concept of Bernal polyhedra. Indeed, the manifold of different grain morphologies obtained from our simulations may be rationalized on the basis of essentially only two different kinds of Bernal polyhedra. The latter also play a crucial role for the B1→B2 transformation and specific grain boundary motifs are identified as preferred nucleation centers for this transition.     

Obtaining reaction coordinates by likelihood maximization

We present a new approach for calculating reaction coordinates in complex systems. The new method is based on transition path sampling and likelihood maximization. It requires fewer trajectories than a single iteration of existing procedures, and it applies to both low and high friction dynamics. The new method screens a set of candidate collective variables for a good reaction coordinate that depends on a few relevant variables. The Bayesian information criterion determines whether additional variables significantly improve the reaction coordinate. Additionally, we present an advantageous transition path sampling algorithm and an algorithm to generate the most likely transition path in the space of collective variables. The method is demonstrated on two systems: a bistable model potential energy surface and nucleation in the Ising model. For the Ising model of nucleation, we quantify for the first time the role of nuclei surface area in the nucleation reaction coordinate. Surprisingly, increased surface area increases the stability of nuclei in two dimensions but decreases nuclei stability in three dimensions.     

Generalized simulated tempering for exploring strong phase transitions

An extension of the simulation tempering algorithm is proposed. It is shown to be particularly suited to the exploration of first-order phase transition systems characterized by the backbending or S-loop in the statistical temperature or a microcanonical caloric curve. A guided Markov process in an auxiliary parameter space systematically combines a set of parametrized Tsallis-weight ensemble simulations, which are targeted to transform unstable or metastable energy states of canonical ensembles into stable ones and smoothly join ordered and disordered phases across phase transition regions via a succession of unimodal energy distributions. The inverse mapping between the sampling weight and the effective temperature enables an optimal selection of relevant Tsallis-weight parameters. A semianalytic expression for the biasing weight in parameter space is adaptively updated "on the fly" during the simulation to achieve rapid convergence. Accelerated tunneling transitions with a comprehensive sampling for phase-coexistent states are explicitly demonstrated in systems subject to strong hysteresis including Potts and Ising spin models and a 147 atom Lennard-Jones cluster.