Ordenação por translocação de genomas sem sinal utilizando algoritmos genéticos

Dissertação (mestrado)—Universidade de Brasília, Instituto de Ciências Exatas, Departamento de Ciência da Computação, Programa de Pós-Graducação em Informática, 2016.

Translocações são usadas para mensurar a distância evolutiva entre espécies. Do ponto de vista biológico dois tipos de genomas tem recebido atenção: genomas com e sem sinal. Ao considerar genomas com sinal, computar a distância mínima de translocações é linear enquanto que o caso sem sinal é NP-difícil. Propõem-se algoritmos genéticos (AGs) para resolver o problema de distância de translocação entre genomas sem sinal. A abordagem, consiste em utilizar uma população composta por indivíduos representando genomas com sinal obtidos de um genoma sem sinal provido como entrada. A solução de cada indivíduo é também uma solução admissível para o genoma dado. A função de aptidão utilizada, que é a distância para genomas com sinal, é computada linearmente com um algoritmo proposto por Bergeron et al. O AG baseado nessa abordagem foi aprimorado com duas técnicas de otimização: memética e aprendizagem baseada em oposição. Além disso, foram propostas paralelizações do AG memético buscando diminuir o tempo de processamento assim como melhorar a precisão. A qualidade dos resultados foi validada utilizando uma implementação de um algoritmo de raio de aproximação 1.5+" recentemente proposto por Cui et al. Experimentos foram realizados tomando como entrada genomas sintéticos e gerados a partir de dados biológicos. Os AGs forneceram melhores resultados que o algoritmo de controle de qualidade. As paralelizações apresentaram melhoras tanto no tempo de execução quanto na precisão dos resultados. Utilizou-se o teste de hipóteses de Wilcoxon a fim de verificar a significância estatística das melhorias fornecidas pelos AGs aprimorados em relação àquelas fornecidas pelo AG básico. Desta análise foi possível identificar que o AG memético provê resultados diferentes (melhores) que o AG básico, e que este último e o AG com aprendizagem baseada em oposição não apresentam nenhuma diferença significativa. O teste foi também aplicado para comparar as soluções das paralelizações confirmando que existem aprimoramentos dos resultados comparados com o AG memético. _______________________________________________________________________________________________ ABSTRACT

Translocations are used to measure the evolutionary distance between species. From a biological point of view two types of genomes have received attention: signed and unsigned genomes. When considering signed genomes, the problem can be solved in linear time, while, in the case of unsigned genomes the problem was shown to be NP-hard. Genetic algorithms (GAs) are proposed to solve the translocation distance problem between unsigned genomes. The approach consists in using a population composed of individuals representing signed genomes obtained from a given unsigned genome provided as input. The solution of each individual is also an admissible solution to the given genome. The fitness function used, which is the distance for signed genome, is computed linearly with an algorithm proposed by Bergeron et al. The GA based on this approach has been enhanced with two optimization techniques: memetic and opposition based learning. Also, parallelizations of the GA embedded with memetic were proposed seeking to improve both running time as the accuracy of results. The quality of the results was verified using an implementation of a 1.5+"-approximation algorithm recently proposed by Cui et al. Experiments were performed taking as input synthetic genomes and genomes generated from biological data. The GAs provided better results than the quality control algorithm. The parallelizations showed improvements both regarding runtime as well as accuracy. A statistical analysis based on the Wilcoxon test was performed to check if the improvements in the solutions provided by enhanced GAs compared to those provided by the basic GA have some significance. This analysis can identify that the GA embedded with the technical memetic provides different (better) results than GA and that the results provided by the GA embedded with opposition based learning presents no significant difference. The test was also performed to compare the solutions of the parallelizations confirming that there are improvements of the results regarding the GA embedded memetic.