KSL-93-12
## 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.