Algoritmo genético adaptativo e paralelo para seleção de polimorfismos de nucleotídeo único representativos

Abstract

Polimorfismos de Nucleotídeo Único (SNPs) são uma ferramenta promissora nos estudos de doenças. Contudo, a análise de todos os SNPs do genoma humano é uma tarefa custosa computacionalmente. Neste cenário, descobriu-se a possibilidade de utilizar um subconjunto de SNPs, chamado tag SNPs, que fosse representativo o suficiente para ser utilizado em estudos, sem que houvesse necessidade de lidar com o conjunto completo. Devido à sua alta complexidade, diversas abordagens foram propostas para lidar com este problema a partir de meta-heurísticas, como os Algoritmos Genéticos. Contudo, dentro do processo evolutivo destes algoritmos, as soluções são influenciadas pelo contexto do problema, ao qual se atribuiu o nome de pressão seletiva e que pode impactar de maneira negativa os resultados encontrados. Apesar da pressão seletiva poder ser controlada, o processamento adicional para o cálculo destes métodos pode acarretar aumento do custo computacional, o que pode inviabilizar sua aplicação. Desta forma, a contribuição científica deste trabalho está na proposição de um método paralelo para seleção de SNPs representativos baseado em algoritmos genéticos com controle de pressão seletiva que, quando comparado aos demais da literatura, apresenta maior diversidade de indivíduos nas populações, maior velocidade de convergência e, consequentemente, melhor resultado das soluções encontradas pelo algoritmo. Os resultados indicaram que o algoritmo desenvolvido foi capaz de reduzir em 27% a quantidade de iterações até a convergência, assim como aumentar o valor de aptidão das soluções em 11%. Adicionalmente, o algoritmo foi capaz de lidar com maiores volumes de dados e apresenta uma taxa de crescimento do tempo de processamento 3,7 vezes menor do que um algoritmo sequencial tradicional.

Single Nucleotide Polymorphisms (SNPs) work as a promising tool to support the study of diseases. Despite this fact, the analysis of all SNPs from human genome is very expensive task from the computational perspective. In that point, genetic related researches found the existence of a small subset of SNPs, named tag SNPs, that can be used to handle the studies, rather than use the complete set of SNPs. Since the problem of finding this subset is a complex task, different metaheuristics were proposed to deal with it, such as Genetic Algorithms. However, a feature named selective pressure can negatively affect the results of these algorithms during the evolutionary process. Even though this feature can be controlled, the additional processing computation performed to deal with it can make its application impracticable. In that sense, the scientific contribution of this work is the proposition of a parallel strategy to find tag SNPs based on genetic algorithms with selective pressure control. This algorithm present higher diversity rate of individuals inside population, higher convergency speed e better solution when compared to related works. The experiments showed that the develop algorithm was able to reduce the number of generations performed until convergence in 27%, as well as increase the fitness of the solutions in 11%. The results also showed that the algorithm is more efficient to deal with a higher volume of data, and present an increasing rate 3.7 times lower than the sequential approach.