5 ms·

Honest question: since AlphaFold doesn't really _solve_ the protein folding problem (it's NP-complete after all), but only _approximates_ solutions very well, w

by Cas9 5y ago

Honest question: since AlphaFold doesn't really _solve_ the protein folding problem (it's NP-complete after all), but only _approximates_ solutions very well, what are the real impacts of this? Isn't a good approximation of a protein enough to cause unexpected problems? How do we know that an approximate structure will perform the same as the correct solution?

radus 5y ago
Yes, it is still useful. Even structures obtained through traditional means (eg. x-ray crystallography) are approximations to an extent since there are limits to the resolution that you can obtain and oftentimes regions of proteins are "disordered". Additionally, these structures are only snapshots of a protein in a particular state, which may not completely reflect the dynamics of the protein in its native environment.
whimsicalism 5y ago
You want to find a protein that has X structure (since structure determines function to a degree). If AlphaFold is substantially more accurate at solving proteins, it can mean that drug discovery is faster, assays are faster, etc. etc. The "unexpected problems" would be caught in the assay stage.
- radus 5y ago
  Kind of disagree with this.. solving protein structures is not the rate limiting step in drug discovery or in biochemical assays -- not by a long shot. See this excellent comment by @dekhn on a related submission: https://news.ycombinator.com/item?id=27849046 https://news.ycombinator.com/item?id=27849046
