I understand from this active COVID-19 question: Are there any COVID-19 (coronavirus) related optimization problems with input datasets that we can "crowd solve"? that the protein folding problem is very important in the fight against COVID-19. When I look for OR studies about the problem, I reach the "Variable neighborhood search for graphical model energy minimization" article. "Computational Protein Design" problem is mentioned in the article. Also, there are MIP, LP and similar approaches for solving the protein design problem. The relation between folding and design is explained as "The protein folding problem has two components: the 'direct' folding problem (i.e. folding) and the ‘inverse’ problem (i.e. protein design)". I am looking for OR resources (starting point) for the problems (such as a book) and ideas about solvability of the problems from experienced researchers.
3 Answers
A good starting point is to look at the following Wikipedia resources:
- https://en.wikipedia.org/wiki/Protein_design
- https://en.wikibooks.org/wiki/Structural_Biochemistry/Proteins/Protein_Folding_Problem
The biochemistry problematic is described and the related mathematical optimization problems are discussed. Now, the state of the art on this topic can be found in this book. Note that an interesting discussion related to the topic can also be found on this forum.
Optimisation technology is practically irrelevant for protein folding because of the garbage-in garbage-out rule.
Our models for molecular interactions are simply so bad that solving Gibbs free energy models is pointless in practice (from an optimisation point of view).
Just to give you a bit more context about the state of the art, people are still struggling to model water properly (let alone very complex structures like proteins).
The underlying reason is that these models are only approximations to the interactions encoded into the Schroedinger equation, but the resulting modelling error makes de Novo based molecular design kind of pointless.
Until we can actually solve the Schroedinger equation at large scale (or somehow devise simple models that approximate it extremely well), discovery of new molecular compounds will be driven by experiments and empirical knowledge.
Protein folding calculations have been turned into QUBO (quadratic unconstrained binary optimization) in this paper where the goal was to run the calculations on a quantum annealer (in OR we are familiar with "simulated annealing", so think of quantum annealing as "real annealing" or "not just simulated" annealing).
The "objective function" for the optimization is in the first equation of the above paper: $$E({\bf s})=\sum h_is_i+\sum J_{ij}s_is_j\tag1$$ where $s_i\in\{0,1\}$ and $h_i$ and $J_{ij}$ are just real numbers: Basically you are just trying to minimize a quadratic function of binary variables, to get the lowest energy configuration of the protein.
Unfortunately there's better ways of solving the protein folding problem using molecular dynamics and other types of physics/chemistry simulations, than to convert the problem into QUBO and then solve the QUBO. This seems to be the case with all QUBO problems, as I have not yet found a case where converting problem "A" to QUBO form, then solving the QUBO, is better than just solving "A" in its original form without "forcing" yourself to use OR techniques via QUBO.
