Heurísticas para Problemas de Rearranjo de Genomas com Genes Multiplicados - Siqueira, Gabriel; Oliveira, Andre Rodrigues; Dias, Zanoni (Anais do Concurso de Teses e Dissertações da SBC (CTD-SBC); 2022: Anais do XXXV Concurso de Teses e DissertaçõesDO - 10.5753/ctd.2022.222522, 2022)
Um dos objetivos dos problemas de rearranjo de genomas consiste em estimar a distância evolutiva entre genomas de diferentes espécies utilizando eventos de rearranjo, mutações capazes de alterar a sequência genética dos genomas. Diferentes problemas de rearranjo podem ser definidos de acordo com os eventos utilizados e as características dos genomas considerados. O objetivo do trabalho foi o desenvolvimento de heurísticas para resolver problemas de rearranjo de genomas considerando genes multiplicados e os eventos de rearranjo de reversão e transposição. Desenvolvemos heurísticas baseadas em técnicas amplamente adotadas para problemas de otimização combinatória, como Busca Local, Algoritmos Genéticos e GRASP. Nos testes realizados, verificamos que as distâncias obtidas pelas heurísticas propostas são menores que as distâncias obtidas por algoritmos da literatura.