Heurísticas para o Problema do Alinhamento de Sequências em Grafos de Sequência sob a Distância de Edição

Abstract

In Computational Biology, the alignment and comparison of genetic sequences is a recurring problem. In the traditional approach, a reference sequence is used, however, this methodology can introduce significant biases, given that such a reference is inherently incapable of representing all possible variations. In this scenario, sequence graphs emerge as a robust data structure capable of consolidating multiple sequences and their respective variations into a single representation. Aligning a sequence to a sequence graph consists of identifying a path in the graph that induces a sequence that is as close as possible to the input sequence. This problem is known in the literature as the Sequence Graph Alignment Problem (SGAP) and it is known to be NP-complete. In the present study, two heuristics for this problem are proposed, implemented in C++ and evaluated on artificial test cases. The results obtained corroborate the effectiveness of the approach and indicate its potential for application in real world scenarios.