A Probabilistic Algorithm for Calculating Structure: Borrowing from Simulated Annealing
Russ Altman
Abstract:
We have developed a general Bayesian algorithm for determining the coordinates of points in a threedimensional 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 maximumlikelihood 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. Our method uses any probabilistic constraints that can be expressed as a function of the point coordinates (for example, distance, angles, dihedral angles, and planarity). It 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 ng molecular structure determination.
Keywords:
Pages: 2331
PS Link:
PDF Link: /papers/93/p23altman.pdf
BibTex:
@INPROCEEDINGS{Altman93,
AUTHOR = "Russ Altman
",
TITLE = "A Probabilistic Algorithm for Calculating Structure: Borrowing from Simulated Annealing",
BOOKTITLE = "Proceedings of the Ninth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI93)",
PUBLISHER = "Morgan Kaufmann",
ADDRESS = "San Francisco, CA",
YEAR = "1993",
PAGES = "2331"
}

