Probabilistic Constraint Satisfaction with Non-Gaussian Noise

Russ B. Altman, Cheng C. Chen, William B. Poland, Jaswinder SinghUAI 1994 · DOI

Abstract

We have previously reported a Bayesian algorithm for determining the coordinates of points in three-dimensional space from uncertain constraints. This method is useful in the determination of biological molecular structure. It is limited, however, by the requirement that the uncertainty in the constraints be normally distributed. In this paper, we present an extension of the original algorithm that allows constraint uncertainty to be represented as a mixture of Gaussians, and thereby allows arbitrary constraint distributions. We illustrate the performance of this algorithm on a problem drawn from the domain of molecular structure determination, in which a multicomponent constraint representation produces a much more accurate solution than the old single component mechanism. The new mechanism uses mixture distributions to decompose the problem into a set of independent problems with unimodal constraint uncertainty. The results of the unimodal subproblems are periodically recombined using Bayes' law, to avoid combinatorial explosion. The new algorithm is particularly suited for parallel implementation.

Introduction: The Challenge of Non-Gaussian Noise

Determining the 3D arrangement of atoms in biological macromolecules, such as proteins, is a fundamental task in structural biology. This process relies on "constraints"—experimental data from techniques like NMR or biophysical theories—that provide estimates of distances between specific atoms.

However, this data is often inherently uncertain. Previous Bayesian approaches typically assumed that constraint uncertainty followed a unimodal Gaussian (normal) distribution. In practice, biological data is frequently multimodal; for instance, a theoretical model might indicate a distance is either 4Å or 8Å, but certainly not the average of 6Å. Representing such "non-Gaussian" noise with a single bell curve leads to significant inaccuracies. This research introduces a probabilistic framework capable of handling multimodal constraints without the computational burden of a combinatorial explosion.

Methodology: Branch and Recombine

The proposed algorithm extends a unimodal approach based on a modified Extended Kalman Filter by employing a Mixture of Gaussians (MoG) representation.

  1. Representation: The molecular structure is modeled as a vector of mean coordinates ($\mathbf{x}$) and a covariance matrix ($C(\mathbf{x})$) capturing the uncertainty and spatial relationships between atoms.
  2. Branching: When encountering a constraint with multiple possible values (components), the algorithm "branches" into parallel subproblems. Each branch independently processes one component of the mixture.
  3. Bayesian Recombination: To maintain computational feasibility, the algorithm periodically merges these branches. It applies Bayes' Law to calculate a posterior weight for each branch, effectively evaluating how well each path's structural estimate aligns with the observed data.
  4. Mixture Collapse: The weighted results are recombined into a single Gaussian estimate by matching the first and second moments, providing a unified starting point for subsequent constraints.
  5. Iterative Reheating: To prevent convergence to local minima, a "reheating" strategy is used, resetting the covariance matrix to allow the system to escape sub-optimal configurations.
The 'branch and recombine' strategy (right) compared to the standard unimodal iteration (left).

Experimental Setup

The algorithm was evaluated using a synthetic dataset based on a 21-atom fragment of the protein crambin. The authors generated exact inter-atomic distances and introduced "noise" by adding spurious Gaussian distributions with random means and variances. This setup simulates the complex, often contradictory data found in real-world structural determination.

Key Results and Structural Fidelity

The multicomponent algorithm demonstrated a substantial improvement in precision compared to the traditional unimodal method.

  • Accuracy: In experimental trials, the unimodal algorithm plateaued at an average error of 2.0 standard deviations (SD). In contrast, the multicomponent algorithm refined the same starting point to an error of just 0.07 SD.
  • Structural Convergence: The final models produced by the new method matched the known "gold standard" structure with a Root Mean Square Deviation (RMSD) between 0.002 Å and 0.09 Å. The unimodal version, by comparison, deviated by nearly 15 Å, failing to capture the correct fold.
  • Robustness to Spurious Data: The system proved resilient even when 50% of the constraints were intentionally "wrong" (where noise components outweighed the true signal). The Bayesian update process successfully identified and prioritized the correct data components over time.
Comparison of structural results: (left) initial atom uncertainty, (middle) the failed unimodal result, and (right) the accurate multicomponent reconstruction.

Discussion and Future Directions

A significant insight from this work is that the simpler unimodal algorithm serves as an effective "rough draft" generator, bringing the system within the radius of convergence for the more intensive multicomponent refinement.

While the "recombine" step prevents infinite branching, the "fan factor" still introduces more computational overhead than unimodal methods. However, because the branching phase creates independent subproblems, the algorithm is inherently parallelizable. Future work will focus on scaling this approach to full-scale macromolecules with thousands of atoms and implementing the algorithm on parallel computing architectures to handle the increased dimensionality.

Summary updated

Abstract

We have previously reported a Bayesian algorithm for determining the coordinates of points in three-dimensional space from uncertain constraints. This method is useful in the determination of biological molecular structure. It is limited, however, by the requirement that the uncertainty in the constraints be normally distributed. In this paper, we present an extension of the original algorithm that allows constraint uncertainty to be represented as a mixture of Gaussians, and thereby allows arbitrary constraint distributions. We illustrate the performance of this algorithm on a problem drawn from the domain of molecular structure determination, in which a multicomponent constraint representation produces a much more accurate solution than the old single component mechanism. The new mechanism uses mixture distributions to decompose the problem into a set of independent problems with unimodal constraint uncertainty. The results of the unimodal subproblems are periodically recombined using Bayes' law, to avoid combinatorial explosion. The new algorithm is particularly suited for parallel implementation.
BibTeX
@inproceedings{altman1994probabilistic,
  author = {Russ B. Altman and Cheng C. Chen and William B. Poland and Jaswinder Singh},
  title = {{Probabilistic Constraint Satisfaction with Non-Gaussian Noise}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {1994},
  doi = {10.48550/arxiv.1302.6780},
}
Figure