A replica exchange Monte Carlo algorithm for protein folding in the HP model

Background  

The ab initio protein folding problem consists of predicting protein tertiary structure from a given amino acid sequence by minimizing an energy function; it is one of the most important and challenging problems in biochemistry, molecular biology and biophysics. The ab initio protein folding problem is computationally challenging and has been shown to be -hard even when conformations are restricted to a lattice. In this work, we implement and evaluate the replica exchange Monte Carlo (REMC) method, which has already been applied very successfully to more complex protein models and other optimization problems with complex energy landscapes, in combination with the highly effective pull move neighbourhood in two widely studied Hydrophobic Polar (HP) lattice models.     

All-atom replica exchange molecular simulation of protein BBL

Downhill folding is one of the most important predictions of energy landscape theory. Recently, the Escherichia coli 2-oxoglutarate dehydrogenase PSBD was described as a first example of global downhill folding (Garcia-Mira et al., Science 2002;298:2191), classification that has been later subject of significant controversy. To help resolve this problem, by using intensive all-atom simulation with explicit water model and the replica exchange method, we sample the phase space of protein BBL and depict the free energy landscape. We give an estimate of the free energy barrier height of 1-2 k(B)T, dependent on the way the energy landscape is projected. We also study the conformational distribution of the transition region and find that the three helices generally take the similar positions as that in the native states whereas their spatial orientations show large variability. We further detect the inconsistency between different signals by individually fitting the thermal denaturation curves of five structural features using two-state model, which gives a wide spread melting temperature of 19 K. All of these features are consistent with a picture of folding with very low cooperativities. Compared with the experimental data (Sadqi et al., Nature 2006; 442:317), our results indicate that the Naf-BBL (pH5.3) may have an even lower barrier height and cooperativity.     

Folding time predictions from all-atom replica exchange simulations

We present an approach to predicting the folding time distribution from all-atom replica exchange simulations. This is accomplished by approximating the multidimensional folding process as stochastic reaction-coordinate dynamics for which effective drift velocities and diffusion coefficients are determined from the short-time replica exchange simulations. Our approach is applied to the folding of the second beta-hairpin of the B domain of protein G. The folding time prediction agrees quite well with experimental measurements. Therefore, we have in hand a fast numerical tool for calculating the folding kinetic properties from all-atom "first-principles" models.     

Molecular dynamics simulations using temperature-enhanced essential dynamics replica exchange

Today's standard molecular dynamics simulations of moderately sized biomolecular systems at full atomic resolution are typically limited to the nanosecond timescale and therefore suffer from limited conformational sampling. Efficient ensemble-preserving algorithms like replica exchange (REX) may alleviate this problem somewhat but are still computationally prohibitive due to the large number of degrees of freedom involved. Aiming at increased sampling efficiency, we present a novel simulation method combining the ideas of essential dynamics and REX. Unlike standard REX, in each replica only a selection of essential collective modes of a subsystem of interest (essential subspace) is coupled to a higher temperature, with the remainder of the system staying at a reference temperature, T(0). This selective excitation along with the replica framework permits efficient approximate ensemble-preserving conformational sampling and allows much larger temperature differences between replicas, thereby considerably enhancing sampling efficiency. Ensemble properties and sampling performance of the method are discussed using dialanine and guanylin test systems, with multi-microsecond molecular dynamics simulations of these test systems serving as references.     

Global optimisation by replica exchange with scaled hybrid Hamiltonians

A global optimisation scheme based on replica-exchange molecular dynamics simulation with scaled hybrid Hamiltonians is presented and applied to fold trpzip2 peptide from extended structures with explicit water model using only eight replicas. The algorithm is shown to be capable of reproducibly optimising the peptide to structures of root mean squared deviations less than 2.5 Å with respect to all heavy atoms of NMR models. Moreover, the large amount of structural data sampled in the optimisation process enables us to provide a possible folding mechanism. The transition state ensemble is characterised by a largely formed turn and a compact packing of tryptophan 2, 4 and 9. The tryptophan 2/11 pair is found to form at a very late stage of the folding process. The first (closest to the turn) and the fourth native backbone hydrogen bonds form earlier and a picture of strict zipping up of hydrogen bonds is not observed. It is demonstrated in the present study that this global optimisation method which integrates structure prediction with approximated conformational samplings may be of help to understand the folding puzzle.     

