Português English
Contato

Dissertação de Pablo Felipe Leonhart


Detalhes do Evento


Aluno: Pablo Felipe Leonhart
Orientador: Prof. Dr. Marcio Dorn

Título: Um Algoritimo Multimemético Auto-Adaptativo para o problema de Atracamento Molecular
Linha de Pesquisa: Algoritmos e Otimização

Data: 02/05/2019
Hora: 10h
Local: Prédio 43412 – Sala 216 – Instituto de Informática UFRGS

Banca Examinadora:
Prof. Dr. Joel Luis Carbonera (UFRGS/INF)
Profª. Drª. Luciana Salete Buriol (UFRGS)
Prof. Dr. Hugo Verli (UFRGS/PPGBCM)

Presidente da Banca: Prof. Dr. Marcio Dorn

Resumo: Atracamento Molecular é uma metodologia que lida com o problema de prever a liga- ção não covalente 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 meta-heurí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 Multimé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 mo- delo 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 exis- tentes 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 estru- turas 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.

Palavras-chave: Otimização. Algoritmos Multimeméticos. Algoritmos Auto-adaptativos. Atracamento Molecular. Bioinformática Estrutural.