## 6 Optimization of PBKMC Algorithm
### Optimizing K-Mer Dumping with Read-Write Separation  
Usually, k-mer frequency counting algorithms do not directly output the frequency counting results to the disk in text format but write the results in binary encoding format. The binary result file is generally smaller than the input data file. To visit frequency files in text format, a decoder program independent of the frequency counting algorithm loads the result as needed.  
Similar to the frequency counting algorithm, the decoding performance of both KMC3 and CHTKC decoding programs is limited mainly by the IO bottleneck. In the decoding program of KMC3, the reading, decoding, and outputting of the binary code are all completed by one thread. Each time a k-mer is decoded, a disk write is executed. This method means that the decoding of each k-mer needs to block and wait for the IO device to be ready for every single k-mer, which significantly limits the overall throughput of the decoding program.  
We optimized the decoder program of KMC3 with a read-write separation strategy and combined it with the improved KMC3 algorithm to reduce the IO overhead. The optimized decoder program reads the binary encoded file in blocks and decodes k-mer  
\begin{table}
\begin{tabular}{c c c c c c} \hline \hline \(\mathbf{k}\) & **Dataset** & **Algorithm** & **Time (s)** & **Memory** & **Disk** & **Output File** \\ \hline \multirow{6}{*}{D-GC36} & CHTKC-1.0.2 & 985.06 & 14.9 GB & 43.2 GB & 42.5 GB \\  & KMC-3.1.1 & 381.21 & 15 GB & 37.4 GB & 35.7 GB \\  & Revised KMC3 & 390.39 & 15 GB & 41.6 GB & 21.8 GB \\ \cline{2-6}  & CHTKC-1.0.2 & 3739 & 14.9 GB & 86.9 GB & 86.6 GB \\  & H-GC41 & KMC-3.1.1 & 809.79 & 15 GB & 75.3 GB & 72.4 GB \\  & Revised KMC3 & 764.36 & 15 GB & 87.6 GB & 52.7 GB \\ \hline \multirow{6}{*}{64} & CHTKC-1.0.2 & 107.57 & 14.9 GB & 19.8 GB & 18.9 GB \\  & T-GC45 & KMC-3.1.1 & 113.02 & 14.9 GB & 17.2 GB & 17.2 GB \\  & Revised KMC3 & 95.46 & 14.6 GB & 8.2 GB & 8.2 GB \\ \cline{2-6}  & CHTKC-1.0.2 & 273.09 & 14.9 GB & 36.7 GB & 35.7 GB \\  & KMC-3.1.1 & 186.43 & 14.8 GB & 32.4 GB & 32.4 GB \\  & Revised KMC3 & 180.82 & 14.9 GB & 16.2 GB & 16.2 GB \\ \cline{2-6}  & CHTKC-1.0.2 & 1107.79 & 14.9 GB & 79.2 GB & 78.7 GB \\  & D-GC36 & KMC-3.1.1 & 413.02 & 14.9 GB & 71.1 GB & 71.1 GB \\  & Revised KMC3 & 370.38 & 15 GB & 38.7 GB & 38.7 GB \\ \cline{2-6}  & CHTKC-1.0.2 & 6050.57 & 14.9 GB & 251.9 GB & 251.8 GB \\  & H-GC41 & KMC-3.1.1 & 1739.18 & 15 GB & 226.9 GB & 226.9 GB \\  & Revised KMC3 & 1308.88 & 15 GB & 164.1 GB & 164.1 GB \\ \hline \hline \end{tabular}
\end{table}
Table 6: _Cont._  
Figure 10: Comparison of KMC3, CHTKC, and Revised KMC3 with various sequencing errors. Memory quota: CHTKC 128 GB, KMC3 32 GB, and Revised KMC3 32 GB. (**a**) counting tasks with various k\({}_{i}\) (**b**) counting tasks in various datasets.  
frequency pairs using the reader thread. Then, the reader thread submits the decoded blocks to the writer thread through a block queue, and the writer thread performs the actual disk writing operation. By separating the reader thread and the writer thread, the decoding operation performed by the reader thread does not need to wait to complete disk writing. The next round of reading and decoding can start immediately after the decoded result is submitted to the queue. Our decoding program demonstrated better performance in evaluations using simulated sequencing datasets than other dump programs (Figure 11). The experiments show that the revised algorithm dumps its counting results 8-60% faster than CHTKC and 3-6% faster than KMC3.