3 ms·
So, the most recent paper says they get a "majority" of structures right: https://www.nature.com/articles/s41592-021-01362-6 https://www.nature.com/articles/s4
by hedora 4y ago
So, the most recent paper says they get a "majority" of structures right:
https://www.nature.com/articles/s41592-021-01362-6 https://www.nature.com/articles/s41592-021-01362-6
And the January paper from this team claimed 66%:
https://www.nature.com/articles/s41592-021-01362-6 https://www.nature.com/articles/s41592-021-01362-6
This is impressive, but not game changing.
Solving protein folding is analogous to solving the halting problem, but harder. The sequence is interpreted by squirting out a string of stuff that mutually attracts and repels itself and the environment. Different temperatures, neighboring proteins (the "program input"), etc, leads to different folds (the "program output"). As with software, there's a happy space of expected inputs where it's hopefully easy to reason about expected outputs.
The difference between folding and the halting problem is that each step of the execution trace you'd need to generate to show a particular structure is reachable is quadratic in the number of atoms in the protein and surrounding environment, and the steps are not discrete.
Alpha fold mostly just glues together previously seen folds that were produced via x-ray crystallography. This technique is called "threading" and is decades old. It has all the obvious limitations you'd expect if you extended my halting problem analogy.
Also, most of the low hanging fruit in this field was picked a long time ago, so the 33% they perform poorly on is precisely the interesting part of the problem space.
Edit: Here's an early paper from 1997: https://pubmed.ncbi.nlm.nih.gov/9237912/ https://pubmed.ncbi.nlm.nih.gov/9237912/
For whole structure threading, they get the correct fold "45-75% of the time". "Correct fold" is a weaker criteria than Alpha Fold uses in their abstract. However, it's interesting that Alpha Fold is still stuck in that range 25 years later. (Also, the 1997 paper is nowhere near state of the art.)
- jagraff 4y agoI disagree with your characterization. Of course, true protein folding computation is hard (literally NP-hard I believe) but the halting problem can be proven to be uncomputable, whereas protein folding is clearly computable - every time a protein is produced in our cells, protein folding is computed. Practically, the two may be the same, in the sense that we can neither truly compute how a complex amino acid sequence will fold nor whether a complex computer program will halt, but one is merely intractable, whereas the other is impossible.
- hedora 4y agoNot true. Protein folding is just as incomputable as the halting problem. Read up on chaperone proteins. They manipulate the protein as it folds to change the final structure. Producing a list of biologically common folds of a protein sequence without access to the actual environment they see is directly analogous to producing a list of all reachable statements in a program over all possible inputs. Biological processes are analogous to running a program once on a well tested input. Prion-based diseases are like fuzz or pen testing the folding process.
- junofan 4y agoHmm, computability is more of a mathematical formalism thing. Physical phenomena aren’t really at question; computability is trivial. But yeah, protein folding in silico is pretty tough.
- hedora 4y agoA computer is just a physical phenomena, so computability is also trivial. Just put the physical computer into the right start state, then wait. :-) Of course, the mathematical formalism is a more useful way to think about computing (and I argue, protein folding).