Uma Metaheurística VNS para o Problema de Alinhamento Sequência-Grafo com Modificação de Rótulos

Este trabalho aborda o Problema de Alinhamento Sequência-Grafo com Modificação de Rótulos, um problema NP-difícil em que o objetivo consiste em encontrar um passeio em um grafo rotulado que reproduza uma sequência de consulta, minimizando as modificações necessárias nos rótulos originais dos vértices. Para isso, apresentamos uma formulação de Programação Linear Inteira e propomos uma metaheurística de Busca em Vizinhança Variável (VNS). Experimentos computacionais mostraram que o modelo exato resolve instâncias menores até a otimalidade, mas falha em grafos esparsos com consultas longas. Nesses cenários intratáveis, a VNS demonstrou alta robustez e competitividade, encontrando alinhamentos perfeitos e superando o melhor limitante superior da abordagem exata em mais de 35% nas instâncias mais complexas, consolidando-se como uma alternativa eficaz.