Um novo algoritmo 1.375-aproximativo baseado em grupos de permutações para o Problema da Ordenação por Transposições

Abstract

O Problema da Ordenação por Transposições (SBT, sigla dos termos em língua inglesa Sorting By Transpositions) é um problema clássico em rearranjos de genoma. Em 2012, Bulteau, Fertin e Rusu provaram que o SBT é N P-difícil e o melhor algoritmo de aproximação com uma razão de 1.375 foi proposto em 2006 por Elias e Hartman. Seu algoritmo emprega simplificação, uma técnica usada para transformar uma permutação de entrada π em uma permutação simples πˆ, presumivelmente mais fácil de lidar. A permutação πˆ é obtida inserindo novos símbolos em π de forma que o limite inferior da distância de transposição de π seja mantido em πˆ. A simplificação garantidamente mantém o limite inferior, mas não a distância de transposição. A sequência de transposições que ordena πˆ pode ser “imitada” para ordenar π. Nesta tese, primeiro, mostramos que o algoritmo de Elias e Hartman (Algoritmo EH) pode requerer uma transposição extra acima da razão de aproximação de 1.375, dependendo de como a permutação de entrada é simplificada. Em seguida, usando uma abordagem algébrica, propomos um novo limite superior para a distância de transposição e um novo algoritmo de aproximação de 1.375 para o SBT, que não emprega simplificação e que garante a razão de aproximação de 1.375 para todo o grupo simétrico Sn. Implementamos o Algoritmo EH e o algoritmo proposto nesta tese. Em relação à implementação do Algoritmo EH, duas novas falhas foram identificadas e precisaram ser corrigidas. Testamos ambos os algoritmos com todas as permutações de tamanho n, 2 ≤ n ≤ 12. Os resultados mostraram que o Algoritmo EH excede a razão de aproximação de 1.375 para permutações com tamanho maior que 7. Em seguida, investigamos o desempenho de ambas as implementações em permutações longas de comprimento máximo 500. Por fim, apresentamos os resultados obtidos de uma investigação visando encontrar uma solução aproximada para o SBT, com razão inferior a 1.375. Ao procurar por resultados que permitissem o desenvolvimento de uma solução 1.33¯3-aproximativa, apenas não foram encontradas sequências de transposições, proporcionando essa razão, para 11 casos, de um universo de ≈ 545.000. A conclusão da investigação foi de que, para baixar a razão de aproximação 1.375, será necessário buscar por sequências de transposições muito longas, o que pode ser impraticável, dependendo dos recursos computacionais disponíveis e da técnica utilizada.