An Integer Linear Programming and Biased Random-Key Genetic Algorithm for the Sequence-to-Graph Alignment Problem with Vertex Label Modification

• Gabriel Pereira Falcão UFMS
• Erick Rodrigues de Lemos Ribeiro UFMS
• Matheus Amorim Martins UFMS
• Eduardo Theodoro Bogue UFMS
• Said Sadique Adi UFMS

DOI: https://doi.org/10.5753/eniac.2026.31457

Resumo

This paper addresses the Sequence-to-Graph Alignment Problem with Vertex Label Modification, where vertex labels may be altered, shifting the objective to minimizing the modification cost for an exact alignment. To tackle the computational complexity of this problem, we propose an exact Integer Linear Programming (ILP) formulation and a Biased Random-Key Genetic Algorithm (BRKGA) metaheuristic. Computational experiments reveal the complementarity between the methods: the ILP efficiently solves moderately sized instances to optimality, while the BRKGA excels in the most challenging scenarios (large, sparse graphs with long queries), improving the best-known upper bounds and reducing alignment costs by more than 50% relative to the ILP solutions.

Referências

Alba, E. and Tomassini, M. (2002). Parallelism and evolutionary algorithms. IEEE transactions on evolutionary computation, 6(5):443–462.

Amir, A., Lewenstein, M., and Lewenstein, N. (2000). Pattern matching in hypertext. Journal of Algorithms, 35(1):82–99.

Bean, J. C. (1994). Genetic algorithms and random keys for sequencing and optimization. ORSA journal on computing, 6(2):154–160.

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(6):682–688.

Dilthey, A. T., Gourraud, P.-A., Mentzer, A. J., Cereb, N., Iqbal, Z., and McVean, G. (2016). High-accuracy hla type inference from whole-genome sequencing data using population reference graphs. PLoS computational biology, 12(10):e1005151.

Erdős, P. and Rényi, A. (1959). On random graphs i. Publicationes Mathematicae Debrecen, 6:290–297.

Garrison, E., Sirén, J., Novak, A. M., Hickey, G., Eizenga, J. M., Dawson, E. T., Jones, W., Garg, S., Markello, C., Lin, M. F., et al. (2018). Variation graph toolkit improves read mapping by representing genetic variation in the reference. Nature biotechnology, 36(9):875–879.

Gonçalves, J. F. and Resende, M. G. (2011). Biased random-key genetic algorithms for combinatorial optimization. Journal of Heuristics, 17(5):487–525.

Ivanov, P., Bichsel, B., Mustafa, H., Kahles, A., Rätsch, G., and Vechev, M. (2020). Astarix: Fast and optimal sequence-to-graph alignment. In International Conference on Research in Computational Molecular Biology, pages 104–119. Springer.

Jain, C., Misra, S., Zhang, H., Dilthey, A., and Aluru, S. (2019). Accelerating sequence alignment to graphs. In 2019 IEEE International Parallel and Distributed Processing Symposium (IPDPS), pages 451–461. IEEE.

Jain, C., Zhang, H., Gao, Y., and Aluru, S. (2020). On the complexity of sequence-to-graph alignment. Journal of Computational Biology, 27(4):640–654.

Jiménez-Blanco, A., López-Villellas, L., Moure, J. C., Moreto, M., and Marco-Sola, S. (2026). Theseus: Fast and optimal affine-gap sequence-to-graph alignment. bioRxiv, pages 2026–02.

Londe, M. A., Pessoa, L. S., Andrade, C. E., and Resende, M. G. (2024). Early years of biased random-key genetic algorithms: a systematic review. Journal of Global Optimization, pages 1–24.

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. (2020). Graphaligner: rapid and versatile sequence-to-graph alignment. Genome biology, 21(1):253.

Vaser, R., Sović, I., Nagarajan, N., and Šikić, M. (2017). Fast and accurate de novo genome assembly from long uncorrected reads. Genome research, 27(5):737–746.