Algoritmo para Alinhamento de Sequências em Grafos de Sequências com Economia de Espaço
Resumo
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).
Palavras-chave:
Grafo de sequências, alinhamento de sequências
Referências
Amir, A., Lewenstein, M., and Lewenstein, N. (2000). Pattern matching in hypertext. Journal of Algorithms, 35(1):82–99.
Dilthey, A., Cox, C., Iqbal, Z., Nelson, M. R., and McVean, G. (2015). Improved genome inference in the mhc using a population reference graph. Nature Genetics, 47:682–688.
Hirschberg, D. S. (1975). A linear space algorithm for computing maximal common subsequences. Communications of the ACM, 18(6):341–343.
Ivanov, P., Bichsel, B., Mustafa, H., Kahles, A., Rätsch, G., and Vechev, M. (2020). Astarix: Fast and optimal sequence-to-graph alignment. In Research in Computational Molecular Biology, pages 104–119, Cham. Springer International Publishing.
Jain, C., Zhang, H., and Aluru, S. (2020). A comprehensive evaluation of long read error correction methods. BMC Genomics, 21:889.
Jain, C., Zhang, H., Gao, Y., and Aluru, S. (2019). On the complexity of sequence to graph alignment. In Cowen, L. J., editor, Research in Computational Molecular Biology, pages 85–100, Cham. Springer International Publishing.
Kavya, V. N. S., Tayal, K., Srinivasan, R., and Sivadasan, N. (2019). Sequence alignment on directed graphs. Journal of Computational Biology, 26(1):53–67.
Navarro, G. (2000). Improved approximate pattern matching on hypertext. Theoretical Computer Science, 237(1):455–463.
Paten, B., Novak, A. M., Eizenga, J. M., and Garrison, E. (2017). Genome graphs and the evolution of genome inference. Genome Research, 27(5):665–676.
Rautiainen, M. and Marschall, T. (2017). Aligning sequences to general graphs in O(V + mE) time. bioRxiv, page 216127.
Rautiainen, M. and Marschall, T. (2020). Graphaligner: rapid and versatile sequence-to-graph alignment. Genome Biology, 21:253.
Secomandi, S., Guido Roberto Gallo, R. R., Fernandes, C. R., Jarvis, E. D., Gianfranceschi, A. B.-A. L., and Formenti, G. (2025). Pangenome graphs and their applications in biodiversity genomics. Nature Genetics, 57:13–26.
Uliano-Silva, M., Gabriel R. N. Ferreira, J., Krasheninnikova, K., of Life Consortium, D. T., Formenti, G., Abueg, L., Torrance, J., Myers, E. W., Durbin, R., Blaxter, M., and McCarthy, S. A. (2023). Mitohifi: a python pipeline for mitochondrial genome assembly from pacbio high fidelity reads. BMC Bioinformatics, 24:288.
Yang, A., Troup, M., and Ho, J. W. (2017). Scalability and validation of big data bioinformatics software. Computational and Structural Biotechnology Journal, 15:379–386.
Dilthey, A., Cox, C., Iqbal, Z., Nelson, M. R., and McVean, G. (2015). Improved genome inference in the mhc using a population reference graph. Nature Genetics, 47:682–688.
Hirschberg, D. S. (1975). A linear space algorithm for computing maximal common subsequences. Communications of the ACM, 18(6):341–343.
Ivanov, P., Bichsel, B., Mustafa, H., Kahles, A., Rätsch, G., and Vechev, M. (2020). Astarix: Fast and optimal sequence-to-graph alignment. In Research in Computational Molecular Biology, pages 104–119, Cham. Springer International Publishing.
Jain, C., Zhang, H., and Aluru, S. (2020). A comprehensive evaluation of long read error correction methods. BMC Genomics, 21:889.
Jain, C., Zhang, H., Gao, Y., and Aluru, S. (2019). On the complexity of sequence to graph alignment. In Cowen, L. J., editor, Research in Computational Molecular Biology, pages 85–100, Cham. Springer International Publishing.
Kavya, V. N. S., Tayal, K., Srinivasan, R., and Sivadasan, N. (2019). Sequence alignment on directed graphs. Journal of Computational Biology, 26(1):53–67.
Navarro, G. (2000). Improved approximate pattern matching on hypertext. Theoretical Computer Science, 237(1):455–463.
Paten, B., Novak, A. M., Eizenga, J. M., and Garrison, E. (2017). Genome graphs and the evolution of genome inference. Genome Research, 27(5):665–676.
Rautiainen, M. and Marschall, T. (2017). Aligning sequences to general graphs in O(V + mE) time. bioRxiv, page 216127.
Rautiainen, M. and Marschall, T. (2020). Graphaligner: rapid and versatile sequence-to-graph alignment. Genome Biology, 21:253.
Secomandi, S., Guido Roberto Gallo, R. R., Fernandes, C. R., Jarvis, E. D., Gianfranceschi, A. B.-A. L., and Formenti, G. (2025). Pangenome graphs and their applications in biodiversity genomics. Nature Genetics, 57:13–26.
Uliano-Silva, M., Gabriel R. N. Ferreira, J., Krasheninnikova, K., of Life Consortium, D. T., Formenti, G., Abueg, L., Torrance, J., Myers, E. W., Durbin, R., Blaxter, M., and McCarthy, S. A. (2023). Mitohifi: a python pipeline for mitochondrial genome assembly from pacbio high fidelity reads. BMC Bioinformatics, 24:288.
Yang, A., Troup, M., and Ho, J. W. (2017). Scalability and validation of big data bioinformatics software. Computational and Structural Biotechnology Journal, 15:379–386.
Publicado
19/07/2026
Como Citar
GIMENEZ, Thayná A.; ROCHA, Lucas B.; ADI, Said Sadique; ARAUJO, Eloi.
Algoritmo para Alinhamento de Sequências em Grafos de Sequências com Economia de Espaço. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 11. , 2026, Gramado/RS.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2026
.
p. 21-25.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2026.21957.
