Evolutionary algorithms and simplified models for tertiary protein structure prediction

A predição de estruturas de proteínas (Protein Structure Prediction PSP) é um problema computacionalmente complexo. Para tratar esse problema, modelos simplificados de proteínas, como o Modelo HP, têm sido empregados para representar as conformações e Algoritmos Evolutivos (AEs) são utilizados na busca por soluções adequadas para PSP. Entretanto, abordagens utilizando AEs muitas vezes não tratam adequadamente as soluções geradas, prejudicando o desempenho da busca. Neste trabalho, é apresentada uma formulação multiobjetivo para PSP em Modelo HP, de modo a avaliar de forma mais robusta as conformações produzidas combinando uma avaliação baseada no número de contatos hidrofóbicos com a distância entre os monômeros. Foi adotado o Algoritmo Evolutivo Multiobjetivo em Tabelas (AEMT) a fim de otimizar essas métricas. O algoritmo pode adequadamente explorar o espaço de busca com pequeno número de indivíduos. Como consequência, o total de avaliações da função objetivo é significativamente reduzido, gerando um método para PSP utilizando Modelo HP mais rápido e robustoProtein Structure Prediction (PSP) is a computationally complex problem. To overcome this drawback, simplified models of protein structures, such as the HP Model, together with Evolutionary Algorithms (EAs) have been investigated in order to find appropriate solutions for PSP. EAs with the HP Model have shown interesting results, however, they do not adequately evaluate potential solutions by using only the usual metric of hydrophobic contacts, hamming the performance of the algorithm. In this work, we present a multi-objective approach for PSP using HP Model that performs a better evaluation of the solutions by combining the evaluation based on the number of hydrophobic contacts with the distance among the hydrophobic amino acids. We employ a Multi-objective Evolutionary Algorithm based on Sub-population Tables (MEAT) to deal with these two metrics. MEAT can adequately explore the search space with relatively low number of individuals. As a consequence, the total assessments of the objective function is significantly reduced generating a method for PSP using HP Model that is faster and more robus