0.8 Motion planning for proteins: biophysics and applications  (Page 6/10)

Once the roadmap is computed, the shortest paths between structures can be found using Djikstra's algorithm, and the folding paths can be extracted and studied. In particular, the order of secondary structure formation can be predicted by a consensus method. The order of secondary structure formation is determined for all paths in the roadmap from unfolded to folded structures, and the most common order is predicted as the true order of formation, which is a coarse, high-level expression of the folding mechanism. On a set of proteins used to test their method, the predicted formation order matched laboratory-determined formation order in all cases where it was available. Because of the coarseness of this notion of the folding mechanism, a statistical analysis of all pathways makes sense.

In their most recent work , these researchers have refined the method by which new structures are generated in the sampling phase of roadmap construction. This method is based on rigidity analysis . For each structure, each degree of freedom is determined to be independently flexible, dependently flexible, or rigid, using an algorithm called the Pebble Game . Independently flexible degrees of freedom rotate with no deterministic effect on others. Dependently flexible degrees of freedom force other degrees of freedom to change in a set way. Rigid degrees of freedom are essentially locked in place unless the constraints change. In perturbing an existing structure to generate a new sample, degrees of freedom are perturbed with a strong bias towards perturbing independently flexible degrees of freedom and against perturbing rigid degrees of freedom. Because the new structures are generated by physically realistic motions, it is expected that they will generally be lower energy and more representative of real structures than if they were generated by completely random perturbation of the degrees of freedom.

In practice, rigidity sampling appears to allow construction of high-quality roadmaps with many fewer samples than were necessary without it. It thus improves the overall efficiency of calculating protein behavior using this roadmap method.

Stochastic roadmap simulations

Numerous variants of MD and MC have been developed in an effort to speed up the process or focus the simulations on particular motions of interest. One method, called the Stochastic Roadmap Simulation (SRS) uses a PRM-like structure to approximate a large number of simultaneous MC simulations very rapidly, allowing the analysis of an ensemble of trajectories. This method followed very directly from the first roadmap studies of molecular properties by Singh and Latombe.

The SRS method proceeds as follows:

• N samples are made uniformly at random by selection of a random value for each dihedral angle.
• The k nearest neighbors for each sample are found.
• For each sample, a transition probability is calculated to each of its nearest neighbors, depending on their energy difference as follows:
  The energy, E, in this method is based on the hydrophobic-polar (H-P) energy model, and includes two terms, one favoring hydrophobic interactions, and the other depending on the solvent-excluded volume. Note the difference between the transition probabilities calculated by this method and those calculated by the method presented in the previous section. These probabilities depend only on the energies of the endpoints of an edge, whereas those of the other method depend on the energy along the path between the endpoints. The probabilities of the SRS method are faster to calculate, and, assuming that the system is at equilibrium, more likely to be consistent with the actual distribution of conformations.
• Each sample is given a self-transition probability as follows, so that the sum of outgoing edge probabilities for each node is 1: