Uma Heurística para o Problema de Alinhamento de Sequência em Grafos de Sequência sob a Distância de Hamming

Abstract

A relevant problem in Computational Biology is mapping and comparing sequences, often using a high-quality reference sequence. However, such reference sequences are often biased, representing only a subset of all possibilities. To address this, multiple sequences are represented using more robust structures, such as sequence graphs, onto which sequences can be mapped. More formally, given as input a sequence s and a sequence graph G, the goal is to find a path in G that induces a sequence as similar as possible to s. This definition leads to the Sequence Graph Alignment Problem (SGAP). In this study, we propose a heuristic for the SGAP, under the Hamming Distance, designed to solve a variant of the problem where the goal is to find a path in the sequence graph G. The proposed heuristic demonstrated efficiency and yielded promising results on an artificial data set.