Computational models of protein kinematics and dynamics: beyond simulation.

Physics-based simulation represents a powerful method for investigating the time-varying behavior of dynamic protein systems at high spatial and temporal resolution. Such simulations, however, can be prohibitively difficult or lengthy for large proteins or when probing the lower-resolution, long-timescale behaviors of proteins generally. Importantly, not all questions about a protein system require full space and time resolution to produce an informative answer. For instance, by avoiding the simulation of uncorrelated, high-frequency atomic movements, a larger, domain-level picture of protein dynamics can be revealed. The purpose of this review is to highlight the growing body of complementary work that goes beyond simulation. In particular, this review focuses on methods that address kinematics and dynamics, as well as those that address larger organizational questions and can quickly yield useful information about the long-timescale behavior of a protein.

Sampling-based exploration of folded state of a protein under kinematic and geometric constraints.

Flexibility is critical for a folded protein to bind to other molecules (ligands) and achieve its functions. The conformational selection theory suggests that a folded protein deforms continuously and its ligand selects the most favorable conformations to bind to. Therefore, one of the best options to study protein-ligand binding is to sample conformations broadly distributed over the protein-folded state. This article presents a new sampler, called kino-geometric sampler (KGS). This sampler encodes dominant energy terms implicitly by simple kinematic and geometric constraints. Two key technical contributions of KGS are (1) a robotics-inspired Jacobian-based method to simultaneously deform a large number of interdependent kinematic cycles without any significant break-up of the closure constraints, and (2) a diffusive strategy to generate conformation distributions that diffuse quickly throughout the protein folded state. Experiments on four very different test proteins demonstrate that KGS can efficiently compute distributions containing conformations close to target (e.g., functional) conformations. These targets are not given to KGS, hence are not used to bias the sampling process. In particular, for a lysine-binding protein, KGS was able to sample conformations in both the intermediate and functional states without the ligand, while previous work using molecular dynamics simulation had required the ligand to be taken into account in the potential function. Overall, KGS demonstrates that kino-geometric constraints characterize the folded subset of a protein conformation space and that this subset is small enough to be approximated by a relatively small distribution of conformations.

Learning probabilistic models of hydrogen bond stability from molecular dynamics simulation trajectories.

BACKGROUND: Hydrogen bonds (H-bonds) play a key role in both the formation and stabilization of protein structures. They form and break while a protein deforms, for instance during the transition from a non-functional to a functional state. The intrinsic strength of an individual H-bond has been studied from an energetic viewpoint, but energy alone may not be a very good predictor. METHODS: This paper describes inductive learning methods to train protein-independent probabilistic models of H-bond stability from molecular dynamics (MD) simulation trajectories of various proteins. The training data contains 32 input attributes (predictors) that describe an H-bond and its local environment in a conformation c and the output attribute is the probability that the H-bond will be present in an arbitrary conformation of this protein achievable from c within a time duration Δ. We model dependence of the output variable on the predictors by a regression tree. RESULTS: Several models are built using 6 MD simulation trajectories containing over 4000 distinct H-bonds (millions of occurrences). Experimental results demonstrate that such models can predict H-bond stability quite well. They perform roughly 20% better than models based on H-bond energy alone. In addition, they can accurately identify a large fraction of the least stable H-bonds in a conformation. In most tests, about 80% of the 10% H-bonds predicted as the least stable are actually among the 10% truly least stable. The important attributes identified during the tree construction are consistent with previous findings. CONCLUSIONS: We use inductive learning methods to build protein-independent probabilistic models to study H-bond stability, and demonstrate that the models perform better than H-bond energy alone.

Markov dynamic models for long-timescale protein motion.