A fast algorithm for computing multilocus recombination

A fast algorithm for computing recombination is developed for model organisms with selection on haploids. Haplotype frequencies are transformed to marginal frequencies; random mating and recombination are computed; marginal frequencies are transformed back to haplotype frequencies. With L diallelic loci, this algorithm is theoretically a factor of a constant times (3/8)^L faster than standard computations with selection on diploids, and up to 16 recombining loci have been computed. This algorithm is then applied to model the opposing evolutionary forces of multilocus epistatic selection and recombination. Selection is assumed to favor haplotypes with specific alleles either all present or all absent. When the number of linked loci exceeds a critical value, a jump bifurcation occurs in the two-dimensional parameter space of the selection coefficient s and the recombination frequency r. The equilibrium solution jumps from high to low mean fitness with increasing r or decreasing s. These numerical results display an unexpected and dramatic nonlinear effect occurring in linkage models with a large number of loci.     

Ant colony based constrained workflow scheduling for heterogeneous computing systems

The problem of constrained workflow scheduling on heterogeneous computing systems has been of major interest in the recent years. The user requirements are described by defining constraints on the workflow makespan and/or its execution cost. The uncertainty in the activity execution path and the dynamicity in the resource workload may cause some run-time changes of the makespan or cost. To prohibit run-time constraint violation, the system needs robust schedules. In this paper, probability of violation (POV) of constraints is proposed as a criterion for the schedule robustness. An ant colony system is then used to minimize an aggregation of violation of constraints and the POV. Simulation results on real world workflows show the effectiveness of the proposed method in finding feasible schedules. The results also indicate that the proposed method decreases the POV, as well as the expected penalty at run-time.     

Folding mechanism of beta-hairpins studied by replica exchange molecular simulations

The folding process of trpzip2 beta-hairpin is studied by the replica exchange molecular dynamics (REMD) and normal MD simulations, aiming to understand the folding mechanism of this unique small, stable, and fast folder, as well as to reveal the general principles in the folding of beta-hairpins. According to our simulations, the TS ensemble is mainly characterized by a largely formed turn and the interaction between the inner pair of hydrophobic core residues. The folding is a zipping up of hydrogen bonds. However, the nascent turn has to be stabilized by the partially formed hydrophobic core to cross the TS. Thus our folding picture is in essence a blend of hydrogen bond-centric and hydrophobic core-centric mechanism. Our simulations provide a direct evidence for a very recent experiment (Du et al., Proc Natl Acad Sci USA 2004;101:15915-15920), which suggests that the turn formation is the rate-limiting step for beta-hairpin folding and the unfolding is mainly determined by the hydrophobic interactions. Besides, the relationship between hydrogen bond stabilities and their relative importance in folding are investigated. It is found that the hydrogen bonds with higher stabilities need not play more important roles in the folding process, and vice versa.     

Induced fit with replica exchange improves protein complex structure prediction

Despite the progress in prediction of protein complexes over the last decade, recent blind protein complex structure prediction challenges revealed limited success rates (less than 20% models with DockQ score > 0.4) on targets that exhibit significant conformational change upon binding. To overcome limitations in capturing backbone motions, we developed a new, aggressive sampling method that incorporates temperature replica exchange Monte Carlo (T-REMC) and conformational sampling techniques within docking protocols in Rosetta. Our method, ReplicaDock 2.0, mimics induced-fit mechanism of protein binding to sample backbone motions across putative interface residues on-the-fly, thereby recapitulating binding-partner induced conformational changes. Furthermore, ReplicaDock 2.0 clocks in at 150-500 CPU hours per target (protein-size dependent); a runtime that is significantly faster than Molecular Dynamics based approaches. For a benchmark set of 88 proteins with moderate to high flexibility (unbound-to-bound iRMSD over 1.2 Å), ReplicaDock 2.0 successfully docks 61% of moderately flexible complexes and 35% of highly flexible complexes. Additionally, we demonstrate that by biasing backbone sampling particularly towards residues comprising flexible loops or hinge domains, highly flexible targets can be predicted to under 2 Å accuracy. This indicates that additional gains are possible when mobile protein segments are known.     

