I’ve heard that solving these problems could help solve cancer specifically through protein folding problems but I have no idea how.
In: Biology
So the thing which makes NP(C) problems interesting is that they are hard to compute, but easy to verify.
For example a sudoku has pretty simple rules, and you can verify that no digit occurs twice in the same row/column/box more than once pretty easily. To solve it however there is always some guessing, seeing where it gets you, and reverting when it is false. That’s why the N in NP stands for non-deterministic.
With protein folding it’s pretty similar: a long chain molecule can fold in many different shapes which each their own behavior. It’s easy to verify from a functional “fold” whether it’s a valid protein, but hard to generate functional folds from the protein.
Finding better solutions for NP problems, allows us to more easily find functional folds for the proteins in our body, and allow us to fold the proteins ourselves into those shapes to get desired behavior. Now we mostly have to guess and see what it gives.
Proteins are *really* complicated. Like, obscenely complicated. But they’re all made from the same group of 20 or so amino acids. As your ribosomes stick amino acids together, the molecular forces between them causes them to fold into the plethora of proteins that make up all of you.
Imagine being told that you need to make [this](https://i.imgur.com/ChAYqYa.jpg) and the only instructions you’re given is [this](https://i.imgur.com/rrImfVG.jpg). Sure, you know that folding that piece of paper along those lines will turn it into that dragon. But you don’t know which way to fold those or which order to do it in, and if you fold it even once the wrong way or in the wrong order, the entire thing comes out wrong and you have no way of knowing until you’re mostly finished.
And also you can’t even see anything, your hands are in a box and you’re doing everything by feel. And also it’s like, ten different pieces of paper with different patterns that all have to be done perfectly and then put together somehow.
That’s kind of what it’s like to try to figure out how protein folding happens. The only real way to figure it out is to just…do it. Put all of the pieces into a computer program and tell the program to start putting them together and see what happens. There’s no elegant solution for that, no simple, generalized rule for how a protein goes together. That makes it computationally complex. A computer just has to sit there and try and try and try and try and try different combinations.
All of that matters because proteins are how your body does…everything. Everything in you is either made of proteins or made by proteins. They send the signals that your cells to use to decide to grow and split or self-destruct, and to build the tags that tell your immune cells not to attack them. If we can understand how proteins fold, we can understand how your DNA codes to build them. If we understand how your DNA codes to build them, we can understand how your DNA was damaged to cause them to fail, and maybe how to fix your DNA. We can better understand how the proteins cause those signals to happen, which might allow us to figure out medicines that target those specific signals. All of those things would be useful tools to help us fight cancer.
there are ways to convert problems within a computational complexity class. If you are interested in solving problem A, but only know how to solve problem B, you could try to convert A into a problem that is of type B.
If you efficiently solved the traveling salesmen problem, and you could convert the protein folding to a salesmen problem, you solved the protein folding.
One interesting question would be: are approximate solutions on the salesman also approximate solutions to the protein?
Latest Answers