Dynamic weighting in Monte Carlo and optimization

Dynamic importance weighting is proposed as a Monte Carlo method that has the capability to sample relevant parts of the configuration space even in the presence of many steep energy minima. The method relies on an additional dynamic variable (the importance weight) to help the system overcome steep barriers. A non-Metropolis theory is developed for the construction of such weighted samplers. Algorithms based on this method are designed for simulation and global optimization tasks arising from multimodal sampling, neural network training, and the traveling salesman problem. Numerical tests on these problems confirm the effectiveness of the method.

Chaperonin-facilitated protein folding: optimization of rate and yield by an iterative annealing mechanism.

We develop a heuristic model for chaperonin-facilitated protein folding, the iterative annealing mechanism, based on theoretical descriptions of "rugged" conformational free energy landscapes for protein folding, and on experimental evidence that (i) folding proceeds by a nucleation mechanism whereby correct and incorrect nucleation lead to fast and slow folding kinetics, respectively, and (ii) chaperonins optimize the rate and yield of protein folding by an active ATP-dependent process. The chaperonins GroEL and GroES catalyze the folding of ribulose bisphosphate carboxylase at a rate proportional to the GroEL concentration. Kinetically trapped folding-incompetent conformers of ribulose bisphosphate carboxylase are converted to the native state in a reaction involving multiple rounds of quantized ATP hydrolysis by GroEL. We propose that chaperonins optimize protein folding by an iterative annealing mechanism; they repeatedly bind kinetically trapped conformers, randomly disrupt their structure, and release them in less folded states, allowing substrate proteins multiple opportunities to find pathways leading to the most thermodynamically stable state. By this mechanism, chaperonins greatly expand the range of environmental conditions in which folding to the native state is possible. We suggest that the development of this device for optimizing protein folding was an early and significant evolutionary event.

Optimization of rates of protein folding: the nucleation-condensation mechanism and its implications.

Small, single-module proteins that fold in a single cooperative step may be paradigms for understanding early events in protein-folding pathways generally. Recent experimental studies of the 64-residue chymotrypsin inhibitor 2 (CI2) support a nucleation mechanism for folding, as do some computer stimulations. CI2 has a nucleation site that develops only in the transition state for folding. The nucleus is composed of a set of adjacent residues (an alpha-helix), stabilized by long-range interactions that are formed as the rest of the protein collapses around it. A simple analysis of the optimization of the rate of protein folding predicts that rates are highest when the denatured state has little residual structure under physiological conditions and no intermediates accumulate. This implies that any potential nucleation site that is composed mainly of adjacent residues should be just weakly populated in the denatured state and become structured only in a high-energy intermediate or transition state when it is stabilized by interactions elsewhere in the protein. Hierarchical mechanisms of folding in which stable elements of structure accrete are unfavorable. The nucleation-condensation mechanism of CI2 fulfills the criteria for fast folding. On the other hand, stable intermediates do form in the folding of more complex proteins, and this may be an unavoidable consequence of increasing size and nucleation at more than one site.

Modeling and optimization of populations subject to time-dependent mutation.

It has become clear that many organisms possess the ability to regulate their mutation rate in response to environmental conditions. So the question of finding an optimal mutation rate must be replaced by that of finding an optimal mutation schedule. We show that this task cannot be accomplished with standard population-dynamic models. We then develop a "hybrid" model for populations experiencing time-dependent mutation that treats population growth as deterministic but the time of first appearance of new variants as stochastic. We show that the hybrid model agrees well with a Monte Carlo simulation. From this model, we derive a deterministic approximation, a "threshold" model, that is similar to standard population dynamic models but differs in the initial rate of generation of new mutants. We use these techniques to model antibody affinity maturation by somatic hypermutation. We had previously shown that the optimal mutation schedule for the deterministic threshold model is phasic, with periods of mutation between intervals of mutation-free growth. To establish the validity of this schedule, we now show that the phasic schedule that optimizes the deterministic threshold model significantly improves upon the best constant-rate schedule for the hybrid and Monte Carlo models.