Scatter search for protein structure prediction. (c2008)

Abstract

Proteins are organic compounds made up of chains of amino acids. These amino acids are formed from atoms and the chain fold into complex 3-dimensional structures based on their chemical and physical properties. A protein is characterized by its 3D structure, which defines its biological function. The protein structure prediction problem has real world significance where several diseases such as Alzheimer, cystic fibrosis, mad cow disease, and many cancers are associated with the wrong folding of proteins. Computational methods for predicting protein structures have recently gained popularity. In this thesis, we present a scatter search algorithm for predicting 3D structures of proteins. Given the protein's sequence of amino acids and data collected from known protein structures, our algorithm produces a 3D structure that aims to minimize the energy function associated with protein folding. Scatter search is an evolutionary approach that is based on a population of solution candidates. These candidates undergo evolutionary operations that combine search intensification and diversification over a number of iterations. We evaluate our algorithm on three proteins taken from a protein data bank. The results show that our algorithm is able to produce 3D structures with good sub-optimal energy values. Also, the root mean square deviations of these structures from the reference proteins are promising within limits imposed by the assumptions used.