Um algoritmo multimemético auto-adaptativo para o problema de atracamento molecular

Abstract

Atracamento Molecular é uma metodologia que lida com o problema de prever a ligação de um receptor e um ligante em um nível atômico para formar um complexo estável. Como o espaço de busca de possíveis conformações de ligação é vasto, este problema é classificado na teoria da complexidade computacional como um problema NP-difícil. Por conta da alta complexidade, os métodos exatos não são eficientes e várias metaheurísticas têm sido propostas. No entanto, esses métodos são muito dependentes das configurações de parâmetros e das definições do mecanismo de pesquisa, o que requer abordagens capazes de se adaptarem automaticamente ao longo do processo de otimização. Nesta dissertação, é apresentado um novo modelo de coordenação auto-adaptativa de operadores de busca local em um Algoritmo Multimemético para lidar com o problema de Atracamento Molecular. A abordagem é baseada em uma variante do Biased Random Key Genetic Algorithm (BRKGA), funcionando como um operador de busca global, aprimorado com quatro algoritmos de busca local: Best Improvement, First Improvement, Stochastic Hill Descent, e Simulated Annealing. O algoritmo também engloba um modelo de discretização baseado em pequenos cubos para manter diversa a população de soluções. O mecanismo de auto-adaptação ocorre na escolha de qual método de busca local deve ser aplicado durante a execução e, também, no ajuste do parâmetro de raio de perturbação, que representa o quanto a solução é modificada em cada iteração do processo de busca local. Uma nova função de probabilidades também é apresentada, como parte do núcleo de auto-adaptação, para medir o custo-benefício de cada operador de busca local, e assim guiar o processo de busca. O algoritmo multimemético foi testado em um conjunto composto por 16 estruturas baseadas na HIV-protease e comparado com ferramentas existentes na literatura: AutoDock Vina, DockThor e jMetal. Os resultados obtidos mostram que a abordagem pode predizer a ligação de complexos com conformação similar a estruturas conhecidas, em termos de Root-Mean-Square Deviation. Testes estatísticos indicam que o algoritmo apresenta melhores resultados quando comparado a uma abordagem não memética e não adaptativa, e é competitivo com os métodos tradicionais do estado da arte.

Molecular Docking is a methodology that deals with the problem of predicting binding of a receptor and a ligand at an atomic level to form a stable complex. Because the search space of possible binding conformations is vast, this problem is classified in computational complexity theory as an NP-difficult problem. Because of the high complexity, the exact methods are not efficient, and several metaheuristics have been proposed. However, these methods are very dependent on parameter settings and search mechanism definitions, which requires approaches that can automatically adapt throughout the optimization process. In this dissertation, a new model of self-adaptive coordination of local search operators is presented in a Multimemetic Algorithm to deal with the problem of Molecular Docking. The approach is based on a variant of the Biased Random Key Genetic Algorithm (BRKGA), running as a global search operator, enhanced with four local search algorithms: Best Improvement, First Improvement, Stochastic Hill Descent, and Simulated Annealing. The algorithm also encompasses a small cube-based discretization model to keep the population of solutions diverse. The self-adaptation mechanism occurs in the choice of which local search method should be applied during execution and also in the perturbation radius parameter setting, which represents how much the solution is modified in each iteration of the local search process. A new probability function is also presented, as part of the self-adaptation core, to measure the cost-effectiveness of each local search operator, and thus guide the search process. The multimemetic algorithm was tested in a set consisting of 16 structures based on HIV-protease and compared with existing tools in the literature: AutoDock Vina, DockThor and jMetal. The results show that the approach can predict the binding of complexes with conformation similar to known structures in terms of Root-Mean-Square Deviation. Statistical tests indicate that the algorithm presents better results when compared to a non-memetic and non-adaptive approach, and is competitive with traditional state-of-the-art methods.