By Alena Shmygelska (based on joint work with Holger Hoos)
The protein structure prediction from its amino-acid sequence is one of the most important problems in computational biology. In this work, we focus on a widely studied abstraction of this problem, the 2-dimensional hydrophobic-polar (2D HP) protein folding problem. We present an improved version of our recently proposed Ant Colony Optimisation (ACO) algorithm for this NP-hard combinatorial problem and demonstrate its ability to solve standard benchmark instances substantially better than the original algorithm and comparable with state-of-the-art Evolutionary and Monte Carlo algorithms for this problem. The improvements over our previous ACO algorithm include long range moves that allows us to perform modification of the protein at high densities, the use of "improving" ants, and selective local search. Overall,the results presented here establish our new ACO algorithm for 2D HP protein folding as a state-of-the-art method for this highly relevant problem from bioinformatics.