Published
ASM implemented in hardware to accelerate DNA alignment tools using FPGAs and HLS technology
ASM implementado en hardware para acelerar herramientas de alineación de ADN utilizando FPGAs y tecnología HLS
DOI:
https://doi.org/10.15446/ing.investig.119497Keywords:
Bioinformatics, DNA alignment, High-level synthesis, FPGA, ASM (en)Bioinformática, Alineación de ADN, Síntesis de alto nivel, FPGA, ASM (es)
Downloads
In bioinformatics, one of the main and most demanding operations is the alignment of millions of short DNA codes to reference strings of millions of nucleotides. The above is carried out by computer programs of high spatial and temporal complexity, requiring several days to complete an alignment project. Given the situation, researchers from all over the world have striven to find new algorithms or new ways of executing them, to reduce long processing times. This paper presents an FPGA acceleration of the Myers algorithm, frequently found in the filtering stage of sophisticated alignment programs. This algorithm rapidly performs approximate string matching by efficiently exploiting the bit-level parallelism in words of a conventional processor. The objective of this work is to find additional speed-up factors when implementing it on an alternate computing platform using high-level synthesis technology. The resulting hardware module can align variable-length strings to suit today's major sequencing technologies, uses very few FPGA resources, has a low latency of between 470 and 3720 clock cycles, and achieves speedups of 157x over the original ASM algorithm and 2.03x relative to the state-of-the-art Myers implementation in the EDLIB library, executed on a contemporary high-performance processor.
En bioinformática, una de las principales y más demandantes operaciones es la alineación de millones de códigos cortos de ADN a cadenas de referencia de millones de nucleótidos. Lo anterior se realiza por programas informáticos de elevada complejidad espacial y temporal, requiriendo varios días para culminar un proyecto de alineación. Ante el panorama, investigadores de todas partes del mundo se han esforzado en encontrar nuevos algoritmos o nuevas formas de ejecutar a éstos, para disminuir los largos tiempos de procesamiento. En este artículo se presenta la aceleración mediante FPGAs del algoritmo de Myers, encontrado frecuentemente en la etapa de filtrado de los programas de alineación más sofisticados. Este algoritmo realiza rápidamente el emparejamiento aproximado de cadenas al explotar eficientemente el paralelismo a nivel de bits en las palabras de un procesador convencional. El objetivo de este trabajo es encontrar factores adicionales de aceleración al implementarlo en una plataforma de cómputo alterno utilizando la tecnología de síntesis de alto nivel. El Módulo hardware resultante puede alinear cadenas de longitud variable adaptándose a las principales tecnologías de secuenciación actuales, utiliza muy pocos recursos del FPGA, tiene una baja latencia de entre 470 y 3720 ciclos de reloj, y logra factores de aceleración de 157x en relación al algoritmo ASM en su versión original y de 2.03x en relación a la implementación en el estado del arte del algoritmo de Myers en la librería EDLIB, ejecutados en un procesador contemporáneo de alto desempeño.
References
[1] M. Alser et al., “From molecules to genomic variations: Accelerating genome analysis via intelligent algorithms and architectures,” Comput. Struct. Biotechnol. J., vol. 20, pp. 4579-4599, 2022. https://doi.org/10.1016/j.csbj.2022.08.019
[2] B. Saada, T. Zhang, E. Siga, J. Zhang and M. Magalhães-Muniz, “Whole-genome alignment: methods, challenges, and future directions,” Appl. Sci., vol. 14, no. 11, 2024, Art. no. 4837. https://doi.org/10.3390/app14114837
[3] G. Myers, “A fast bit-vector algorithm for approximate string matching based on dynamic programming,” J. ACM, vol. 46, no. 3, pp. 395-415, 1999. https://doi.org/10.1145/316542.316550
[4] T. F. Smith and M. S. Waterman, “Identification of common molecular subsequences,” J. Mol. Biol., vol. 147, no. 1, pp. 195-197, 1981. https://doi.org/10.1016/0022-2836(81)90087-5
[5] S. B. Needleman and C. D. Wunsch, “A general method applicable to the search for similarities in the amino acid sequence of two proteins,” J. Mol. Biol., vol. 48, no. 3, pp. 443-453, 1970. https://doi.org/10.1016/0022-2836(70)90057-4
[6] H. Cheng et al., “BitMapper: an efficient all-mapper based on bit-vector computing,” BMC Bioinform., vol. 16, 2015, Art. no. 192. https://doi.org/10.1186/s12859-015-0626-9
[7] H. Zhang et al., “Fast alignment and preprocessing of chromatin profiles with Chromap,” Nat. Commun., vol. 12, no. 1, 2021, Art. no. 6566. https://doi.org/10.1038/s41467-021-26865-w
[8] E. Espinosa, R. Quislant, R. Larrosa and O. Plata, “Se-qMatcher: efficient genome sequence matching with AVX-512 extensions,” J. Supercomput., vol. 81, no. 1, 2025, Art. no. 355. https://doi.org/10.1007/s11227-024-06789-0
[9] D. Pacheco-Bautista, R. Carreño-Aguilera, I. Algredo-Badillo and M. Patiño-Ortiz, “Hardware acceleration of DNA read alignment programs: Challenges and opportu-nities,” Fractals, vol. 31, no. 7, 2023, Art. no. 2350097. https://doi.org/10.1142/S0218348X23500974
[10] Z. Liu, S. Zhang and H. Zhao, “Survey of hardware accel-eration of genomic analysis,” in Proc. IEEE 17th Int. Symp. Embedded Multicore/Many-Core Syst.-on-Chip (MCSoC), Kuala Lumpur, Malaysia, 2024, pp. 540-547. https://doi.org/10.1109/MCSoC64144.2024.00093
[11] S. Lahti and T. D. Hämäläinen, “High-level synthesis for FPGAs—a hardware engineer’s perspective,” IEEE Access, vol. 13, pp. 28574-28593, 2025. https://doi.org/10.1109/ACCESS.2025.3540320
[12] R. S. Molina, V. Gil-Costa, M. L. Crespo and G. Ramponi, “High-level synthesis hardware design for FPGA-based ac-celerators: Models, methodologies, and frameworks,” IEEE Access, vol. 10, pp. 90429-90455, 2022. https://doi.org/10.1109/ACCESS.2022.3201107
[13] M. Šošić and M. Šikić, “Edlib: a C/C++ library for fast, exact sequence alignment using edit dis-tance,” Bioinformatics, vol. 33, no. 9, pp. 1394-1395, 2017. https://doi.org/10.1093/bioinformatics/btw753
[14] A. Döring, D. Weese, T. Rausch and K. Reinert, “SeqAn an efficient, generic C++ library for sequence analysis,” BMC Bioinform., vol. 9, 2008, Art. no. 11. https://doi.org/10.1186/1471-2105-9-11
[15] J. Hoffmann, D. Zeckzer and M. Bogdan, “Using FPGAs to accelerate Myers bit-vector algorithm,” in Proc. 14th Medi-terranean Conf. Med. Biol. Eng. Comput. (MEDICON), Pa-phos, Cyprus, 2016, pp. 535-541. https://doi.org/10.1007/978-3-319-32703-7_104
[16] T. Wada, S. Funasaka, K. Nakano and Y. Ito, “A hybrid architecture for the approximate string matching on an FPGA,” in Proc. 5th Int. Symp. Comput. Netw. (CANDAR), Aomori, Japan, 2017, pp. 48-57. https://doi.org/10.1109/CANDAR.2017.61
[17] D. Pacheco-Bautista, R. Carreño-Aguilera, F. Aguilar-Acevedo and I. Algredo-Badillo, “Bit-vector-based hard-ware accelerator for DNA alignment tools,” J. Circuits Syst. Comput., vol. 30, no. 5, 2021, Art. no. 2150087. https://doi.org/10.1142/S0218126621500870
[18] L. Cai, Q. Wu, T. Tang, Z. Zhou and Y. Xu, “A design of FPGA acceleration system for Myers bit-vector based on OpenCL,” in Proc. Int. Conf. Intell. Informat. Biomed. Sci. (ICIIBMS), Shanghai, China, 2019, pp. 305-312. https://doi.org/10.1109/ICIIBMS46890.2019.8991468
[19] E. Espinosa, R. Álvarez, J. Miranda, R. Larrosa, M. Peón-Quirós, O. Plata and D. Atienza, “GeneTEK: Low-power, high-performance and scalable genome sequence matching in FPGAs,” 2025, arXiv:2509.01020. https://doi.org/10.48550/arXiv.2509.01020
[20] V. Y. Gudur, S. Maheshwari, S. Bhardwaj, A. Acharyya and R. Shafik, “Hardware-algorithm codesign for fast and energy efficient approximate string matching on FPGA for computational biology,” in Proc. 44th Annu. Int. Conf. IEEE Eng. Med. Biol. Soc. (EMBC), Glasgow, Scotland, United Kingdom, July 11-15, 2022, pp. 87-90. https://doi.org/10.1109/EMBC48229.2022.9870924
[21] D. Castells-Rufas et al., “OpenCL-based FPGA accelerator for semi-global approximate string matching using diago-nal bit-vectors,” in Proc. 31st Int. Conf. Field-Programmable Logic Appl. (FPL), Dresden, Germany, 2021, pp. 174-178. https://doi.org/10.1109/FPL53798.2021.00036
[22] K. Polonis, J. H. Blommel, A. E. Hughes, D. Spencer, J. A. Thompson and M. C. Schroeder, “Innovations in short-read sequencing technologies and their applications to clinical genomics,” Clin. Chem., vol. 71, no. 1, pp. 97-108, 2025. https://doi.org/10.1093/clinchem/hvae173
[23] J. C. Rolando, A. V. Melkonian, and D. R. Walt, “The present and future landscapes of molecular diagnostics,” Annu. Rev. Anal. Chem., vol. 17, no. 1, pp. 459-474, 2024. https://doi.org/10.1146/annurev-anchem-061622-015112
Dimensions
PlumX
Article abstract page views
Downloads
How to Cite
License
Copyright (c) 2026 Daniel Pacheco Bautista, Atziry Cardenas Jijón, Francisco Aguilar acevedo, Ignacio Algredo Badillo, Ricardo Carreño Aguilera
This work is licensed under a Creative Commons Attribution 4.0 International License.
The authors or holders of the copyright for each article hereby confer exclusive, limited and free authorization on the Universidad Nacional de Colombia's journal Ingeniería e Investigación concerning the aforementioned article which, once it has been evaluated and approved, will be submitted for publication, in line with the following items:
1. The version which has been corrected according to the evaluators' suggestions will be remitted and it will be made clear whether the aforementioned article is an unedited document regarding which the rights to be authorized are held and total responsibility will be assumed by the authors for the content of the work being submitted to Ingeniería e Investigación, the Universidad Nacional de Colombia and third-parties;
2. The authorization conferred on the journal will come into force from the date on which it is included in the respective volume and issue of Ingeniería e Investigación in the Open Journal Systems and on the journal's main page (https://revistas.unal.edu.co/index.php/ingeinv), as well as in different databases and indices in which the publication is indexed;
3. The authors authorize the Universidad Nacional de Colombia's journal Ingeniería e Investigación to publish the document in whatever required format (printed, digital, electronic or whatsoever known or yet to be discovered form) and authorize Ingeniería e Investigación to include the work in any indices and/or search engines deemed necessary for promoting its diffusion;
4. The authors accept that such authorization is given free of charge and they, therefore, waive any right to receive remuneration from the publication, distribution, public communication and any use whatsoever referred to in the terms of this authorization.