Molecular dynamics (MD) simulation is a well-established method for studying protein motion at the atomic scale. However, it is computationally intensive and generates massive amounts of data. One way of addressing the dual challenges of computation efficiency and data analysis is to construct simplified models of long-timescale protein motion from MD simulation data. In this direction, we propose to use Markov models with hidden states, in which the Markovian states represent potentially overlapping probabilistic distributions over protein conformations. We also propose a principled criterion for evaluating the quality of a model by its ability to predict long-timescale protein motions. Our method was tested on 2D synthetic energy landscapes and two extensively studied peptides, alanine dipeptide and the villin headpiece subdomain (HP-35 NleNle). One interesting finding is that although a widely accepted model of alanine dipeptide contains six states, a simpler model with only three states is equally good for predicting long-timescale motions. We also used the constructed Markov models to estimate important kinetic and dynamic quantities for protein folding, in particular, mean first-passage time. The results are consistent with available experimental measurements.

Modeling discrete heterogeneity in X-ray diffraction data by fitting multi-conformers.

The native state of a protein is regarded to be an ensemble of conformers, which allows association with binding partners. While some of this structural heterogeneity is retained upon crystallization, reliably extracting heterogeneous features from diffraction data has remained a challenge. In this study, a new algorithm for the automatic modelling of discrete heterogeneity is presented. At high resolution, the authors' single multi-conformer model, with correlated structural features to represent heterogeneity, shows improved agreement with the diffraction data compared with a single-conformer model. The model appears to be representative of the set of structures present in the crystal. In contrast, below 2 A resolution representing ambiguous electron density by correlated multi-conformers in a single model does not yield better agreement with the experimental data. Consistent with previous studies, this suggests that variability in multi-conformer models at lower resolution levels reflects uncertainty more than coordinated motion.

Efficient algorithms to explore conformation spaces of flexible protein loops.

Several applications in biology - e.g., incorporation of protein flexibility in ligand docking algorithms, interpretation of fuzzy X-ray crystallographic data, and homology modeling - require computing the internal parameters of a flexible fragment (usually, a loop) of a protein in order to connect its termini to the rest of the protein without causing any steric clash. One must often sample many such conformations in order to explore and adequately represent the conformational range of the studied loop. While sampling must be fast, it is made difficult by the fact that two conflicting constraints - kinematic closure and clash avoidance - must be satisfied concurrently. This paper describes two efficient and complementary sampling algorithms to explore the space of closed clash-free conformations of a flexible protein loop. The "seed sampling" algorithm samples broadly from this space, while the "deformation sampling" algorithm uses seed conformations as starting points to explore the conformation space around them at a finer grain. Computational results are presented for various loops ranging from 5 to 25 residues. More specific results also show that the combination of the sampling algorithms with a functional site prediction software (FEATURE) makes it possible to compute and recognize calcium-binding loop conformations. The sampling algorithms are implemented in a toolkit (LoopTK), which is available at https://simtk.org/home/looptk.

Using stochastic roadmap simulation to predict experimental quantities in protein folding kinetics: folding rates and phi-values.

This paper presents a new method for studying protein folding kinetics. It uses the recently introduced Stochastic Roadmap Simulation (SRS) method to estimate the transition state ensemble (TSE) and predict the rates and the Phi-values for protein folding. The new method was tested on 16 proteins, whose rates and Phi-values have been determined experimentally. Comparison with experimental data shows that our method estimates the TSE much more accurately than an existing method based on dynamic programming. This improvement leads to better folding-rate predictions. We also compute the mean first passage time of the unfolded states and show that the computed values correlate with experimentally determined folding rates. The results on Phi-value predictions are mixed, possibly due to the simple energy model used in the tests. This is the first time that results obtained from SRS have been compared against a substantial amount of experimental data. The results further validate the SRS method and indicate its potential as a general tool for studying protein folding kinetics.

Real-space protein-model completion: an inverse-kinematics approach.

