Skip to Main content Skip to Navigation
Conference papers

Quadratic Programming Approach to Fit Protein Complexes into Electron Density Maps

Roman Pogodin 1, 2 Alexander Katrutsa 3, 1, 2 Sergei Grudinin 3
3 NANO-D - Algorithms for Modeling and Simulation of Nanosystems
Inria Grenoble - Rhône-Alpes, Grenoble INP - Institut polytechnique de Grenoble - Grenoble Institute of Technology, LJK - Laboratoire Jean Kuntzmann
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.
Complete list of metadata

Cited literature [21 references]  Display  Hide  Download
Contributor : Nano-D Equipe Connect in order to contact the contributor
Submitted on : Saturday, January 7, 2017 - 12:04:40 AM
Last modification on : Wednesday, December 1, 2021 - 2:36:21 PM
Long-term archiving on: : Saturday, April 8, 2017 - 12:07:02 PM


Files produced by the author(s)


Distributed under a Creative Commons Attribution - NonCommercial - NoDerivatives 4.0 International License


  • HAL Id : hal-01419380, version 2
  • ARXIV : 1701.02192



Roman Pogodin, Alexander Katrutsa, Sergei Grudinin. Quadratic Programming Approach to Fit Protein Complexes into Electron Density Maps. Information Technology and Systems 2016, Sep 2016, Repino, St. Petersburg, Russia. pp.576-582. ⟨hal-01419380v2⟩



Les métriques sont temporairement indisponibles