# Reference Mapping Considering Swaps of Adjacent Bases
## 1 Introduction  
Since the time of the Human Genome Project (HGP) [1; 2], next-generation sequencing, which can reduce the cost and time of sequence analysis using computer algorithms, has been a very active area of research [3; 4]. Mapping is a next-generation sequencing method that identifies sequences by aligning short reads with a reference genome for which sequence information is known. It can be applied to various types of analyses of genetic mutations and genetic polymorphisms, such as single-nucleotide polymorphism (SNP) calling, motif searches, and gene identification [5; 6]. Most mapping algorithms consist of an indexing step, in which a data structure for a reference or reads is created, and an alignment step, in which fast mapping is performed using the data structures generated. In order to enhance mapping speed, studies utilizing various data structures have been conducted. Burrows-Wheeler transform (BWT)-based mapping tools have been developed [7; 8; 9; 10]. Among them, Bowtie [7] performs mapping based on the [PERSON]'s algorithm [11] and takes mismatches into account. The Burrows-Wheeler aligner (BWA) [8] first generates a prefix trie for the reference sequence and then performs mapping, taking mismatches and gaps into account with the use of a top-down traversal method. SOAP2 [9] considers mismatches and gaps using a bi-directional BWT search (or 2 way-BWT search) [12] and the Smith-Waterman algorithm [13], and it reduces space usage through a sampled suffix array. BWA-MEM [10] improved the performance of BWA using the seed alignments with maximal exact matches (MEM) and the seed extensions with the affine-gap Smith-Waterman algorithm. Meanwhile, tophat2 [14], considering very large deletions, inversions on the same chromosome and translocations involving different chromosomes were introduced. As the performance of graphics processing units (GPUs) has improved, several mapping studies that utilize this technology have been conducted [15; 16; 17; 18; 19]. SOAP3 [15] was developed based on SOAP2, in which the memory access method of the auxiliary data structure was improved with the consideration of the characteristics of Compute Unified Device Architecture (CUDA). Hard patterns referring to the read that causes some of the GPU processors to idle as a result of too many branches in alignment are processed, and a coalesced memory access strategy is employed. Subsequently, SOAP3-dp [16], which is based on SOAP3, improved the alignment ratio using the Smith-Waterman algorithm. BarraCUDA [17] was developed based on BWA, utilizing the texture memory of CUDA and a depth-first search algorithm. CUSHAW [18] uses 64 threads per thread block and a shared memory to improve performance, and it uses a depth-first search algorithm that considers the number of mismatches and the quality score of the mismatched base positions. CUSHAW2-GPU [19] improved upon the CUSHAW2 [20] algorithm by utilizing CUDA, a collaborative calculation of CPU and GPU, seed-based alignment, and a tile-based Smith-Waterman algorithm. Early mapping tools performed alignment only with exact sequence matches, but later alignment algorithms allowed a limited number of mismatches to search for SNPs. In recent years, mapping tools that consider not only mismatches but also gaps have been developed to facilitate the analysis of various genetic mutations. Approximate string matching algorithms that compare sequences in the presence of errors are used [5; 6; 7; 8; 9; 12; 15; 16; 17; 18; 19; 20]. In approximate string matching algorithms, distance functions are used for measuring errors. Typical distance functions include the Hamming distance, edit distances, and weighted edit distances [21]. Studies have also been conducted on the extended edit distance, which takes into consideration swaps that change the positions of two adjacent bases [22; 23; 24; 25] (Figure 1). Swaps occur during genetic mutation and replication and are known to be associated with spinal muscular atrophy [26; 27].