]> 2012-02-11T05:52:10-05:00 A Probabilistic Algorithm for Calculating Structure: Borrowing from Simulated Annealing 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. techreport 1993 A Probabilistic Algorithm for Calculating Structure: Borrowing from Simulated Annealing KSL-93-12 1993 June 1993. A Probabilistic Algorithm for Calculating Structure: Borrowing from Simulated Annealing 1993 Year Title YES Process note Number Note Ksl tr id Knowledge Systems, AI Laboratory Institution Has year Has where published Has title Has publishing details Has identifier Has author Bibtype Russ B. Altman Author Washington D.C. Address Abstract KSL Technical Report Publication Technical Report