# Reference Mapping Considering Swaps of Adjacent Bases
## 2 Materials and Methods  
Consider two sequences, \(T\) and \(R\). If \(T[(i-2k+1)..(i-k)]=R[(j-k+1)..j]\) and \(T[(i-k+1)..i]=R[(j-2k+1)..(j-k)]\)\((i,j\geq 2k)\), we can determine that a swap of length \(k\) took place at \(T[i]\) and \(R[j]\). A swap of length \(k\) means that the order of two adjacent subsequences with a length of \(k\) is changed. Let \(S_{SW}\) be the penalty score for swaps. The alignment score of the swap is calculated by adding \(S_{SW}\) to the score before the swap occurred. In Algorithm 2, which computes the tables for SOAP3-swap, the alignment score \(M(i,j)\) is defined as the largest score among the alignment scores that considers matches, mismatches, gaps, and swaps (line 9). In SOAP3-swap, swaps of length 1 to 3 can be considered, and the time complexity is the same as that of SOAP3-dp, as shown in Algorithm 2.  
The Sequence Alignment/Map (SAM) format is a text format for storing read alignments against reference sequences, and it supports short and long reads (up to 128 Mbp) produced by different sequencing platforms [28; 29]. The Binary Alignment/Map (SAM) format is a binary representation of the SAM and keeps exactly the same information as the SAM. To achieve fast random access in a zlib-compatible compressed file [30; 31; 32; 33], the BAM can be compressed using the BGZF library, a generic library developed by [PERSON] and modified by [PERSON] for remote file access and in-memory caching [28]. The SAM/SAM format includes the Compact Idiosyncratic Gapped Alignment Report (CIGAR) string format to describe how a read aligns to a reference. The CIGAR operations in SAM include the following: 'M' for match/mismatch, 'I' for insertion compared with the reference, 'D'for deletion, 'N' for skipped bases on the reference, 'S' for soft clipping where the clipped subsequence is shown in the read sequence in the SAM format, 'H' for hard clipping where the clipped subsequence is not shown in the read sequence in the SAM format, 'P' for padding, '=' for match, and 'X' for mismatch [28,29].  
```
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)\leftarrow\mathit{max}\{M(i,j-1)+S_{GO},I(i,j-1)+S_{GE}\}\)
6:\(D(i,j)\leftarrow\mathit{max}\{M(i-1,j)+S_{GO},D(i-1,j)+S_{GE}\}\)
7:\(M(i,j)\leftarrow\mathit{max}\{M(i-1,j-1)+\delta(T[i],R[j]),I(i,j),D(i,j)\}\)
8:if\((i\geq 2k)\) and \((j\geq 2k)\) and \(T[(i-2k+1)..(i-k)]=R[(j-k+1)..j]\) and \(T[(i-k+1)..i]=R[(j-2k+1)..(j-k)]\)) then
9:\(M(i,j)\leftarrow\mathit{max}\{M(i,j),M(i-2k,j-2k)+S_{SW}\}\)
10:endif
11:endfor
12:endfor
```  
**Algorithm 2****Compute \(I\), \(D\), and \(M\) considering swaps.**  
Since a mapping tool that considers swaps was not available, no alignment information regarding swaps was available in the CIGAR string. Therefore, the symbols representing the swap were added to the CIGAR string of SOAP3-swap. When outputting the alignment results in SAM format, the reads where a swap occurred are marked as 'T', 'W', and 'B' in the CIGAR string when the lengths of the two exchanged base sequences are 1, 2, and 3, respectively.