Quadratic Programming Approach to Fit Protein Complexes into Electron Density Maps

Roman Pogodin, Alexander Katrutsa, Sergei GrudininarXiv 2017 · DOI · arXiv

Abstract

This paper investigates the challenge of fitting protein complexes into high-resolution cryo-electron microscopy (cryoEM) density maps. The problem is modeled as a combinatorial optimization task over discrete states, which is known to be NP-hard. We introduce a quadratic programming (QP) framework to define the positions of all proteins within a complex. By converting density maps into overlapping matrices—which are generally indefinite and lead to non-convex optimization—we evaluate various convex relaxations and optimization techniques to determine which configurations best minimize the quadratic form.

Introduction

In structural biology, cryoEM allows researchers to visualize the "envelope" of large protein complexes. However, these maps are often at a lower resolution than the individual high-resolution protein structures that compose them. Fitting these components into the map is akin to a 3D jigsaw puzzle. Mathematically, if one has $m$ proteins and $N$ possible positions for each, the number of combinations is astronomical, making the problem NP-hard. Traditional methods often rely on computationally expensive genetic algorithms or exhaustive searches.

Methodology

The authors propose a Quadratic Programming (QP) framework with an objective function consisting of two primary components:

  1. The Quadratic Term (Overlapping Matrix $Q$): This term penalizes pairs of proteins that overlap or clash in 3D space.
  2. The Linear Term (Relevance Vector $b$): This rewards proteins for fitting well into the density map’s contour, utilizing Laplacian-filtered cross-correlation.

The goal is to find a binary vector $x$ that minimizes clashing while maximizing fit. Because the matrix $Q$ is indefinite, the problem is non-convex. The authors explored several strategies to address this:

  • Convex Relaxations: Spectrum Shift (adjusting eigenvalues) and Semidefinite Programming (SDP).
  • Continuous Optimization: Sequential Quadratic Programming (SQP), which treats variables as continuous before rounding to binary.
  • Stochastic Search: Simulated Annealing (SA) as a global search baseline.
  • Linear Approximation: A simplified model that ignores protein-protein overlaps entirely, focusing solely on the map fit.

Experimental Setup

The methods were evaluated using simulated 10 Å resolution maps generated from seven known protein complexes in the Protein Data Bank (PDB): 1e6v, 1gte, 1tyq, 1z5s, 2p4n, 4a6j, and 4bij. These simulated maps provided a "ground truth" to calculate the Root-Mean-Square Deviation (RMSD) and the Correct Answers Ratio ($\beta$).

Analysis and Insights

  • Contour Importance: Matching the edges (contours) of the density map using Laplacian filters proved more informative for positioning than matching total volume.
  • The Linear Surprise: The "Linear Approximation"—which ignores overlaps—often performed as well as or better than complex quadratic models. This suggests that the density map itself often provides sufficient unique information for correct placement.
  • Relaxation Failures: Standard convex relaxations like SDP and Spectrum Shift performed poorly. Shifting the spectrum to achieve convexity often distorted the problem so much that the solutions lost physical meaning.
  • Local Search Efficiency: SQP proved effective, particularly when initialized with the solution from the linear fit.

Key Results

Across all tested complexes, the Linear approach showed the highest average success rate, followed closely by SA and SQP. For specific complexes like 1gte, SQP and SA achieved a perfect correct answer ratio ($\beta = 1.00$) across all scoring types (Contact, CCF, Skin-Core, and Core-Skin).

Average performance of different optimization methods in terms of correct answers ratio.

As shown in the detailed breakdown below, the performance varies by complex, with 1e6v proving more challenging than 1gte or 1z5s for several methods.

Detailed performance metrics (correct answers ratio) for specific protein complexes across various scoring functions.

Conclusion

While the QP framework shows promise, particularly the Linear and SQP approaches, limitations remain. The study relied on simulated data, which lacks the noise and non-uniform resolution of real-world cryoEM maps. Additionally, the method assumes a set of predefined candidate positions is already available. Future work may explore more robust scoring functions, such as Mutual Information (MI), to handle higher noise levels and varying resolutions.

Summary updated

Abstract

The paper investigates the problem of fitting protein complexes into electron density maps. They are represented by high-resolution cryoEM density maps converted into overlapping matrices and partly show a structure of a complex. The general purpose is to define positions of all proteins inside it. This problem is known to be NP-hard, since it lays in the field of combinatorial optimization over a set of discrete states of the complex. We introduce quadratic programming approaches to the problem. To find an approximate solution, we convert a density map into an overlapping matrix, which is generally indefinite. Since the matrix is indefinite, the optimization problem for the corresponding quadratic form is non-convex. To treat non-convexity of the optimization problem, we use different convex relaxations to find which set of proteins minimizes the quadratic form best.
BibTeX
@misc{pogodin2017quadratic,
  author = {Roman Pogodin and Alexander Katrutsa and Sergei Grudinin},
  title = {{Quadratic Programming Approach to Fit Protein Complexes into Electron Density Maps}},
  year = {2017},
  eprint = {1701.02192},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1701.02192},
}
Figure