Knowledge-based Approach to Genetic Algorithms for the Protein Structure Prediction Problem

Author(s)

Lariza Laura de Oliveira

• Document type: Master's Dissertation
• Press: São Paulo.
• Institution: Universidade de São Paulo (USP). Instituto de Matemática e Estatística (IME/SBI)
• Defense date: 2011-05-20

Examining board members

Renato Tinós; Alexandre Cláudio Botazzo Delbem; Paulo Sérgio Lopes de Oliveira

• Advisor: Renato Tinós

Abstract

Proteins exhibit an enormous variety of biology functions. The knowledge of tertiary structures can help the understanding of the proteins function. According to Anfisen, the native tertiary structure of a protein can be determined by its primary structure information, what could allow that computational methods could be used to predict the tertiary structure when the primary structure is available. However, there is still not a computational tool to solve the structure prediction problem for a large range of proteins. In this way, Protein Structure Prediction (PSP) has been a challenge to Molecular Biology. The conformation of native protein is usually the thermodynamically most stable configuration, i.e., the one having the lowest free energy. Hence, PSP can be viewed as a problem of optimization, where the structure with the lowest free energy should be found among all possible structures. However, this is an NP-problem, where traditional optimization methods, in general, do not have good performance. Genetic algorithms (GAs), due to their characteristics, are interesting for this class of problems. In recent years, there is a growing interest in using GAs for the protein structure prediction problem. The main objective of this work is to verify the addition of useful information to GAs employed in PSP. Each individual of the GA represents a solution for the optimization problem which is, in this case, a possible conformation that will be evaluated by a force field function. Thus, an individual is encoded by a set of torsion angles of each amino acid. In order to reduce the search space, a database composed of angles, determined by crystallography and NMR, is used. With the aim to guide the final search process and maintain diversity in GAs, two strategies were employed here: Random Immigrants and Similarity-based Immigrants. The last strategy was based on similarity of primary amino acid sequence. Furthermore, in this work, a coarse-grained force field, which uses -carbon to represent the protein backbone was employed to evaluate the individuals of GA. (AU)

• FAPESP's process: 08/07098-8 - Use of Knowledge in Genetic Algorithms for Structure Prediction of Proteins
• Grantee: Lariza Laura de Oliveira
• Support Opportunities: Scholarships in Brazil - Master