Energy-aware task scheduling in heterogeneous computing environments

Efficient application scheduling is critical for achieving high performance in heterogeneous computing (HC) environments. Because of such importance, there are many researches on this problem and various algorithms have been proposed. Duplication-based algorithms are one kind of well known algorithms to solve scheduling problems, which achieve high performance on minimizing the overall completion time (makespan) of applications. However, they pursuit of the shortest makespan overly by duplicating some tasks redundantly, which leads to a large amount of energy consumption and resource waste. With the growing advocacy for green computing systems, energy conservation has been an important issue and gained a particular interest. An existing technique to reduce energy consumption of an application is dynamic voltage/frequency scaling (DVFS), whose efficiency is affected by the overhead of time and energy caused by voltage scaling. In this paper, we propose a new energy-aware scheduling algorithm with reduced task duplication called Energy-Aware Scheduling by Minimizing Duplication (EAMD), which takes the energy consumption as well as the makespan of an application into consideration. It adopts a subtle energy-aware method to search and delete redundant task copies in the schedules generated by duplication-based algorithms, and it is easier to operate than DVFS, and produces no extra time and energy consumption. This algorithm not only consumes less energy but also maintains good performance in terms of makespan compared with duplication-based algorithms. Two kinds of DAGs, i.e., randomly generated graphs and two real-world application graphs, are tested in our experiments. Experimental results show that EAMD can save up to 15.59 % energy consumption for HLD and HCPFD, two classic duplication-based algorithms. Several factors affecting the performance are also analyzed in the paper.     

Ab initio folding simulation of Trpcage by replica exchange with hybrid Hamiltonian

Replica-exchange molecular dynamics simulations with hybrid Hamiltonian in explicit solvent were performed to study the folding of a designed 20-residue miniprotein, Trpcage, from a fully extended structure. During the simulations several folding/unfolding events happened. In the folded states the majority of experimentally observed NMR NOE restraints are satisfied. The folded structures have root mean squared deviation of 2.0 A with respect to the NMR structures considering all heavy atoms. The free-energy surface constructed by the hybrid Hamiltonian simulations is similar to the one built by a standard replica-exchange simulation which started from the native structure. Consistent with previous experimental observation, a pre-existing hydrophobic collapse in the unfolded state is detected by investigating the desolvation behavior of Trpcage. At room temperature, an intermediate state featured by a misfolded core, a nearly formed alpha-helix segment and an absence of 3(10)-helix is found. The replica exchange with hybrid Hamiltonian method is shown here to be capable of resolving the folding picture of the miniprotein.     

Simulating force-induced conformational transitions in polysaccharides with the SMD replica exchange method

Conventional steered molecular dynamics (SMD) simulations do not readily reproduce equilibrium conditions of atomic force microscopy (AFM) stretch and release measurements of polysaccharides undergoing force-induced conformational transitions because of the gap between the timescales of computer simulations ( approximately 1 mus) and AFM measurements ( approximately 1 s). To circumvent this limitation, we propose using the replica exchange method (REM) to enhance sampling during SMD simulations. By applying REM SMD to a small polysaccharide system and comparing the results with those from AFM stretching experiments, we demonstrate that REM SMD reproduces the experimental results not only qualitatively but quantitatively, approaching near equilibrium conditions of AFM measurements. As tested in this work, hysteresis and computational time of REM SMD simulations of short polysaccharide chains are significantly reduced as compared to regular SMD simulations, making REM SMD an attractive tool for studying forced-induced conformational transitions of small biopolymer systems.     

Solution study of engineered quartz binding peptides using replica exchange molecular dynamics

