Scatter search metaheuristic for homology based protein structure prediction. (c2015)

Abstract

Determining a protein’s structure is a challenging goal in structural bioinformatics, offering important insight towards understanding the function of a protein. Homology modeling is an effective technique in protein structure prediction (PSP). However this technique suffers from poor initial target-template alignments, especially when the sequence identity between the two falls below 25%. To improve homology based PSP, we propose a scatter search (SS) metaheuristic algorithm. Our algorithm optimizes the initial poor alignments, generated by a dynamic programming method. SS is an evolutionary approach that is based on a population of candidate solutions. These candidates undergo evolutionary operations that combine search intensification and diversification over a number of iterations. The metaheuristic is guided using two fitness functions, GA341 and DOPE. 3D models are generated using the software MODELLER. We assess our algorithm on a total of 11 proteins whose structures are present in the Protein Data Bank (PDB) and which has been used in previous literature. Results obtained by our algorithm are compared with other homology modeling approaches as well as a pure ab-initio and a fragment based assembly approach. The 3D models predicted by our algorithm show improved root mean standard deviations (RMSD) with respect to the native structures.