Explorando a diversidade em algoritmos genéticos distribuídos para o problema de predição de estrutura tridimensional de proteínas

Abstract

Conhecer a estrutura tridimensional de uma proteína é um passo fundamental para se determinar seu papel biológico. Ainda que o problema de predição da estrutura de proteínas permaneça sem solução definitiva, diversos métodos foram propostos nos últimos anos no intuito de solucioná-lo. Como principal alternativa, meta-heurísticas como o Algoritmo Genético e versões similares vem sendo aplicadas ao problema. Apesar de eficientes em diversas tarefas, estes algoritmos encontram alguns obstáculos ao tratarem o problema, principalmente devido à convergência prematura. Isso ocorre quando a população do algoritmo perde diversidade, convergindo então em valores não satisfatórios. Muitas maneiras de lidar com este problema foram desenvolvidas. O Algoritmo Genético Distribuído se divide em múltiplas populações, de modo a desacelerar a convergência global. Nesta dissertação, um Algoritmo Genético Distribuído com controle de diversidade é apresentado. Para tal, uma nova política de migração foi proposta, a qual busca manter e explorar de maneira eficiente a diversidade populacional. Antes de aplicá-la ao problema de predição da estrutura de proteínas, uma série de testes foram realizados, com o objetivo de se obter a versão mais adequada ao problema. Em uma primeira etapa, esta nova política foi testada em conjunto com outras cinco políticas distintas, todas aplicadas no Algoritmo Genético canônico e no Biased Random-Key Genetic Algorithm (BRKGA), uma versão também baseada em diversidade. Os resultados apontam para um melhor desempenho da política proposta em relação às demais, principalmente combinada ao BRKGA. Na etapa seguinte, uma série de operadores genéticos foram propostos, no intuito de agregar informações específicas do problema à tomada de decisão. Além disso, utilizou-se também uma base de conhecimento experimental visando reduzir o espaço de busca conformacional. Como resultado, um novo método foi gerado (política proposta + BRKGA), incorporando novos operadores de inicialização baseado em conhecimento experimental, além de operadores de recombinação e mutação que utilizam informação da estrutura secundária. Por fim, este método foi comparado a outros dois que também fazem uso de informação da estrutura secundária e de bases de conhecimento. Os resultados apontam para um desempenho competitivo, se mostrando superior em diversos casos.

The knowledge of the three-dimensional structure of a protein is a key step in determining its biological role. Although the protein structure prediction problem remains without a definitive solution, several methods have been proposed in the last years aiming to solve it. As the main alternative, meta-heuristics such as the Genetic Algorithm and similar versions have been applied to the problem. Despite efficient in several tasks, these algorithms face some obstacles when dealing with this problem, mainly due to the premature convergence. This happens when the population of the algorithm loses diversity, converging to unsatisfactory values. Many ways of dealing with this problem have been developed. The Distributed Genetic Algorithm seeks to divide the population into multiple groups to slow global convergence. In this dissertation, a Distributed Genetic Algorithm with diversity control is presented. To this end, a new migration policy has been developed, in which it seeks not only to maintain but also to efficiently explore population diversity. Before applying it to the protein strucure prediction problem, several tests were performed, in order to obtain the most appropriate version of the method to the problem. In a first stage, this new policy was tested along with five other distinct policies, all applied in the Canonical Genetic Algorithm and the Biased Random-Key Genetic Algorithm (BRKGA), a version also based on diversity. The results point to a better performance of the proposed policy in relation to the others, mainly combined with BRKGA. In the next stage, a series of genetic operators were proposed, to aggregate specific information of the problem to the decision making. Also, an experimental knowledge base was used to reduce the conformational search space. As a result, a novel method (proposed policy + BRKGA) was generated, incorporating new initialization operators based on experimental knowledge, as well as recombination and mutation operators that use information from the secondary structure of proteins. Finally, this method was compared to other two methods that also make use of secondary structure information and knowledge bases. The results point to a competitive performance, proving superior in several cases.