Stochastic conformational roadmaps for computing ensemble properties of molecular motion

Abstract

A key intuition behind probabilistic roadmap planners for motion planning is that many collision-free paths potentially exist between two given robot configurations. Hence the connectivity of a robot's free space can be captured effectively by a network of randomly sampled configurations. In this paper, a similar intuition is exploited to preprocess molecular motion pathways and efficiently compute their ensemble properties, i.e., properties characterizing the average behavior of many pathways. We construct a directed graph, called stochastic conformational roadmap, whose nodes are randomly sampled molecule conformations. A roadmap compactly encodes many molecular motion pathways. Ensemble properties are computed by viewing the roadmap as a Markov chain. A salient feature of this new approach is that it examines all the paths in the roadmap simultaneously, rather than one at a time as classic methods such as Monte Carlo (MC) simulation would do. It also avoids the local-minima problem encountered by the classic methods. Tests of the approach on two important biological problems show that it produces more accurate results and achieves several orders of magnitude reduction in computation time, compared with MC simulation. © 2004 Springer-Verlag.