AFAIK, there are no "useful" computational problems that have the properties necessary to be used as a proof-of-work.
The hash function is used because it is irreversible, easily checkable, small in size, and probably some other things I'm forgetting. Even if you could, for example, encode the transactions as a polypeptide (chain of amino acids), and then made folding the polypeptide into a protein the proof-of-work, such a proof-of-work could not be checked without redoing the entire computation.
Even if you could come up with a suitable problem, due to the economics of BC you would never actually generate any additional value by using a "useful" problem.
I think this point needs to be stressed in the BTC documentation...it's kinda like the uncertainty principle: the more useful the work, the less suitable it is to being proof-of-work for currency purposes (kind of like how Heisenberg himself misled the Nazi's doing "useful" work on the bomb)...