A VNS Metaheuristic for the Sequence-to-Graph Alignment Problem with Label Modification

This paper addresses the Sequence-to-Graph Alignment Problem with Vertex Label Modification, an NP-hard problem where the objective is to find a walk in a labeled graph that matches a query sequence while minimizing the required alterations to the original vertex labels. To this end, we show an Integer Linear Programming (ILP) formulation and propose a Variable Neighborhood Search (VNS) metaheuristic. Computational experiments revealed that the exact model solves smaller instances to optimality but fails on sparse graphs with long queries. In these intractable scenarios, the VNS demonstrated high robustness and competitiveness, finding perfect alignments and outperforming the exact approach's best upper bound by over 35% in the hardest instances, establishing itself as a highly effective alternative.