Protein Sampling an NP-Complete problem?

[iainmcgin]

Hey,

A slightly random and not very well thought out question, but I'm studying for my second year comp sci exams and I thought I might as well ask.

Is ab inito prediction of protein folding an NP complete problem? i.e. one which has no known polynomial time complexity algorithm which can accurately predict the structure of the protein?

I was just thinking about the amount of computing power that's being thrown at the proteins we're analysing, and the (small?) size of the proteins. Is it just that the time complexity is quite huge but still polynomial, or is it actually an NP problem?

If it is an NP complete problem, is the algorithm that is employed in this project equivalent to the algorithms that exist for the Travelling Salesman Problem that are polynomial, i.e. it is "approximating" a good solution but most likely is missing the "perfect" solution?

Another thing: say this is an NP-complete problem, and the holy grail proof that the set of polynomial problems and the set of NP-complete problems are actually the same (meaning that all NP-complete problems actually do have polynomial time algorithms that solve them), would this mean that an algorithm could be devised for protein folding that would be polynomial?

I think these are interesting questions, since as mentioned somewhere on the site there are now literally thousands of proteins uncovered from the human genome that need to be analysed. If this problem were NP-complete, and NP problems were proved to be solvable in polynomial time, then all those unanalysed proteins could be solved in perhaps a few months with some big supercomputers rather than years, perhaps even decades! :cheers:

Iain
University of Glasgow

P.S: I have no real knowledge of biology so I hope I'm not making some completely wrong assumptions :smoking:

[jlandgr]

Hi, read http://bane.free-dc.org/forum/showthread.php3?threadid=714&perpage=25&pagenumber=2
Hope this helps and welcome,
Jerome

[MAD-ness]

The issue of NP complete-ness, etc. is discussed in the thread under the "educational" forum in the thread "The science of Distributed Folding" by Raj. Dr. Hogue and Howard Feldman both have some long comments and Howard especially addresses the issues of NP complete solutions (they have not found a solution to an NP complete problem) and it is a very informative thread.

gl.

[iainmcgin]

Thanks for the links, they proved quite informative... :)

I had a feeling that although the collision detection problem within individual proteins has been solved in O(NlogN) time by Howard et al, the overall problem was still an NP-complete one. I knew that if it was an NP-complete problem (and not just some horrible time complexity like O(N^100) or something) then there would have been no way that they would have solved it with a polynomial algorithm, since it would have caused a HUGE riot amongst my computing science lecturers.

One of my lecturers (Dr. Patrick Prosser) deals specifically with "hard" problems like NP-completeness, so we probably would have heard from him that a proof that the NP-complete problems were actually solvable in polynomial time, in amongst his mad raving gestures. All of a sudden all those Travelling Salesman would get where they wanted to go for a few hundred pounds less, and the world would be a better place ;)

I find things like this fascinating, and I can only wish Howard & co. the best of luck in finding faster and faster ways to solve this problem. I don't think I could ever do it, I would probably just start breaking things in frustration. Like people :rolleyes:

Iain
University of Glasgow

P.S: I was thinking of emailing the Bioinformatics departmeny here at my university to see if they will throw some computers DF's way, do you think they would be interested?