Select Lab Publications


Stochastic Roadmap Simulation: An Efficient Representation and Algorithm for Analyzing Molecular Motion (2002)

By: M. Serkan Apaydin, Douglas L. Brutlag, Carlos Guestrin, David Hsu, and Jean-Claude Latombe

Abstract: Classic techniques for simulating molecular motion, such as Monte Carlo method and molecular dynamics, generate individual motion pathways one at a time and are inefficient if applied in a naive fashion to deal with many pathways. In this paper, we introduce stochastic roadmap simulation (SRS), a new approach for exploring the kinetics of molecular motion by examining multiple pathways simultaneously. In SRS, we compactly encode many pathways in a graph, called a roadmap. Every path in the roadmap represents a potential motion pathway and is associated with a probability indicating the likelihood that a molecule may follow the path. By viewing the roadmap as a Markov chain, we can efficiently compute kinetic properties of molecular motion over the entire energy landscape. Furthermore we prove that in the limit, SRS converges to the same distribution as Monte Carlo simulation. To test the effectiveness of our method, we applied it in the computation of the transmission coefficient for protein folding, which is an important order parameter that measures the ``kinetic distance'' of a conformation to the folded state of a protein. Our computational studies demonstrate that compared with Monte Carlo method, SRS obtains more accurate results and achieves several orders-of-magnitude reduction in running time.



Download Information
M. Serkan Apaydin, Douglas L. Brutlag, Carlos Guestrin, David Hsu, and Jean-Claude Latombe (2002). "Stochastic Roadmap Simulation: An Efficient Representation and Algorithm for Analyzing Molecular Motion." Sixth Annual International Conference on Research in Computational Molecular Biology (RECOMB) (pp. 12-21). Project page. pdf            
BibTeX citation

@inproceedings{Apaydin+al:recomb2002roadmap,
author = {M. Serkan Apaydin and Douglas L. Brutlag and Carlos Guestrin and David Hsu and Jean-Claude Latombe},
title = {Stochastic Roadmap Simulation: An Efficient Representation and Algorithm for Analyzing Molecular Motion},
booktitle = {Sixth Annual International Conference on Research in Computational Molecular Biology (RECOMB)},
pages = {12-21},
year = {2002},
address = {Washington, DC},
month = {April},
note = {Project page},
wwwfilebase = {recomb2002-apaydin-brutlag-guestrin-hsu-latombe},
wwwtopic = {Computational Biology}
}



full list