Devising protein structure prediction methods comes to mind. The problem is, there's only finite training/evaluation data; I have no idea how one would avoid hideous overfitting if performing an infinite number of trials. This is probably a problem with any machine-learning type problem.

I don't know if there are existing molecular dynamics sims that would give good answers given enough cycles (fivemack?); if so then one could generate one's own training data (and get structures for all known sequences while we're at it).

Yes, I was wondering if you'd have any interesting computational biology problems. I think that if there's existing simulation software around for this sort of thing then I'm prepared to relax my ground rules enough to let you have access to a copy of it :-)

The problem is, as I say, most of the comp.bio problems are things that need validation, and against a finite evaluation set, you end up with a machine that will regurgitate the test data. I guess you could try and derive a (relatively) small number of rules that will do the job.

Proving evolution by the mad method my professor came up with (which I can't remember the details of - will have to look through my lecture notes. There's a great short story in the latest Interzone about evolving AI in a superfast processor.