Ordenação por reversões de permutações sem sinal usando uma abordagem de algoritmos genéticos

Abstract

Ordenação de permutações por reversões é um dos problemas mais desafiantes relacionados com a análise da distância evolutiva entre organis- mos, cujos resultados podem ser usados na construção de árvores filogenéticas baseadas nesta distância. No caso de permutações com sinal, o problema pode ser resolvido em tempo linear, porém, no caso de permutações sem sinal o problema é mais complexo, já que foi demonstrado ser NP-difícil e com uma questão ainda em aberto: se é ou não NP completo; este foi o motivo pelo qual foram propostos diversos algoritmos de aproximação e de computação evolucionária. Neste trabalho, é proposto um algoritmo genético(AG) padrão para resolver o problema de ordenação de permutações sem sinal. Este enfoque está baseado no método proposto por Auyeung e Abraham, que usa soluções exatas para o caso de permutações com sinal, para resolver a versão do problema com permutações sem sinal. Adicionalmente, foi proposto um algoritmo genético melhorado (hibrido), que usa uma heurística de eliminação de pontos de quebra em gerações iniciais. Diversos experimentos foram feitos tomando como entrada permutações gera- das aleatoriamente, escolhendo um elemento aleatório sobre um conjunto de números, ou aplicando reversões aleatórias sobre uma permutação ordenada. Ademais, foram usadas permutações de Gollan as quais sabemos que podem ser ordenadas usando n — 1 reversões, onde n é o comprimento da permutação. Desde que muitos enfoques de AG's usaram mecanismos de controle impreci- sos para validar a precisão das suas respostas, foi necessário um grande esforço para desenvolver uma algoritmo de aproximação confiável. Dando origem a um desenvolvimento teórico baseado no algoritmo de raio de aproximação 1.5 proposto por Christie, e sua posterior implementação. Os experimentos mostraram que ambos AG fornecem respostas que são melhores do que aquelas fornecidas por métodos relacionados prévios, tanto como os que são fornecidos pelo algoritmo de raio de aproximação 1.5 corrigido. ______________________________________________________________________________ ABSTRACT

Sorting permutations by reversals is one of the most challenging problems related to the analysis of the evolutionary distance between organisms, whose results can be used in the construction of phylogenetic trees bases on this distance. In the case of signed permutations, the problem can be solved in linear time, however in the case of unsigned permutations the problem is more complex, since it was shown to be NP-hard and it is unknown whether it is NP-complete or not; this fact motivated the proposal of several approximation, and evolutionary computing algorithms. In this work, we propose genetic algorithms (GA) to solve the problem of sorting unsigned permutations. Initially, we propose a standard GA approach based on the method proposed by Auyeung and Abraham, which uses exact polynomial solutions for the case of signed permutations, for solving the problem with unsigned permutations. Further, we propose an improved genetic algorithm, which uses the heuristic of elimination of break points in early generations and then the standard approach. Several experiments were made using as inputs permutations generated randomly by choosing a random element over a set of numbers, and by applying random reversals over an sorted permutation. Also, was used Gollan permutations that it's well-known that can be sorted by n 1 reversals, where n is the length of the permutation. Since previous GA approaches have used imprecise control mechanisms for checking the accuracy of their answers, a great deal of e ort was necessary in order to develop a reliable approximate algorithm. This gave rise to a theoretical development based on the well-known Christie's 1.5 ratio approximation algorithm and its further implementation. Experiments showed that both AG approaches compute answers that are better than the ones computed by previous approaches as well as than the ones computed with the adjusted correct 1.5 approximation algorithm.