## 3 Background  
### FM-Based Mechanism in Sequence Alignment  
In the field of bioinformatics, deciphering genetic information is one of the most important tasks for sequence aligners and exposes hidden patterns within DNA, RNA, and protein sequences. The criteria for the selection of the sequence aligners depend on the properties of the data, the level of accuracy, and the computational performance. These aligners are implemented using computational methods, such as heuristics and machine learning algorithms, combined with statistical approaches to increase precision and effectiveness. Notable alignment tools in bioinformatics include MAQ [27], BOWTIE [10], BWA [11], and HISAT [12].  
FM index-based sequence alignment is a widely employed tool in genomics research. It generates a compact index for the reference genome, enabling the alignment to be conducted in fixed-size segments using a round-robin pattern [28]. This aligner processes data individually, thereby avoiding interdependence among data segments. FM aligners permit predefined scores for mismatches and gaps, thus increasing the probability of aligning short reads to long reference sequences. It uses a compressed genome reference, which simplifies the search of sequencing data. The BWT data structure is applied to optimize pattern matching [29]. Therefore, the FM-based sequence aligner generally comprises two processes: index building and sequence searching. Index building is the process through which the genome reference is preprocessed. The alignment of short sequences, such as DNA or RNA segments, with the reference genome is called sequence searching. Due to these techniques, FM-based sequence aligners take less time and use fewer processing resources.  
The FM alignment approach is a technique of facilitating the features of suffix array (SA) and BWT that helps optimize the alignment of sequences through the use of their structural efficiencies. This combination allows for the rapid alignment of all instances of a given pattern P within a large genome reference (GR). Unlike other traditional alignment methods, FM-based sequence aligner is essentially faster than other popular algorithms,and its computational complexity depends mainly on the length of P. Thus, it is especially useful for large genomes. The detailed computation process is as follows.  
(1) SA construction  
The creation of suffixes is initially conducted. For a given genome reference GR, all possible suffixes of GR are created by adding a unique character $ at the end of GR to define the ending of the string with a minimal lexicographical value. This is followed by sorting the suffixes in the lexicographical order. The SA is an array with elements indicating the initial positions where a sorted suffix begins in the original string.  
(2) BWT computation  
Rotations and sorting are performed in the procedure. Each rotation of the string GR is formed through a circular shift in the input string. The set of rotations is sorted lexically, followed by BWT formation. The BWT is constructed by taking the last character from each of the sorted rotations. The reasoning behind using these characters is that, when concatenated, they reveal the repetitive nature of the original string, aiding in effective compression and transformation.  
Table 1 illustrates the calculation of SA and BWT of the string GR = GTGTAC. Each row indicates a rotation of the sequences in sorted order. The SA index column contains the original indices of the suffixes before sorting. The rotations column displays every possible rotation of GR. The Sorted-BWT column is the sequence of rotations in sorted order, which directly affects the construction of the BWT. The sorted index represents the SA values for the starting positions of the suffixes in the original string. Thus, the BWT represented as CTAT$GG is derived from the last characters of the sorted rotations in the Sorted-BWT. This BWT sequence is essential for the reconstruction of the original sequence and facilitates effective pattern searching.