We use replica-exchange molecular dynamics (REMD) to interrogate molecular structures and properties of four engineered dodecapeptides (in solution, in the absence of a surface) that have been shown to bind to quartz with different propensities. We find that all of the strong-binding peptides feature some polyproline type II secondary structure, have less conformational freedom, and feature fewer intrapeptide hydrogen bonds compared with the weak binder. The regions of contiguous proline content in a given sequence appear to play a role in fostering some of these properties of the strong binders. For preliminary insights into quartz binding, we perform lattice-matching studies between a grid corresponding with the quartz (100) surface and the strong-binding peptide REMD structures. Our findings indicate a commonality among the putative contact residues, even for peptide structures with very different backbone conformations. Furthermore, interpeptide interactions in solution are studied. Our preliminary findings indicate that the strong-binder interpeptide contacts are dominated by weak, nonspecific hydrophobic interactions, while the weak-binding peptide shows more variable behavior due to the distribution of charged residues. In summary, the solution structures of peptides appear to be significant. We propose that these differences in their intra- and interpeptide interactions can influence their propensity to bind onto a solid substrate.     

Managing performance and power consumption tradeoff for multiple heterogeneous servers in cloud computing

There are typically multiple heterogeneous servers providing various services in cloud computing. High power consumption of these servers increases the cost of running a data center. Thus, there is a problem of reducing the power cost with tolerable performance degradation. In this paper, we optimize the performance and power consumption tradeoff for multiple heterogeneous servers. We consider the following problems: (1) optimal job scheduling with fixed service rates; (2) joint optimal service speed scaling and job scheduling. For problem (1), we present the Karush-Kuhn-Tucker (KKT) conditions and provide a closed-form solution. For problem (2), both continuous speed scaling and discrete speed scaling are considered. In discrete speed scaling, the feasible service rates are discrete and bounded. We formulate the problem as an MINLP problem and propose a distributed algorithm by online value iteration, which has lower complexity than a centralized algorithm. Our approach provides an analytical way to manage the tradeoff between performance and power consumption. The simulation results show the gain of using speed scaling, and also prove the effectiveness and efficiency of the proposed algorithms.     

Interaction mechanism of insulin with ZnO nanoparticles by replica exchange molecular dynamics simulation

The interaction of ZnO nanoparticles with biological molecules such as proteins is one of the most important and challenging problems in molecular biology. Molecular dynamics (MD) simulations are useful technique for understating the mechanism of various interactions of proteins and nanoparticles. In the present work, the interaction mechanism of insulin with ZnO nanoparticles was studied. Simulation methods including MD and replica exchange molecular dynamics (REMD) and their conditions were surveyed. According to the results obtained by REMD simulation, it was found that insulin interacts with ZnO nanoparticle surface via its polar and charged amino acids. Unfolding insulin at ZnO nanoparticle surface, the terminal parts of its chains play the main role. Due to the linkage between chain of insulin and chain of disulfide bonds, opposite directional movements of N terminal part of chain A (toward nanoparticle surface) and N termini of chain B (toward solution) make insulin unfolding. In unfolding of insulin at this condition, its helix structures convert to random coils at terminal parts chains.     

Structure of Met-enkephalin in explicit aqueous solution using replica exchange molecular dynamics.

Replica exchange molecular dynamics (MD) simulations of Met-enkephalin in explicit solvent reveal helical and nonhelical structures. Four predominant structures of Met-enkephalin are sampled with comparable probabilities (two helical and two nonhelical). The energy barriers between these configurations are low, suggesting that Met-enkephalin switches easily between configurations. This is consistent with the requirement that Met-enkephalin be sufficiently flexible to bind to several different receptors. Replica exchange simulations of 32 ns are shown to sample approximately five times more configurational space than constant temperature MD simulations of the same duration. The energy landscape for the replica exchange simulation is presented. A detailed study of replica trajectories demonstrates that the significant increases in temperature provided by the replica exchange technique enable transitions from nonhelical to helical structures that would otherwise be prevented by kinetic trapping. Met-enkephalin (Type Entrez Proteins; Value A61445; Service Entrez Proteins).     

