Sep 19 2011

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 in 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.

13 responses so far

13 thoughts on “Gamers Succeed Where Scientists Fail”

  1. decitrig says:

    You’re comparing two different things here: the difficulty of solving a general class of problems (folding any protein) with the difficulty of solving a single example in that class (folding *this* protein). I think it’s important to make the distinction.

    If you’re going to claim that something special allowed the humans to solve the specific example better than computers could, you’d have to state the size of the input somehow and then show that the human solution was polynomial in the size of the input. It took a week to solve, so it may well be that Foldit is still a non-polynomial-time algorithm, it just parallelizes more easily than formal programming.

    Hope that’s clear. I agree that this is a brilliant use of technology & crowdsourcing, I just don’t think the discussion of NP problems is really appropriate here.

  2. vexorian says:

    This has been a very interesting news bit and well-written article. I had to nitpick about the NP problems though:

    NP-completeness is not about there being trillions of possible solutions. But about whether they can be reduced to other NP-complete problems and that other NP-complete problems can be reduced to them.

    Computers can “solve” instances of NP-complete problems.
    There are SAT ( solvers which get a good result in acceptable more often than not. The issue is that we do not know yet whether it is possible or not to come up with an algorithm that can give a correct answer to any instance of these problems in polynomial time.

    Since right now only non-polynomial time algorithms are known that can solve any instance of NP-complete problems, it means that if we were to try an algorithm that is guaranteed to correctly solve any instance of the problem, it would take enormous amounts of time to solve even slightly large instances of the problem UNLESS we could come up with an algorithm that is faster, if we did then we would also find fast algorithms for all the other NP-complete problems (which would deserve you world-wide fame and right to win a 1000000 dollars challenge).

    Here is more:

    As we could see, the gamers were able to solve the specific instance of the molecule problem and they used an algorithm that solves that specific instance.

  3. locutusbrg says:

    Amazing is there a site that has the specifics of how it was done. I am curious, is it a pattern recognition issue. Which I know humans excel at, or was it another aspect of our strengths?

  4. sharkey says:

    However, some think that quantum computers may be designed to solve NP-problems (even if they are not particularly suited to running Windows).

    That is probably not the case. Quantum computers can solve a class of computational problems known as “bounded quantum polynomial”. The best-known quantum algorithm is Shor’s factoring algorithm, which shows a dramatic speed-up from classical algorithms. However, factoring a composite number into prime factors is not in the same class of problem as the traveling salesman problem, which is in a class known as NP-Hard. There is no evidence that a quantum computer can efficiently solve NP-hard problems, which is too bad as there are many interesting problems in that class.

  5. mikero says:

    Computer scientist here, excited to have a chance to discuss computational complexity here on Neurologica 😉

    This is, fact, called an NP-problem (non-deterministic polynomial).

    Everywhere in this article where you use the phrase “NP-problems”, the more accurate term is “NP-complete problems.” Just saying that a problem is “NP” doesn’t say that it is difficult. “NP-complete” means that the problem is one of the hardest problems in NP, and these are the tough ones. Finding the protein folding structure (when pseudoknots are allowed) that has the minimum free energy is NP-complete.

    Such problems are impossible to solve by computational brute force

    Believed to be impossible to solve significantly faster than brute force. And as you say, the number of possibilities one must explore with brute force quickly becomes astronomical.

    However, some think that quantum computers may be designed to solve NP-problems

    This is a common misconception about quantum computing, but it is very unlikely that quantum computers are a magic bullet that make every NP-complete problem tractable. That would require an exponential speedup across the board, while quantum computing only gives a general quadratic speedup. There are some specific problems (like factoring) for which the speedup may be exponential, but these problems are somewhat incomparable in difficulty to NP-complete problems.

    And that is probably more than you cared to know about the current state of computational complexity theory 😉 Cheers!

  6. tmac57 says:

    Now if they can just solve the problem of folding a road map…

  7. jyesselm says:

    A faculty membered visited my research to discuss his research and apparently he is using a 72 qbit quantum computer to do protein folding with a 3-4 long polypeptide. He said he is currently submitting it to nature protocols I think… Anyway talking with him with my very limited understanding of quantum computing it seems like it is at least plausible keep a look out for it. His name is Dr. Aspuru-Guzik from Harvard.

  8. LarryCoon says:

    In addition to what Sharkey & Mikero said, I think we need to be careful about a possible equivocation of the word “solve.” An NP-complete problem (like the Traveling Salesman problem) is NP-complete* because it’s proven to take exponential time to find *the* solution. For example, for the Traveling Salesman problem it’s not sufficient just to find a really fast traversal path; you have to search every possible path in order to know that you found the best path (and the number of paths rises by n-factorial).

    *NP-complete is also considered NP-complete because it is proven that every other problem in the set of NP-complete problems can be transformed into this problem in polynomial time.

    On the folding problem, I didn’t see enough information to determine if the solution was *a* solution or “the” solution — I.E., was the entire state space searched to determine that no better solution exists, or did they just find one solution that was sufficient?

    If the latter, then it would be equivalent to someone finding a fast traversal in the Traveling Salesman problem (which most people can do pretty well) and declaring the problem solved. While a fast solution is usually good enough for government work, and may indeed be *the* best solution, SOLVING the problem means showing that there is no better solution, and that’s not what you did.

  9. SARA says:

    I found this fascinating and if anyone finds an article (for the layman) on how the foldit worked, I would like to read it.
    A short article I read said 10 gamers solved it.
    So I wondered if the gamers worked as a team or if the problem is solvable in layers. If solvable in layers, than the foldit could just update everyone to the newest level solved and move forward.
    However, that seems unlikely on two fronts. One, its a public game, so there were likely a lot more players than 10.
    And two, the description of the computer whizzes in comments here make it sound like NP Complete would need to solved a whole.
    You can’t assume what the 1st leg of the Traveling salesman’s route should be until you have shown that the further legs would support the entire route being shorter than any previously tested route, right?
    Or if 10 people came up with the same solution. Which seems remarkably unlikely in such a short period.

  10. eiskrystal says:

    Ah yes, but how many of those gamers were also scientists?

    Also does getting a million gamers to challenge something in general not count as brute force?

    That being said, I think it’s brilliant that this has been done. Imagine what we could have achieved if this was done by everyone in America instead of them watching tv. It would have been solved before the commercials.

  11. davidsmith says:

    Very interesting post. I wonder if gamers will start charging a fee for their services? 😀

    So, if our most powerful classical computers have a hard time solving NP-complete problems, what is it about the brain that is giving it an advantage? Is is purely a case of parallel processing? If so, why can’t we design a computer than can do parallel processing like a brain can? Is it a problem of implementation?

  12. Karol_str says:

    They have to find just “a” solution, in quantum chemistry / molecular modelling there are only few examples of “the” solution and the rest is just the best known at given time (due to variational principle).

    It is not needed to find “the” solution (but it would be nice). The point is that now we can treat given protein with enough accuracy for the problem of molecular mechanics.

Leave a Reply