dekhn 5y ago
The protein folding problem is not NP complete. The "formal" protein folding problem, as posed (find the set of dihedral angles whose resulting structure has the lowest energy) might be, but that bears only a distant resemblance to how people "solve" the problem today. At the very least, the statement is incorrect because many proteins don't actually fold to their energy minimum, they get stuck in kinetic traps, and the formal PF defintion never accomodated that idea.
bawolff 5y ago
I dont know much about protein folding, but for most things in life,exact solutions to NPC problems usually aren't needed for non-contrived problems. In many cases, approximations are good enough. Besides, this is real life - if predictions and real life match, that's great. If they don't, well you know you went wrong somewhere.
- jerven 5y ago
  I would upvote this twice if I could. Life science quite often NP-hard still approximate results are extremely useful. Joke, which I think is from Sean Eddy (hammer). Bioinformatics approaches a Computer Scientist for help with a hard problem. CS agrees to help. Year later CS comes back very excitedly. "your problem is not hard it is NP-hard!". Bioinformatics nods, and says "I still got to solve it" and continues finding ever faster and better approximations ;) Also problem space is both bounded (you don't have infinite length proteins) and f'd up in reality. e.g protein hijacking and re-conformation in the face of an infectious agent.
wpasc 5y ago
A very-non-expert opinion, if an approach approximates it pretty well and can be improved upon, then it could end up being quite useful. Given that biology exists on a real, tangible scale then perfection in the fold prediction isn't necessary, instead just an approximation that is sufficiently good to be functionally useful. ^ That sounds like word-salad BS but I think there's some truth to it. I know protein folding has been postulated to be useful in terms of understanding basic biology, understanding disease pathology, and drug prediction. While a wide range of approximations are functionally useless, perhaps the Alphafold approach or some improved version of it surpasses the functionally useful threshold. At least I hope so
ashtonbaker 5y ago
Not really an answer to your question, but is the problem really NP-complete, or just combinatorially difficult? For example how is this condition of NP-completeness satisfied? > it is a problem for which the correctness of each solution can be verified quickly [0] [0] https://en.wikipedia.org/wiki/NP-completeness https://en.wikipedia.org/wiki/NP-completeness
- Cas9 5y ago
  According to this answer[0] it seems it's actually NP-Hard, my bad. Haven't seen the proof though, and I'm not an expert. [0] https://cs.stackexchange.com/questions/128493/is-protein-folding-really-np-hard-and-how-to-show-that https://cs.stackexchange.com/questions/128493/is-protein-fol...
mrfusion 5y ago
Is it really np complete? If so we could map other np complete problems onto it and let biology solve it for us.
nmca 5y ago
NP completeness tells you about the hardest cases, not the most useful cases.
hobofan 5y ago
I would expect that once AlphaFold has helped you identify a potential protein (e.g. as a drug) out of a bigger set of potential proteins, there will still be a manual step of traditional cryoEM, NMR, etc. to get an accurate high-resolution structure.
t_serpico 5y ago
To me, the interesting thing is not the specific results but rather that you can accurately predict crystal structures from sequence alone. This begets the question: what other physical biological properties can we predict?
thxg 5y ago
> (it's NP-complete after all) Protein folding is a physical/biological phenomenon. AFAIK we don't currently have a proper exact mathematical formulation of the problem that would let one determine its complexity. You may be referring to this paper [1]. It only claims that one particular optimization problem, believed to give a solution to protein folding problems, is NP-hard. So, even if a suitable exact formulation exists, it is not yet proven that protein folding is hard, although it for sure seems plausible. By the way, it is perfectly possible today to solve some very large-scale NP-hard problems (think millions of variables and constraints) in reasonable amounts of time (think minutes or hours). Examples are knapsack problems, SAT problems [2], the Traveling Salesman Problem [3] or more generally Mixed Integer Programming [4]. [1] "Complexity of protein folding", 1993, by Aviezri S. Fraenkel [2] http://www.satcompetition.org http://www.satcompetition.org [3] http://www.math.uwaterloo.ca/tsp/ http://www.math.uwaterloo.ca/tsp/ [4] http://plato.asu.edu/bench.html http://plato.asu.edu/bench.html
saithound 5y ago
AlphaFold is not about solving any kind of NP-complete problem. Proteins consist of chains of amino acids which spontaneously fold up to form a structure. Understanding how the amino acid chain determines the protein structure is highly challenging, and this is called the "protein folding problem". People use mathematical models to predict how proteins fold in nature. Many such mathematical models are stated in terms such as "proteins fold into a configuration that minimizes a certain energy function". Even the simplest such models [1] give rise to NP-hard decision problems, which are also known (somewhat confusingly) as "protein folding problems". To make this a bit less confusing, I will call the mathematical decision problems PFPs. Like all mathematical models, our protein folding models don't correspond exactly to reality. Even if you are somehow able to determine the exact mathematical solution to a mathematical PFP, that _still_ doesn't guarantee that the real protein that you were trying to model behaves like the mathematical solution would indicate. E.g. the protein may fold in such a way that it gets stuck in a local optimum of the energy function you were using. How do we detect this? We make inferences about how the protein should behave, given the mathematical solution to the Protein Folding Problem, and then we perform experiments, and find out (empirically) that the protein behaves in a manner that is inconsistent with the inferences drawn from the mathematical model. Scientists _do_ do this. And they would have to do it even if they had a fast, exact way to solve NP-complete problems, because the NP-complete problems are still just part of a mathematical model, and need not correspond to reality in any way. The success of AlphaFold is not measured by how well it solves (or approximates) mathematical PFPs. The success of AlphaFold is measured by making successful predictions about how certain proteins will fold. And this is exactly how it was tested [2]: they threw it at a bunch of problems for which scientists have empirically determined how certain amino acid chains fold, but didn't release the results. And then they compared the solutions predicted by AlphaFold, and found that most of the predictions were consistent with what they knew to be the case.* [1] https://en.wikipedia.org/wiki/Lattice_protein https://en.wikipedia.org/wiki/Lattice_protein [2] https://predictioncenter.org/casp14/index.cgi https://predictioncenter.org/casp14/index.cgi * That's an understatement. The solutions were really very good, much better than those produced by any other submission to CASP14.
- Cas9 5y ago
  Thanks a lot for the detailed explanation :-)

by Cas9 5y ago

radus 5y ago

Yes, it is still useful. Even structures obtained through traditional means (eg. x-ray crystallography) are approximations to an extent since there are limits to the resolution that you can obtain and oftentimes regions of proteins are "disordered". Additionally, these structures are only snapshots of a protein in a particular state, which may not completely reflect the dynamics of the protein in its native environment.

whimsicalism 5y ago

You want to find a protein that has X structure (since structure determines function to a degree). If AlphaFold is substantially more accurate at solving proteins, it can mean that drug discovery is faster, assays are faster, etc. etc. The "unexpected problems" would be caught in the assay stage.

radus 5y ago
Kind of disagree with this.. solving protein structures is not the rate limiting step in drug discovery or in biochemical assays -- not by a long shot. See this excellent comment by @dekhn on a related submission: https://news.ycombinator.com/item?id=27849046 https://news.ycombinator.com/item?id=27849046

dekhn 5y ago

The protein folding problem is not NP complete. The "formal" protein folding problem, as posed (find the set of dihedral angles whose resulting structure has the lowest energy) might be, but that bears only a distant resemblance to how people "solve" the problem today. At the very least, the statement is incorrect because many proteins don't actually fold to their energy minimum, they get stuck in kinetic traps, and the formal PF defintion never accomodated that idea.

bawolff 5y ago

I dont know much about protein folding, but for most things in life,exact solutions to NPC problems usually aren't needed for non-contrived problems. In many cases, approximations are good enough. Besides, this is real life - if predictions and real life match, that's great. If they don't, well you know you went wrong somewhere.

jerven 5y ago
I would upvote this twice if I could. Life science quite often NP-hard still approximate results are extremely useful. Joke, which I think is from Sean Eddy (hammer). Bioinformatics approaches a Computer Scientist for help with a hard problem. CS agrees to help. Year later CS comes back very excitedly. "your problem is not hard it is NP-hard!". Bioinformatics nods, and says "I still got to solve it" and continues finding ever faster and better approximations ;) Also problem space is both bounded (you don't have infinite length proteins) and f'd up in reality. e.g protein hijacking and re-conformation in the face of an infectious agent.

wpasc 5y ago

A very-non-expert opinion, if an approach approximates it pretty well and can be improved upon, then it could end up being quite useful. Given that biology exists on a real, tangible scale then perfection in the fold prediction isn't necessary, instead just an approximation that is sufficiently good to be functionally useful. ^ That sounds like word-salad BS but I think there's some truth to it. I know protein folding has been postulated to be useful in terms of understanding basic biology, understanding disease pathology, and drug prediction. While a wide range of approximations are functionally useless, perhaps the Alphafold approach or some improved version of it surpasses the functionally useful threshold. At least I hope so

ashtonbaker 5y ago

Not really an answer to your question, but is the problem really NP-complete, or just combinatorially difficult? For example how is this condition of NP-completeness satisfied? > it is a problem for which the correctness of each solution can be verified quickly [0] [0] https://en.wikipedia.org/wiki/NP-completeness https://en.wikipedia.org/wiki/NP-completeness

Cas9 5y ago
According to this answer[0] it seems it's actually NP-Hard, my bad. Haven't seen the proof though, and I'm not an expert. [0] https://cs.stackexchange.com/questions/128493/is-protein-folding-really-np-hard-and-how-to-show-that https://cs.stackexchange.com/questions/128493/is-protein-fol...

mrfusion 5y ago

Is it really np complete? If so we could map other np complete problems onto it and let biology solve it for us.

nmca 5y ago

NP completeness tells you about the hardest cases, not the most useful cases.

hobofan 5y ago

I would expect that once AlphaFold has helped you identify a potential protein (e.g. as a drug) out of a bigger set of potential proteins, there will still be a manual step of traditional cryoEM, NMR, etc. to get an accurate high-resolution structure.

t_serpico 5y ago

To me, the interesting thing is not the specific results but rather that you can accurately predict crystal structures from sequence alone. This begets the question: what other physical biological properties can we predict?

thxg 5y ago

> (it's NP-complete after all) Protein folding is a physical/biological phenomenon. AFAIK we don't currently have a proper exact mathematical formulation of the problem that would let one determine its complexity. You may be referring to this paper [1]. It only claims that one particular optimization problem, believed to give a solution to protein folding problems, is NP-hard. So, even if a suitable exact formulation exists, it is not yet proven that protein folding is hard, although it for sure seems plausible. By the way, it is perfectly possible today to solve some very large-scale NP-hard problems (think millions of variables and constraints) in reasonable amounts of time (think minutes or hours). Examples are knapsack problems, SAT problems [2], the Traveling Salesman Problem [3] or more generally Mixed Integer Programming [4]. [1] "Complexity of protein folding", 1993, by Aviezri S. Fraenkel [2] http://www.satcompetition.org http://www.satcompetition.org [3] http://www.math.uwaterloo.ca/tsp/ http://www.math.uwaterloo.ca/tsp/ [4] http://plato.asu.edu/bench.html http://plato.asu.edu/bench.html

saithound 5y ago

AlphaFold is not about solving any kind of NP-complete problem. Proteins consist of chains of amino acids which spontaneously fold up to form a structure. Understanding how the amino acid chain determines the protein structure is highly challenging, and this is called the "protein folding problem". People use mathematical models to predict how proteins fold in nature. Many such mathematical models are stated in terms such as "proteins fold into a configuration that minimizes a certain energy function". Even the simplest such models [1] give rise to NP-hard decision problems, which are also known (somewhat confusingly) as "protein folding problems". To make this a bit less confusing, I will call the mathematical decision problems PFPs. Like all mathematical models, our protein folding models don't correspond exactly to reality. Even if you are somehow able to determine the exact mathematical solution to a mathematical PFP, that _still_ doesn't guarantee that the real protein that you were trying to model behaves like the mathematical solution would indicate. E.g. the protein may fold in such a way that it gets stuck in a local optimum of the energy function you were using. How do we detect this? We make inferences about how the protein should behave, given the mathematical solution to the Protein Folding Problem, and then we perform experiments, and find out (empirically) that the protein behaves in a manner that is inconsistent with the inferences drawn from the mathematical model. Scientists _do_ do this. And they would have to do it even if they had a fast, exact way to solve NP-complete problems, because the NP-complete problems are still just part of a mathematical model, and need not correspond to reality in any way. The success of AlphaFold is not measured by how well it solves (or approximates) mathematical PFPs. The success of AlphaFold is measured by making successful predictions about how certain proteins will fold. And this is exactly how it was tested [2]: they threw it at a bunch of problems for which scientists have empirically determined how certain amino acid chains fold, but didn't release the results. And then they compared the solutions predicted by AlphaFold, and found that most of the predictions were consistent with what they knew to be the case.* [1] https://en.wikipedia.org/wiki/Lattice_protein https://en.wikipedia.org/wiki/Lattice_protein [2] https://predictioncenter.org/casp14/index.cgi https://predictioncenter.org/casp14/index.cgi * That's an understatement. The solutions were really very good, much better than those produced by any other submission to CASP14.

Cas9 5y ago
Thanks a lot for the detailed explanation :-)