Pairwise sequence alignment accounts for the majority of key genome analysis applications' runtime. Because of the quadratic time complexity of exact alignment algorithms, the community is moving away from exact algorithms in favor of heuristics that only compute high-quality results. However, the state of the art lacks hardware-accelerated versions of these heuristic algorithms as the vast majority of the available solutions still rely on implementing exact alignment algorithms. Moreover, hardware-based implementations lack high-level APIs that can simplify their integration in commonly used genomic pipelines, hindering their applicability in real-world scenarios. In this context, we present the first high-performance FPGA implementation of the popular X-drop heuristic alignment algorithm and provide an easy-to-use API for its integration. On a Xilinx Alveo U280, our FPGA design achieves up to 5 speed-up over SeqAn, the state-of-the-art software version of the algorithm, running on two Intel Xeon processors using 80 CPU threads. Moreover, our design is also 3.45 faster than ksw2, a state-of-the-art vectorized alignment algorithm that performs a similar heuristic to the one employed in the X-drop algorithm. Finally, our implementation also outperforms LOGAN, a recently published GPU implementation of X-drop running on an Nvidia Tesla V100, by a factor of 1.5.

The Importance of Being X-Drop: High Performance Genome Alignment on Reconfigurable Hardware

Zeni A.;Di Donato G. W.;Di Tucci L.;Rabozzi M.;Santambrogio M. D.
2021-01-01

Abstract

Pairwise sequence alignment accounts for the majority of key genome analysis applications' runtime. Because of the quadratic time complexity of exact alignment algorithms, the community is moving away from exact algorithms in favor of heuristics that only compute high-quality results. However, the state of the art lacks hardware-accelerated versions of these heuristic algorithms as the vast majority of the available solutions still rely on implementing exact alignment algorithms. Moreover, hardware-based implementations lack high-level APIs that can simplify their integration in commonly used genomic pipelines, hindering their applicability in real-world scenarios. In this context, we present the first high-performance FPGA implementation of the popular X-drop heuristic alignment algorithm and provide an easy-to-use API for its integration. On a Xilinx Alveo U280, our FPGA design achieves up to 5 speed-up over SeqAn, the state-of-the-art software version of the algorithm, running on two Intel Xeon processors using 80 CPU threads. Moreover, our design is also 3.45 faster than ksw2, a state-of-the-art vectorized alignment algorithm that performs a similar heuristic to the one employed in the X-drop algorithm. Finally, our implementation also outperforms LOGAN, a recently published GPU implementation of X-drop running on an Nvidia Tesla V100, by a factor of 1.5.
2021
Proceedings - 29th IEEE International Symposium on Field-Programmable Custom Computing Machines, FCCM 2021
978-1-6654-3555-0
Genome Alignment
Genome Analysis
Heuristic Alignment
HPC
Roofline Analysis
X drop Alignment
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11311/1183089
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 11
  • ???jsp.display-item.citation.isi??? 5
social impact