Title: Quadratic Programming Approach to Fit Protein Complexes into Electron Density Maps,
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.