A fast algorithm for computing geodesic distances in tree space

Comparing and computing distances between phylogenetic trees are important biological problems, especially for models where edge lengths play an important role. The geodesic distance measure between two phylogenetic trees with edge lengths is the length of the shortest path between them in the continuous tree space introduced by Billera, Holmes, and Vogtmann. This tree space provides a powerful tool for studying and comparing phylogenetic trees, both in exhibiting a natural distance measure and in providing a euclidean-like structure for solving optimization problems on trees. An important open problem is to find a polynomial time algorithm for finding geodesics in tree space. This paper gives such an algorithm, which starts with a simple initial path and moves through a series of successively shorter paths until the geodesic is attained.     

'Extremotaxis': computing with a bacterial-inspired algorithm

We present a general-purpose optimization algorithm inspired by "run-and-tumble", the biased random walk chemotactic swimming strategy used by the bacterium Escherichia coli to locate regions of high nutrient concentration The method uses particles (corresponding to bacteria) that swim through the variable space (corresponding to the attractant concentration profile). By constantly performing temporal comparisons, the particles drift towards the minimum or maximum of the function of interest. We illustrate the use of our method with four examples. We also present a discrete version of the algorithm. The new algorithm is expected to be useful in combinatorial optimization problems involving many variables, where the functional landscape is apparently stochastic and has local minima, but preserves some derivative structure at intermediate scales.     

Study of the aggregation mechanism of polyglutamine peptides using replica exchange molecular dynamics simulations

Polyglutamine (polyQ, a peptide) with an abnormal repeat length is the causative agent of polyQ diseases, such as Huntington’s disease. Although glutamine is a polar residue, polyQ peptides form insoluble aggregates in water, and the mechanism for this aggregation is still unclear. To elucidate the detailed mechanism for the nucleation and aggregation of polyQ peptides, replica exchange molecular dynamics simulations were performed for monomers and dimers of polyQ peptides with several chain lengths. Furthermore, to determine how the aggregation mechanism of polyQ differs from those of other peptides, we compared the results for polyQ with those of polyasparagine and polyleucine. The energy barrier between the monomeric and dimeric states of polyQ was found to be relatively low, and it was observed that polyQ dimers strongly favor the formation of antiparallel β-sheet structures. We also found a characteristic behavior of the monomeric polyQ peptide: a turn at the eighth residue is always present, even when the chain length is varied. We previously showed that a structure including more than two sets of β-turns is stable, so a long monomeric polyQ chain can act as an aggregation nucleus by forming several pairs of antiparallel β-sheet structures within a single chain. Since the aggregation of polyQ peptides has some features in common with an amyloid fibril, our results shed light on the mechanism for the aggregation of polyQ peptides as well as the mechanism for the formation of general amyloid fibrils, which cause the onset of amyloid diseases.     

Simulated annealing coupled replica exchange molecular dynamics—An efficient conformational sampling method

Molecular dynamics simulated annealing (SA-MD) simulations are frequently used for refinement and optimization of peptide and protein structures. Depending on the simulation conditions and simulation length SA-MD simulations can be trapped in locally stable conformations far from the global optimum. As an alternative replica exchange molecular dynamics (RexMD) simulations can be used which allow exchanges between high and low simulation temperatures at all stages of the simulation. A significant drawback of RexMD simulations is, however, the rapid increase of the replica number with increasing system size to cover a desired temperature range. A combined SA-MD and RexMD approach termed SA-RexMD is suggested that employs a small number of replicas (4) and starts initially with a set of high simulation temperatures followed by gradual cooling of the set of temperatures until a target temperature has been reached. The protocol has been applied for the folding of several peptide systems and for the refinement of protein model structures. In all the cases, the SA-RexMD method turned out to be significantly more efficient in reaching low energy structures and also structures close to experiment compared to continuous MD simulations at the target temperature and to SA-MD simulations at the same computational demand. The approach is well suited for applications in structure refinement and for systematic force field improvement.