# Reference Mapping Considering Swaps of Adjacent Bases
## 1 Introduction
### Previous Work  
SOAP3-dp is a mapping tool that is an extension of SOAP3 [15], the first GPU-based mapping tool. SOAP3 and SOAP3-dp use an improved memory access method and 2 way-BWT and allocate reads to different groups according to the amount of calculation required when considering the characteristics of CUDA. SOAP3-dp has a similar execution time to that of SOAP3 but performs an additional alignment of the reads not aligned during the initial attempt using dynamic programming. The addition of this step leads to an enhanced alignment ratio compared to that of SOAP3. While SOAP3 performs alignments that only consider mismatches, SOAP3-dp performs alignments that consider mismatches and also small gaps using the Smith-Waterman algorithm [13], a well-known sequence comparison algorithm.  
Figure 1: An example of swaps when the swapped block size (the length of the swapped bases) is 2.  
When a paired-end alignment is carried out using SOAP3-dp, the alignment is first performed through a 2 way-BWT search considering only mismatches. For some read pairs that do not align during this process, a search is made for the position with the highest alignment score, which satisfies the interval condition between the pair, taking mismatches and gaps into account. At this point, the region of the reference sequence in which the corresponding read pair may exist is called the candidate region. When a read \(R\) (\(|R|=n\)) likely to be aligned to a candidate region \(T\) (\(|T|=m\)) is provided, the sub-region of \(T\) with the highest alignment score between the \(T\)'s sub-region and \(R\) is searched. Let \(T[i..j]\) represent the subsequence from \(i\) to \(j\) in \(T\). Among the subsequences of \(T[1..i]\), the alignment score of the subsequence with the highest alignment score for \(R[1..j]\) is expressed as \(M(i,j)\). \(I(i,j)\) refers to the alignment score that inserts \(R[j]\) next to \(T[1..i]\), and \(D(i,j)\) refers to the alignment score that deletes \(T[i]\) from \(T[1..i]\). Thus, the highest score at which \(R\) is aligned to \(T\) is \(max_{1\leq i\leq m}M(i,n)\). The starting position at which \(R\) is aligned to \(T\) can be calculated by tracing back the errors used to align from \(max_{1\leq i\leq m}M(i,n)\). The match score was expressed as \(S_{MA}\), and the penalty scores for mismatches, gap openings, and gap extensions were expressed as \(S_{MI}\), \(S_{GO}\), and \(S_{GE}\), respectively. The initial values of each alignment score are as follows: \(I(i,0)=-\infty\) (\(1\leq i\leq m\)), \(D(0,j)=-\infty\) (\(1\leq j\leq n\)), \(M(i,0)=0\) (\(0\leq i\leq m\)), and \(M(0,j)=S_{GO}+(j-1)S_{GE}\) (\(1\leq j\leq n\)). Algorithm 1 shows the Smith-Waterman algorithm for SOAP3-dp [16]. Here, \(\delta(a,b)\) denotes the match or mismatch score between two sequence elements \(a\) and \(b\). If \(T[i]=R[j]\), then \(\delta(T[i],R[j])=S_{MA}\), and if \(T[i]\
eq R[j]\), then \(\delta(T[i],R[j])=S_{MI}\).  
```
1: Assign tables \(I\), \(D\), and \(M\) of size \((m+1)\times(n+1)\)
2: Initialize(\(I\), \(D\), \(M\))
3:for\(i\gets 1\) to \(m\)do
4:for\(j\gets 1\) to \(n\)do
5:\(I(i,j)\gets max\{M(i,j-1)+S_{GO},I(i,j-1)+S_{GE}\}\)
6:\(D(i,j)\gets max\{M(i-1,j)+S_{GO},D(i-1,j)+S_{GE}\}\)
7:\(M(i,j)\gets max\{M(i-1,j-1)+\delta(T[i],R[j]),I(i,j),D(i,j)\}\)
8:endfor
9:endfor
```  
**Algorithm 1****Compute \(I\), \(D\), and \(M\)**.