Rapid protein-structure determination relies greatly on software that can automatically build a protein model into an experimental electron-density map. In favorable circumstances, various software systems are capable of building over 90% of the final model. However, completeness falls off rapidly with the resolution of the diffraction data. Manual completion of these partial models is usually feasible, but is time-consuming and prone to subjective interpretation. Except for the N- and C-termini of the chain, the end points of each missing fragment are known from the initial model. Hence, fitting fragments reduces to an inverse-kinematics problem. A method has been developed that combines fast inverse-kinematics algorithms with a real-space torsion-angle refinement procedure in a two-stage approach to fit missing main-chain fragments into the electron density between two anchor points. The first stage samples a large number of closing conformations, guided by the electron density. These candidates are ranked according to density fit. In a subsequent refinement stage, optimization steps are projected onto a carefully chosen subspace of conformation space to preserve rigid geometry and closure. Experimental results show that fitted fragments are in excellent agreement with the final refined structure for lengths of up to 12-15 residues in areas of weak or ambiguous electron density, even at medium to low resolution.

Algorithm and data structures for efficient energy maintenance during Monte Carlo simulation of proteins.

Monte Carlo simulation (MCS) is a common methodology to compute pathways and thermodynamic properties of proteins. A simulation run is a series of random steps in conformation space, each perturbing some degrees of freedom of the molecule. A step is accepted with a probability that depends on the change in value of an energy function. Typical energy functions sum many terms. The most costly ones to compute are contributed by atom pairs closer than some cutoff distance. This paper introduces a new method that speeds up MCS by exploiting the facts that proteins are long kinematic chains and that few degrees of freedom are changed at each step. A novel data structure, called the ChainTree, captures both the kinematics and the shape of a protein at successive levels of detail. It is used to efficiently detect self-collision (steric clash between atoms) and/or find all atom pairs contributing to the energy. It also makes it possible to identify partial energy sums left unchanged by a perturbation, thus allowing the energy value to be incrementally updated. Computational tests on four proteins of sizes ranging from 68 to 755 amino acids show that MCS with the ChainTree method is significantly faster (as much as 10 times faster for the largest protein) than with the widely used grid method. They also indicate that speed-up increases with larger proteins.

Stochastic roadmap simulation: an efficient representation and algorithm for analyzing molecular motion.

Classic molecular motion simulation techniques, such as Monte Carlo (MC) simulation, generate motion pathways one at a time and spend most of their time in the local minima of the energy landscape defined over a molecular conformation space. Their high computational cost prevents them from being used to compute ensemble properties (properties requiring the analysis of many pathways). This paper introduces stochastic roadmap simulation (SRS) as a new computational approach for exploring the kinetics of molecular motion by simultaneously examining multiple pathways. These pathways are compactly encoded in a graph, which is constructed by sampling a molecular conformation space at random. This computation, which does not trace any particular pathway explicitly, circumvents the local-minima problem. Each edge in the graph represents a potential transition of the molecule and is associated with a probability indicating the likelihood of this transition. By viewing the graph as a Markov chain, ensemble properties can be efficiently computed over the entire molecular energy landscape. Furthermore, SRS converges to the same distribution as MC simulation. SRS is applied to two biological problems: computing the probability of folding, an important order parameter that measures the "kinetic distance" of a protein's conformation from its native state; and estimating the expected time to escape from a ligand-protein binding site. Comparison with MC simulations on protein folding shows that SRS produces arguably more accurate results, while reducing computation time by several orders of magnitude. Computational studies on ligand-protein binding also demonstrate SRS as a promising approach to study ligand-protein interactions.

Stochastic roadmap simulation for the study of ligand-protein interactions.

Understanding the dynamics of ligand-protein interactions is indispensable in the design of novel therapeutic agents. In this paper, we establish the use of Stochastic Roadmap Simulation (SRS) for the study of ligand-protein interactions through two studies. In our first study, we measure the effects of mutations on the catalytic site of a protein, a process called computational mutagenesis. In our second study, we focus on distinguishing the catalytic site from other putative binding sites. SRS compactly represents many Monte Carlo (MC) simulation paths in a compact graph structure, or roadmap. Furthermore, SRS allows us to analyze all the paths in this roadmap simultaneously. In our application of SRS to the domain of ligand-protein interactions, we consider a new parameter called escape time, the expected number of MC simulation steps required for the ligand to escape from the 'funnel of attraction' of the binding site, as a metric for analyzing such interactions. Although computing escape times would probably be infeasible with MC simulation, these computations can be performed very efficiently with SRS. Our results for six mutant complexes for the first study and seven ligand-protein complexes for the second study, are very promising: In particular, the first results agree well with the biological interpretation of the mutations, while the second results show that escape time is a good metric to distinguish the catalytic site for five out of seven complexes.

