An efficient approach for solving the HP protein folding problem based on UEGO

This work applies the methodology of the Universal Evolutionary Global Optimization, UEGO, to solve the protein structure optimization problem based on the HP model. The UEGO algorithm was initially designed to solve problems whose solutions were codified as real vectors. However, in this work the HP protein folding solutions have been defined as means of conformations encoded by relative coordinates. Consequently several main concepts in UEGO have been re-defined, i.e. the representation of a solution, the distance concept, the computation of a middle point, etc. In addition, a new efficient local optimizer has been designed based on the characteristics of the protein model. This work develops the adaptation and implementation of UEGO to the HP model and analyzes the UEGO solutions of HP protein folding for different 3D problems. Finally, obtained HP solutions are converted into all-atom models so that comparison with real proteins can be carried out, and a good agreement is obtained for small size proteins.