## 6 Optimization of PBKMC Algorithm
### Optimizing Disk IO with an Overlapping Sequence Set  
We improved the KMC algorithm by filtering and gluing the first-occurring k-mers to decrease disk occupation (Figure 9). First, the DNA sequence data are read into the memory in the partition stage through the reader thread and then passed to the worker threads through a blocking queue. Next, the worker threads divide the DNA sequences into k-mers and transmit each k-mer to a bloom filter to check if the k-mer is the first occurrence. The consecutive first-occurring k-mers are merged into an overlapping sequence, and non-first-occurring k-mers are distributed according to the process of KMC3. The overlapping sequences are also distributed to the corresponding overlapping sequence sets according  
Figure 8: Weak scalability comparison of KMC3 and CHTKC.  
to the partitioning rules consistent with KMC3 and written into different files. As a result, every partition in our algorithm has two files: one for the overlapping sequence set we produced and the other for the super k-mers used in the counting stage. After that, the counting stage of the revised algorithm is consistent with the counting stage of KMC3.  
By introducing a bloom filter to filter the first occurrence of k-mers and storing them as overlapping sequences, singleton k-mers that occupy most of the input data are stored on disk in a highly compact manner. Therefore, the spatial correlation of k-mers described above is effectively utilized, and the IO performance can be significantly optimized. It also prevents many singleton k-mers from using extra memory in the subsequent counting stage, which improves the overall efficiency of the algorithm from another perspective.  
We evaluated the improved algorithm using simulated sequencing datasets (Table 6). When k = 32, the singleton k-mers in the sequencing data make up the majority, the revised KMC3 algorithm only needs nearly half of the disk space of other algorithms with similar running memory, which suggests a significant optimization in disk access. As a result, the revised KMC3 algorithm is slightly faster than others when processing large datasets. The improved KMC3 algorithm performs better when k is larger. For example, the improved KMC3 algorithm is 13% faster than CHTKC and 18% faster than KMC3 in T-GC45, a dataset with more than 9 GB input. With the increase in dataset size, the advantage of the revised algorithm in terms of IO becomes more apparent. When counting the 64-mer frequency of H-GC41 in the same memory space, the running time of the improved algorithm is nearly five times faster than CHTKC and 33% faster than KMC3. Our experiments show that the revised algorithm has excellent performance when dealing with large datasets and frequency counting tasks with larger k-mers. Because sequencing errors result in more singleton k-mers, the revised algorithm has an increasing advantage over low sequencing quality data (Figure 10).  
\begin{table}
\begin{tabular}{c c c c c c} \hline \hline \(\mathbf{k}\) & **Dataset** & **Algorithm** & **Time (s)** & **Memory** & **Disk** & **Output File** \\ \hline \multirow{4}{*}{32} & \multirow{4}{*}{T-GC45} & CHTKC-1.0.2 & 116.19 & 14.9 GB & 11.7 GB & 10.9 GB \\  & & KMC-3.1.1 & 97.32 & 14.9 GB & 9.3 GB & 9.3 GB \\  & & Revised KMC3 & 97.83 & 14.9 GB & 8.5 GB & 5 GB \\ \cline{2-6}  & \multirow{4}{*}{T-GC30} & CHTKC-1.0.2 & 258.13 & 14.9 GB & 20 GB & 19.1 GB \\  & & KMC-3.1.1 & 209.2 & 14.8 GB & 16.2 GB & 16.1 GB \\  & & Revised KMC3 & 191.99 & 14.9 GB & 18 GB & 9.3 GB \\ \hline \hline \end{tabular}
\end{table}
Table 6: Comparison of KMC3, CHTKC, and Revised KMC3 with various sequencing data (Memory quota 16 GB).  
Figure 9: The partition procedure of the revised KMC3 algorithm. FO k-mers denote first-occurring k-mers, NFO k-mers denote non-first-occurrence k-mers, and OS denotes overlapping sequence.