Algoritmo genético híbrido com meta-heurísticas e aprendizado por reforço para alinhamento múltiplo de sequências

Abstract

O alinhamento múltiplo de sequências é uma das tarefas mais importantes dentro do campo da bioinformática, sendo usado para diversos tipos de análises biológicas, como a de função e estrutura de proteínas desconhecidas, design de drogas e estudos evolucionários. A literatura apresenta diversas estratégias para a realização de um alinhamento com qualidade biológica significante, sendo o algoritmo genético um dos mais usados devido à sua adaptabilidade. Porém, apesar dos bons resultados produzidos, o algoritmo sofre com o chamado problema de máximo local, fazendo com que a solução final seja um alinhamento que ainda pode ser melhorado. Dessa forma, o presente trabalho propõe a modelagem e implementação de uma estratégia híbrida entre o algoritmo genético, meta-heurísticas conhecidas da área e técnicas de aprendizado de máquina por reforço, com o objetivo de amenizar essa dificuldade. Com os resultados obtidos, demonstra-se a eficácia da estratégia proposta em amenizar consideravelmente o problema de máximo local, produzindo resultados com ótima significância biológica, semelhante às principais ferramentas da área, como Clustal Omega e Kalign.

The multiple sequence alignment is one of the most important tasks in bioinformatics, being used for different types of biological analysis such as the function and structure of unknown proteins, drugs design and evolutionary studies. There are several distinct strategies to get an alignment with significant biological quality, being the genetic algorithm one of the most used due to its adaptability. However, it suffers with the local maximum problem, causing the final solution to be an alignment that could be improved. Thus, this work proposes the modelling and implementation of a new hybrid method between genetic algorithm, well-known metaheuristics and machine reinforcement learning techniques as a way to smooth this problem. The results demonstrate the efficacy of the proposed strategy in mitigating considerably the local optima problem, achieving alignments with great biological significance, which are comparable with leading state-of-art tools, like Clustal Omega and Kalign.