Problems in optimisation with applications to biology?
Maximum likelihood phylogenetic trees. The trees are easily scored but the tree space is so large that finding optimal phylogenetic trees is extremely difficult. There's some research but there haven't been very many actual breakthroughs, so it's probably a pretty rich field.