Algoritmo para Alinhamento de Sequências em Grafos de Sequências com Economia de Espaço - Gimenez, Thayná A.; Rocha, Lucas B.; Adi, Said Sadique; Araujo, Eloi (Anais do Encontro de Teoria da Computação (ETC); 2026: Anais do XI Encontro de Teoria da Computação, 2026)
Sequências biológicas obtidas de múltiplos indivíduos podem ser representadas por grafos de sequências, nos quais um alinhamento corresponde a um passeio no grafo que representa uma sequência s. Trabalhos anteriores apresentam um algoritmo com tempo O(V + mE) e espaço O(√m·V), em que m é o comprimento de s e V e E correspondem aos conjuntos de vértices e arcos do grafo. Entretanto, seu alto consumo de memória pode limitar aplicações práticas. Neste trabalho, propomos uma variação que aumenta o tempo por um fator O(log m) e reduz o espaço para O(V + E + m).