Hardware Acceleration of Minimap2 Genomic Sequence Alignment Algorithm
Authors: 
Jie Cheng, Lifu Hu, Wei Xu, Hanhua Chen, Tian XiaAuthors Info & Claims
Pages 887 - 897
Abstract
Sequence alignment, a crucial task in genome analysis for downstream applications such as mutation detection, faces challenges due to longer sequences and increased errors in the era of third-generation sequencing. This paper focuses on the optimization of Minimap2, a widely used alignment algorithm for mapping variable-length reads to extensive reference sequences. To enhance the algorithm’s performance, we introduce a novel approach leveraging FPGA technology to expedite the time-consuming extension step.
Our work addresses limitations in existing hardware implementations through innovative designs. The Cyclic Variable Logical Length (CVLL) method optimizes systolic arrays by reducing latency and resource waste. Additionally, we employ 2-bit variables to streamline backtracking direction recording, simplifying FPGA implementation and significantly reducing memory usage. We further enhance the system performance by incorporating the pipeline and multi-channel techniques.
Experimental results on the FX410QL FPGA platform demonstrate the notable speedups of our design, reaching a peak improvement of 2.84 × over CPU implementation, and achieving improvements compared to GPU implementation at various input lengths. Beyond algorithm acceleration, our design provides insights into enhancing genome data processing overall and implications for FPGA implementation on application-specific integrated circuits, addressing the growing gap between genome data generation and analysis.
References
[1]
Denis Bauer. 2011. Variant calling comparison CASAVA1. 8 and GATK. Nature Precedings (2011), 1–1.
[2]
Juechu Dong, Xueshen Liu, Harisankar Sadasivan, Sriranjani Sitaraman, and Satish Narayanasamy. 2024. mm2-gb: GPU Accelerated Minimap2 for Long Read DNA Mapping. bioRxiv (2024), 2024–03.
[3]
Zonghao Feng, Shuang Qiu, Lipeng Wang, and Qiong Luo. 2019. Accelerating long read alignment on three processors. In Proceedings of the 48th International Conference on Parallel Processing. Kyoto, Japan, 1–10.
[4]
David Gordon, John Huddleston, Mark JP Chaisson, Christopher M Hill, Zev N Kronenberg, Katherine M Munson, Maika Malig, Archana Raja, Ian Fiddes, LaDeana W Hillier, 2016. Long-read sequence assembly of the gorilla genome. Science 352, 6281 (2016), aae0344.
[5]
Osamu Gotoh. 1982. An improved algorithm for matching biological sequences. Journal of molecular biology 162, 3 (1982), 705–708.
[6]
Osamu Gotoh. 1990. Optimal sequence alignment allowing for long gaps. Bulletin of mathematical biology 52, 3 (1990), 359–373.
[7]
Licheng Guo, Jason Lau, Zhenyuan Ruan, Peng Wei, and Jason Cong. 2019. Hardware acceleration of long read pairwise overlapping in genome sequencing: A race between fpga and gpu. In 2019 IEEE 27th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM). IEEE, San Diego, CA, USA, 127–135.
[8]
Ltd. HangZhou FlySlice Technologies Co.2017. The introduction of FX410QL board. https://www.flyslice.com/page434?product_id=15.
[9]
Ernst Joachim Houtgast, Vlad-Mihai Sima, Koen Bertels, and Zaid Al-Ars. 2015. An FPGA-based systolic array to accelerate the BWA-MEM genomic mapping algorithm. In 2015 international conference on embedded computer systems: Architectures, modeling, and simulation (samos). IEEE, Samos, Greece, 221–227.
[10]
Ernst Joachim Houtgast, Vlad-Mihai Sima, Koen Bertels, and Zaid Al-Ars. 2018. Hardware acceleration of BWA-MEM genomic short read mapping for longer read lengths. Computational biology and chemistry 75 (2018), 54–64.
[11]
Saurabh Kalikar, Chirag Jain, Md Vasimuddin, and Sanchit Misra. 2022. Accelerating minimap2 for long-read sequencing applications on modern CPUs. Nature Computational Science 2, 2 (2022), 78–83.
[12]
Steven L Kleiman. 2005. The picard scheme. arXiv preprint math/0504020 (2005).
[13]
Heng Li. 2013. Aligning sequence reads, clone sequences and assembly contigs with BWA-MEM. arXiv preprint arXiv:1303.3997 (2013).
[14]
Heng Li. 2016. Minimap and miniasm: fast mapping and de novo assembly for noisy long sequences. Bioinformatics 32, 14 (2016), 2103–2110.
[15]
Heng Li. 2018. Minimap2: pairwise alignment for nucleotide sequences. Bioinformatics 34, 18 (2018), 3094–3100.
[16]
Heng Li, Bob Handsaker, Alec Wysoker, Tim Fennell, Jue Ruan, Nils Homer, Gabor Marth, Goncalo Abecasis, Richard Durbin, and 1000 Genome Project Data Processing Subgroup. 2009. The sequence alignment/map format and SAMtools. bioinformatics 25, 16 (2009), 2078–2079.
[17]
Heng Li and Nils Homer. 2010. A survey of sequence alignment algorithms for next-generation sequencing. Briefings in bioinformatics 11, 5 (2010), 473–483.
[18]
Tim Oliver, Bertil Schmidt, and Douglas Maskell. 2005. Hyper customized processors for bio-sequence database scanning on FPGAs. In Proceedings of the 2005 ACM/SIGDA 13th international symposium on Field-programmable gate arrays. Monterey California USA, 229–237.
[19]
Harisankar Sadasivan, Milos Maric, Eric Dawson, Vishanth Iyer, Johnny Israeli, and Satish Narayanasamy. 2023. Accelerating Minimap2 for accurate long read alignment on GPUs. Journal of biotechnology and biomedicine 6, 1 (2023), 13.
[20]
Saul Schleimer, Daniel S Wilkerson, and Alex Aiken. 2003. Winnowing: local algorithms for document fingerprinting. In Proceedings of the 2003 ACM SIGMOD international conference on Management of data. San Diego, California, USA, 76–85.
[21]
Zachary D Stephens, Skylar Y Lee, Faraz Faghri, Roy H Campbell, Chengxiang Zhai, Miles J Efron, Ravishankar Iyer, Michael C Schatz, Saurabh Sinha, and Gene E Robinson. 2015. Big data: astronomical or genomical?PLoS biology 13, 7 (2015), e1002195.
[22]
Hajime Suzuki and Masahiro Kasahara. 2018. Introducing difference recurrence relations for faster semi-global alignment of long sequences. BMC bioinformatics 19, 1 (2018), 33–47.
[23]
Carolina Teng, Renan W Achjian, Caio C Braga, Marcelo K Zuffo, and Wang J Chau. 2021. Accelerating the base-level alignment step of DNA assembling in Minimap2 Algorithm using FPGA. In 2021 IEEE 12th Latin America Symposium on Circuits and System (LASCAS). IEEE, 1–4.
[24]
Carolina Teng, Renan Weege Achjian, Jiang Chau Wang, and Fernando Josepetti Fonseca. 2023. Adapting the GACT-X aligner to accelerate minimap2 in an FPGA cloud instance. Applied Sciences 13, 7 (2023), 4385.
[25]
Liu Yanhu, Wang Lu, and Yu Li. 2015. The principle and application of the single-molecule real-time sequencing technology. Yi chuan= Hereditas 37, 3 (2015), 259–268.
Index Terms
- Hardware Acceleration of Minimap2 Genomic Sequence Alignment Algorithm
Recommendations
Optimizations of Sequence Alignment on FPGA: A Case Study of Extended Sequence Alignment (Abstact Only)
FPGA '18: Proceedings of the 2018 ACM/SIGDA International Symposium on Field-Programmable Gate ArraysDetecting similarities between sequences is an important part of Bioinformatics. In this poster, we explore the use of high-level synthesis tool and a field-programmable gate array (FPGA) for optimizing a sequence alignment algorithm. We demonstrate the ...
Hardware Accelerator for BLAST
MCSOC '12: Proceedings of the 2012 IEEE 6th International Symposium on Embedded Multicore SoCsThe basic local alignment search tool (BLAST) is one of the most popular sequence alignment tools available. Sequence alignment is used to extract similar parts of an input protein (or DNA) sequence from protein (or DNA) databases, in order to ...
Hardware acceleration of graphics and imaging algorithms using FPGAs
SCCG '02: Proceedings of the 18th Spring Conference on Computer GraphicsComputer graphics algorithms and algorithms used in image processing are generally computationally expensive. This fact is the reason why people struggle to accelerate such algorithms using any reasonable means. The traditional sources of speedup are ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
August 2024
1279 pages
ISBN:9798400717932
DOI:10.1145/3673038
Copyright © 2024 Owner/Author.
This work is licensed under a Creative Commons Attribution International 4.0 License.
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 12 August 2024
Check for updates
Author Tags
Qualifiers
- Research-article
- Research
- Refereed limited
Conference
ICPP '24
ICPP '24: the 53rd International Conference on Parallel Processing
August 12 - 15, 2024
Gotland, Sweden
Acceptance Rates
Overall Acceptance Rate 91 of 313 submissions, 29%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 195Total Downloads
- Downloads (Last 12 months)195
- Downloads (Last 6 weeks)124
Reflects downloads up to 25 Dec 2024
Other Metrics
Citations
View Options
View options
View or Download as a PDF file.
PDFeReader
View online with eReader.
eReaderHTML Format
View this article in HTML Format.
HTML FormatLogin options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in