# Adapting the GACT-X Aligner to Accelerate Minimap2 in an FPGA Cloud Instance
## 1 Introduction
(1) The seeding stage implements a position table indexing method for each unique sequence of a length k (k-mer) in the reference; this allows for efficient computation of the exact matches of k-mers between the read and reference, defining the anchors along them. (2) The filtering stage is performed via the chaining algorithm, which selects correlated anchors to form chains that are sorted by their corresponding scores. (3) In the extending stage, read sub-sequences are aligned to reference sub-sequences, guided by the anchoring positions in the selected chain(s). but with different heuristics and/or transformations added on to reduce its complexity. One recurrent example is the banding heuristic: by calculating only a band of the SWG matrix, where the optimal alignment path is more probable to be, the time and memory complexities can be reduced from a quadratic to a linear ratio in relation to the inputs' lengths [19; 20]. The genome assembly algorithms may perform differently depending on the type of input reads, obtained through different sequencing technologies. There are short reads, with lengths of a few hundred bases, and long reads, with many thousands of bases on average. Currently, the so-called second generation of sequencing technology, which produces short reads, dominates the market and is expected to stay prevalent for years to come due to its high throughput and relatively low cost [21]. In recent years, the third generation of sequencers, which produces long reads, has emerged as the technology of the future in the market, presenting several advantages with respect to the previous technologies. For instance, long reads are more effective in detecting structural variants (SVs), which are insertions, deletions, duplications, inversions, or translocations that affect more than 50 nucleotide bases in the genome. Each human genome has \(>\)20,000 SVs, and most of them remained undetected until long reads were introduced. That posed a serious problem since SVs account for the highest number of divergent bases across human genomes [22]. The current shortcomings in long-read technologies are their higher sequencing costs [23] and their higher error rates [13] in comparison to their established short-read counterparts. Many programs, such as Bowtie2 [16], have been developed to efficiently assemble short reads on the second-generation technology. However, their strategies are often unsuitable for processing long reads; in this condition, they present low performance or require a large sum of resources to compute. BWA-MEM [15] and Minimap2 [14] are examples of programs/algorithms that have been proposed to fill the long-read gap; the latter is 50 times faster than the former in addition to having better mapping accuracy than most other programs. Minimap2 is the current state-of-the-art program for assembling long reads. Its filtering stage corresponds to a chaining algorithm that takes advantage of the higher load of information carried by long reads to find approximate mapping positions with high performance and high accuracy. Its extending/alignment stage corresponds to a transformed version of the SWG algorithm, proposed by [PERSON] and [PERSON] (SK) [24], that limits data size in Streaming SIMD (single instruction, multiple data) extensions' (SSE) vector instructions to maximize the parallelization of cell data computation. Despite the efficient techniques adopted, processing in Minimap2 is still time-consuming; dozens of central processing unit (CPU) hours on an Intel(r) Xeon(r) processor are required to assemble one human genome sample of long reads with high coverage [25]. In order to improve the computational performance of software-based algorithms, one alternative is designing domain-specific architectures (DSAs), particularly with application-specific integrated circuits (ASICs), field programmable gate arrays (FPGAs), or graphic processing units (GPUs). The design of an ASIC or FPGA solution takes a longer time and is usually more expensive than programming a GPU system.