Interdisciplinary Initiatives Program Round 1 - 2000

Jean-Claude Latombe, Computer Science
Doug Brutlag, Biochemistry
Vijay Pande, Chemistry
Leonidas Guibas, Computer Science
Michael Levitt, Structural Biology

We introduce Sochastic Roadmap Simulation (SRS), a new approach for exploring the kinetics of molecular motion by examining multiple pathways in a graph, called a roadmap. A roadmap is generated by sampling the molecule’s conformational space at random and its computation does not suffer from the local-minimum problem encountered with other methods.

Every path in the roadmap represents a potential pathway and is associated with a probability indicating the likelyhood that the molecule follow this pathway. By viewing the roadmap as a Markov chain, we efficiently compute kinetic properties of molecular motion over the entire energy landscape of the molecule. We also prove that in the limit, SRS converges to the same distribution as Monte Carlo simulation.

To test the effectiveness of our approach, we have applied it to the computation of the transmission coefficient for protein folding, an important parameter that measures the “kinetic distance” of a protein’s conformation to the folded state. Our computational studies show that SRS achieves several orders-of-magnitude reduction in running time compared with a Monte Carlo method.