Predicting the native structure of proteins is one of the most challenging
problems in molecular biology. The goal is to determine the three-dimensional struc-
ture from the one-dimensional amino acid sequence. De novo prediction algorithms
seek to do this by developing a representation of the proteins structure, an energy
potential and some optimization algorithm that ¿nds the structure with minimal
energy.

Bee Colony Optimization (BCO) is a relatively new approach to solving opti-
mization problems based on the foraging behaviour of bees. Several variants of BCO
have been suggested in the literature. We have devised a new variant that uni¿es
the existing and is much more ¿exible with respect to replacing the various elements
of the BCO. In particular this applies to the choice of the local search as well as the
method for generating scout locations and performing the waggle dance.

We apply our BCO method to generate good solutions to the protein structure
prediction problem. The results show that BCO generally ¿nds better solutions
than simulated annealing which so far has been the metaheuristic of choice for this
problem.