Alphafold

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

[2] 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.

Here's where I think we need to be going: You go to a doctor's office, sick. 1) They take a blood sample. 2) They find the malignant bacteria and DNA sequence it. 3) If it's a known strain, they know what antibiotics to use on it. 4) If not, they solve protein folding on the genes. 5) From that, they see which existing antibiotics would kill it. 6) If none will, then given the proteins, they have to derive a new antibiotic.

1) is easy. 2) might not be - there can be a lot of things in a blood sample, and finding only the interesting (bad) things might not be simple. The sequencing part is pretty much solved. 3) would take a bit of work, but I think it's possible now. 4) we're getting there. 5) might have a fair amount in common with 3), but it probably takes some additional work. 6) is... probably non-trivial.

That's just one research agenda. There are others. You may have to move to related work, but I doubt you're going to be out of a job in this lifetime.

I'm genuinely curious: could the output of Alphafold be fed into a classical folding algorithm (as a starting point), or is the output of Alphafold too far down the wrong path, in these cases?

The key difference seems to be using the multiple alignments and assumption about evolutionary conservation? Useful for genes conserved, but less useful for de-novo proteins (like COVID and cancer) I guess?

Where there isn't an available crystal structure, Alphafold can be used to create initial structures for simulation via folding@home, replacing older homology modeling techniques.

Source: former folding@home researcher.