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 metadatas

Cited literature [21 references]  Display  Hide  Download

https://hal.inria.fr/hal-01419380
Contributor : Nano-D Equipe <>
Submitted on : Saturday, January 7, 2017 - 12:04:40 AM
Last modification on : Tuesday, November 24, 2020 - 5:04:04 PM
Long-term archiving on: : Saturday, April 8, 2017 - 12:07:02 PM

Files

itas.pdf
Files produced by the author(s)

Licence


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

Identifiers

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

Collections

Citation

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⟩

Share

Metrics

Record views

2572

Files downloads

531