### Gamers Succeed Where Scientists Fail

The rather provocative title of this post refers to the at home science game, Foldit. The game essentially involves figuring out how to fold proteins in three dimensions. This is an extremely difficult problem, even for computers. The Foldit game is a way of harnessing the brain power of video game players to help find solutions.

The game has been available for a while, and now (apparently for the first time) has been used to solve a specific puzzle of protein structure. Scientists have been trying for 10 years to solve the structure of retroviral protease, a protein-cutting enzyme found it HIV-like viruses. So, they put the problem to Foldit gamers, and they solved the structure in one week.

The reason these types of problems are so difficult is that the number of possible ways in which a large protein can fold is staggering large. This is, fact, called an NP-problem (non-deterministic polynomial). The classic example of this is the traveling salesman who wishes to map the minimum route to a set of cities he wishes to visit. Such problems are impossible to solve by computational brute force (the number of possibilities to check quickly becomes greater than the number of atoms in the universe), and there is no mathematical way to derive the answer quickly.

For this reason computer programmers have simply not been able to develop a program that can solve the folding puzzle for large proteins.

The human brain, however, is a massive parallel processor and is excellent at pattern recognition – something we still do (for now) better than computers. Also, there are lots of people – lots of computer brains that can be put to work.

That is the idea of the Foldit program – to put human brains to work to solve the NP-problem of folding proteins that computers cannot do with brute force. In this case, the Foldit gamers were able to suggest possible folding strategies that checked out – they essentially solved the folding puzzle in one week. The potential benefit of this is, potentially, the ability to design drugs that target receptor sites on the folded protein, perhaps to inactivate it. In other words, this knowledge could lead to the development of new anti-retroviral drugs.

It is important to recognize that the reason computers cannot solve NP-problems is not a limitation of current computer power. Standard computers, no matter how powerful they become, will simply not be able to solve NP-problems. However, some think that quantum computers may be designed to solve NP-problems (even if they are not particularly suited to running Windows).

The Foldit program is a great way to engage the public with science, and it’s a great way to make use of a powerful resource (the human brain) to solve difficult problems in science. It’s good to see the fruits of this program – hopefully it will make Foldit and programs like it more popular.

The article says that it took the gamers three weeks, not one. And quantum computing will not solve NP-problems, it will just change the scale by several orders of magnitude for when a NP-problem becomes too difficult to solve. For instance, the traveling-salesman problem is not too difficult when there are only 3 cities, but quickly becomes intractable as more cities are added. Quantum computing will let the number of cities get to a few more before it is intractable.

Computers can solve the traveling salesman problem faster than humans, not by brute force, but by using heuristics like ant colony optimization.

I knew you subscribed to ant colony optimization. And you’re doing a damn fine job, you and all your little ants.

Don’t you have a bridge to hide under?

Don’t you have a colony to feed?

Computers actually can’t “solve” the traveling salesman problem. By using heuristics (ant colony optimization is one of several that have been developed), they can arrive at a “good” solution in a reasonable amount of time, but heuristics can’t give you the best solution (or at least they can’t give a solution you can prove is the best). So far, computers can only give you an exact solution through brute force calculations, which is impractical for large numbers (I’ve seen 20 cities cited as the cut-off point for the traveling salesman problem).

I’m not as familiar with protein folding; I think (but I’m not sure) that you need an exact solution, which would rule out heuristics. And, in response to your comment/question below, as I understand it, and as Mr. Novella notes in his post above, there are a large number of ways (too large for brute force approaches) a protein molecule could fold, but only one way it actually does in nature. Of course, it’s not computing its optimal fold ahead of time, it’s just folding according to natural laws to achieve its most stable and lowest energy state – but no one has figured out how to compute what that is ahead of time. And at this point I’m beyond my limited understanding of protein topology and NP-complete problems, so I hope someone else can give you a better – maybe even exact :) – answer.

A “good” solution is still a solution. That’s how I was using “solve.”

An NP problem is intractable for both computers and humans. Both use heuristics. Computers are already faster than humans at finding both optimal and sub-optimal solutions to the traveling salesman problem, they can beat humans at chess, and I expect that they’ll fold proteins faster too.

I mentioned ant colony optimization because it shows how nature can find good solutions to hard problems. Evolutionary algorithms are another example.

If you literally want to travel between the capitals of all 48 contiguous states (the classic formulation of the traveling salesman problem), then a “good” solution is indeed good enough, and solves the problem in practical terms. I’m sure there are plenty of practical situations where “good” solutions to NP-problems are sufficient.

Again, though, it’s my understanding (although I could be wrong) that this is not the case for protein folding, where you need an exact solution, which computers (at this point) can’t provide. You may well be right that “they’ll fold proteins faster” – eventually. As this post indicates, humans are still better at some problems – for now.

BTW, NP-problems aren’t necessarily intractable – exact solutions have actually been found for a number of specific traveling salesman problems. Using problem-specific approaches and math that I frankly don’t understand, exact solutions can be found for traveling salesman problems involving tens of thousands of cities. Maybe some day similar approaches can be used for protein folding.

For now, though, the idea that gamers playing around at home found a solution to a seemingly intractable problem that had eluded professional researchers for a decade in only three weeks is pretty cool.

Why is protein folding an NP problem? Isn’t it just molecules forming bonds? Somehow they naturally fold up without any computation. It’s not like solving a Rubik’s cube.

The answer to you question is complicated, and I probably would get it wrong, but if you play through the FoldIt tutorial, you’ll be able to answer your own question.

I would like to contribute my wisdom this problem. Alas, I am not able. I am just programmer. If you dummy the discussion down, though, I will hop right in.

I see what you did there