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.