Protein folding isn't a good "proof of work" problem. Really the expression "proof of work" is misleading. The main point of mining is not the lottery part. The lottery is only a side effect.
The main point of mining is to extend the blockchain. Pick the last block in the blockchain, add the recent transactions and create a new block in a way that is almost imposible to forge. The blockchain keeps all the transactions without a central autority.
-
Q: How are we sure that nobody replaced the old blocks with fake versions?
A: Chain the blocks, so they have to forge the old the chains of block up to the newest.
-
Q: How are we sure that it's difficult to forge a lot of blocks?
A: Made it as difficult as possible, but not so difficult that it's impossible to find the next block. Pick a problem where we can predict and adjust the difficulty of the problem.
-
Q: How are we sure that the blocks are legit?
A: Made it easy to verify. Finding a block should be difficult, but checking it should be easy.
-
Q: How are we sure that it's really difficult to forge them?
A: Use some cryptographic secure problem (and hope that it's secure). Don't create your own apparent difficult problem.
-
Q: How do we convince people to mine?
A: A lottery! Give 50 BTC for each block they found, plus fees.