# Adapting the GACT-X Aligner to Accelerate Minimap2 in an FPGA Cloud Instance
## 2 Materials and Methods
### Adapting GACT-X for Minimap2 on an FPGA Platform  
#### 2.4.1 The Tile Approach  
The aligning task in assembly algorithms has been carried out fundamentally by the Smith-Waterman-Gotoh algorithm [18], with the computation of the best alignments between two sequences using a matrix-based dynamic programming method. The alignment allows for comparisons involving matches when the characters or strings are in identical in the same position(s) of alignment; mismatches occur when the characters are different in the same position; and gaps occur when either one of the sequences has an insertion or a deletion of a nucleotide or a sub-sequence.  
In order to save memory and improve performance, generations of alignment algorithms [19; 29], including the SK algorithm in Minimap2 [24], have adopted the use of a band to limit the number of cells computed in the matrix. These banding strategies improve the efficiency of software-implemented algorithms but still leave a linear memory complexity to the input's lengths, which poses a challenge in hardware applications since there are limited resources available.  
Figure 3: Simulated, real ONT, and real PacBio read length percentage histograms. Read lengths are grouped in intervals of 5000 nucleotide bases, except for the rightmost column, which represents all reads longer than 30,000 bases.  
GACT-X computes the banded SWG matrix with limited trace-back memory for any input lengths. Memory usage is limited because the computation is performed in scaffolding _tiles_ of a fixed size, instead of the entire matrix in one go. One tile overlaps a previous one by a certain number of bases to expand the alignment, forming a scaffold band on the SWG matrix. GACT-X's expansion starts from the anchoring point and stops when the last tile's max score is negative or zero or when the alignment has reached the border of query or target sequences.  
For each tile, the computation of cells is limited within a band. The matrix is filled row-wise while tracking the maximum score \(V_{max}\) of the tile. Stripes with a number of rows equivalent to the number of processing elements (PEs) are calculated with wave-front parallelism. The computation in a stripe is limited to columns containing at least one cell with a score close to the \(V_{max}\) by an \(X\) threshold. This process is called the X-drop banding algorithm. Figure 4 illustrates an example of a GACT-X alignment with expansion from the top-left corner. Four tiles are computed, and bands are adopted inside the tiles. Figure 5 presents GACT-X's architecture based on a systolic array with 32 processing nodes.  
Figure 4: Example of a GACT-X SWG semi-global alignment with expansion from the top-left corner. For reference, the scale is based on the values of query and target lengths of 14,000 bases, tile size being 4000, the tile overlap being 128, and 32 rows in each stripe. The SWG matrix is the widest light square on the left; the alignment was finished with 4 tiles in medium gray. The X-drop band of calculated cells is in dark gray, which can be seen more clearly on the zoom-in on the right, with the final alignment path in light blue.  
Figure 5: GACT-X’s systolic array architecture with 32 PEs. The host transfers the target and the query sequences to the DRAM. \(N_{PE}=32\) query characters are loaded to the PEs, and target elements are streamed in a systolic fashion. A fixed memory of 1 BRAM bank per PE is allocated to store the 4-bit trace-back pointers, sequentially—2 bits for the main matrix and 2 bits for gap matrices. The start and stop positions of each stripe are stored in separate BRAMs.