iainmcgin
06-05-2002, 05:53 PM
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:
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: