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.