Using robotics to fold proteins and dock ligands.

The problems of protein folding and ligand docking have been explored largely using molecular dynamics or Monte Carlo methods. These methods are very compute intensive because they often explore a much wider range of energies, conformations and time than necessary. In addition, Monte Carlo methods often get trapped in local minima. We initially showed that robotic motion planning permitted one to determine the energy of binding and dissociation of ligands from protein binding sites (Singh et al., 1999). The robotic motion planning method maps complicated three-dimensional conformational states into a much simpler, but higher dimensional space in which conformational rearrangements can be represented as linear paths. The dimensionality of the conformation space is of the same order as the number of degrees of conformational freedom in three-dimensional space. We were able to determine the relative energy of association and dissociation of a ligand to a protein by calculating the energetics of interaction for a few thousand conformational states in the vicinity of the protein and choosing the best path from the roadmap. More recently, we have applied roadmap planning to the problem of protein folding (Apaydin et al., 2002a). We represented multiple conformations of a protein as nodes in a compact graph with the edges representing the probability of moving between neighboring states. Instead of using Monte Carlo simulation to simulate thousands of possible paths through various conformational states, we were able to use Markov methods to calculate the steady state occupancy of each conformation, needing to calculate the energy of each conformation only once. We referred to this Markov method of representing multiple conformations and transitions as stochastic roadmap simulation or SRS. We demonstrated that the distribution of conformational states calculated with exhaustive Monte Carlo simulations asymptotically approached the Markov steady state if the same Boltzman energy distribution was used in both methods. SRS permits one to calculate contributions from all possible paths simultaneously with far fewer energy calculations than Monte Carlo or molecular dynamics methods. The SRS method also permits one to represent multiple unfolded starting states and multiple, near-native, folded states and all possible paths between them simultaneously. The SRS method is also independent of the function used to calculate the energy of the various conformational states. In a paper to be presented at this conference (Apaydin et al., 2002b) we have also applied SRS to ligand docking in which we calculate the dynamics of ligand-protein association and dissociation in the region of various binding sites on a number of proteins. SRS permits us to determine the relative times of association to and dissociation from various catalytic and non-catalytic binding sites on protein surfaces. Instead of just following the best path in a roadmap, we can calculate the contribution of all the possible binding or dissociation paths and their relative probabilities and energies simultaneously.

Algorithmic tools for real-time microsurgery simulation.

Today, there is growing interest in computer surgical simulation to enhance surgeons' training. This paper presents a simulation system based on novel algorithms for animating instruments interacting with deformable tissue in real-time. The focus is on computing the deformation of a tissue subject to external forces, and detecting collisions among deformable and rigid objects. To achieve real-time performance, the algorithms take advantage of several characteristics of surgical training: (1) visual realism is more important than accurate, patient-specific simulation; (2) most tissue deformations are local; (3) human-body tissues are well damped; and (4) surgical instruments have relatively slow motions. Each key algorithm is described in detail and quantitative performance-evaluation results are given. The specific application considered in this paper is microsurgery, in which the user repairs a virtual severed blood vessel using forceps and a suture (micro-anastomosis). Microsurgery makes it possible to demonstrate several facets of the simulation algorithms, including the deformations of the blood vessel and the suture, and the collisions and interactions between the vessel, the forceps, and the suture. Validation of the overall microsurgery system is based on subjective analysis of the simulation's visual realism by different users.