Convex Max-Product over Compact Sets for Protein Folding

Jian Peng, Tamir Hazan, David A. McAllester, Raquel UrtasunICML 2011 · OpenReview

Finding the minimum-energy configuration—or Maximum A Posteriori (MAP) estimation—in a graphical model is a fundamental problem in machine learning. Recently, "convex belief propagation" (BP) has emerged as a powerful way to solve this by optimizing a linear programming (LP) relaxation of the problem.

However, convex BP was originally designed for discrete variables. Applying it to continuous variables is mathematically awkward: if variables take on real numbers, the LP relaxation suddenly requires a continuum of variables, making it computationally intractable. This paper tackles this gap, extending convex BP to Markov Random Fields (MRFs) with continuous variables. The authors introduce a novel "particle convex max-product" algorithm that iteratively samples discrete points to approximate continuous spaces, and they apply it to the highly complex, continuous 3D spatial problem of protein folding.

Methods

The authors present three main contributions, moving from pure theory to a practical algorithm:

  1. Theoretical Foundation: They prove that strong duality holds for continuous, bounded variables with continuous potential functions. This means the optimal solution can theoretically be achieved using continuous functions rather than arbitrary ones.
  2. Interval Convex Max-Product (Theoretical Algorithm): They propose discretizing the continuous space into intervals, bounding the energy within each, and running discrete BP. The algorithm iteratively subdivides promising intervals. While provably convergent to the correct continuous value, it remains too computationally expensive for real-world use.
  3. Particle Convex Max-Product (Practical Algorithm): To solve the computational bottleneck, they introduce a particle-based approach. Instead of intervals, each continuous variable is represented by a discrete set of sampled points (particles). The algorithm alternates between two steps:
  4. Running discrete convex max-product on the current set of particles to find the optimal assignment.
  5. Resampling new particles in the continuous space centered around the optimal points found in the previous step.
Primal and dual convergence of the particle convex max-product algorithm across different particle counts (100, 200, and 1000 points).

Key Insights

  • Convexity is crucial for particle methods: Standard max-product algorithms are aggressive and tend to converge rapidly to poor local optima when used with particle resampling. Because convex max-product optimizes a lower bound, it is more conservative and stable, making it vastly superior for guiding the resampling of continuous variables.
  • Dynamic sampling beats static grids: A dynamic particle approach that iteratively hones in on good solutions vastly outperforms a static, fine-grained discretization of the continuous space, both in accuracy and computational speed.
  • Less is (sometimes) more in biology: The authors achieved highly competitive protein folding results using a remarkably simple energy function based only on distance constraints derived from template proteins. They ignored the massive list of physical and chemical constraints (like bond angles and atomic clashes) usually required by domain-specific solvers.

Key Results

The approach was evaluated on the task of protein structure prediction (predicting the 3D coordinates of $C_\alpha$ atoms in the protein backbone) using a dataset of 20 proteins ranging from 43 to 186 amino acids. Predictions were evaluated using the GDT-TS score, a standard metric that measures the percentage of correctly aligned amino acids compared to the ground-truth native structure.

  • Crushing standard particle methods: The proposed particle convex max-product significantly outperformed standard particle max-product. For example, on the protein 1fc2, the proposed method achieved a GDT-TS score of 67.8, compared to just 27.9 for the standard method.
  • Rivaling state-of-the-art: The algorithm performed comparably to MODELLER, a highly specialized, state-of-the-art protein folding tool. It actually beat MODELLER on 12 out of the 20 proteins tested.
  • Excelling on hard problems: Interestingly, the proposed method specifically outperformed MODELLER on the "harder" proteins in the dataset, suggesting that the convex BP approach is more robust to complex energy landscapes where traditional simulated annealing (used by MODELLER) might fail.
Comparison of GDT-TS scores and Primal Values demonstrating the superiority of the proposed approach over standard discrete convex BP and particle max-product.

The authors also found that the most efficient optimization strategy is to start with a small number of particles to quickly locate the general region of interest, and then increase the sample size in later iterations to fine-tune the exact continuous values.

Limitations and Future Work

While the slow "interval" method provides a provable lower bound on the minimal energy, the practical "particle" method is ultimately a local search technique and loses this strict theoretical guarantee. However, the authors suggest that the theoretically sound interval method could be made practical in the future by using variable-sized voxels (3D intervals) to improve efficiency. Furthermore, because the algorithm already rivals MODELLER using only simple distance constraints, incorporating actual physical and chemical constraints into their MRF model could push prediction accuracy even higher.

Summary updated

BibTeX
@inproceedings{peng2011convex,
  author = {Jian Peng and Tamir Hazan and David A. McAllester and Raquel Urtasun},
  title = {{Convex Max-Product over Compact Sets for Protein Folding}},
  booktitle = {International Conference on Machine Learning},
  year = {2011},
  url = {https://openreview.net/forum?id=B1WIGnbO-r},
}

Loading related content...

Figure