A Probabilistic Algorithm for Calculating Structure: Borrowing from Simulated Annealing

Reference: Altman, R. A Probabilistic Algorithm for Calculating Structure: Borrowing from Simulated Annealing. Washington D.C., 1993.

Abstract: We have developed a general Bayesian algorithm for determining the coordinates of points in a three-dimensional space. The algorithm takes as input a set of probabilistic constraints on the coordinates of the points, and an a priori distribution for each point location. The output is a maximum likelihood estimate of the location of each point. We use the extended, iterated Kalman filter, and add a search heuristic for optimizing its solution under nonlinear conditions. This heuristic is based on the same principle as the simulated annealing heuristic for other optimization problems. Simply stated, we iteratively estimate the positions of the points using all available data; we allow the algorithm to leave local optima by resetting a variance- covariance matrix elements to high values. By increasing the variance of the elements, we allow unsatisfied (relatively low-variance) constraints to make large changes in the estimates of location, and thereby jump out of local optima. By iterating this process, we have been able to reliably identify sets of coordinates that satisfy the probabilistic constraints. Our method can use any probabilistic constraints that can be expressed as a general function of the point coordinates (e.g., distance, angles, dihedral angles, planarity etc...). It currently assumes that all constraints have gaussian noise. In this paper, we describe the algorithm and show its performance on a set of synthetic data to illustrate its convergence properties, and its applicability to domains such as molecular structure determination.

Notes: June 1993.

Full paper available as ps.

Jump to... [KSL] [SMI] [Reports by Author] [Reports by KSL Number] [Reports by Year]
Send mail to: ksl-info@ksl.stanford.edu to send a message to the maintainer of the KSL Reports.