{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T02:57:19Z","timestamp":1760151439488,"version":"build-2065373602"},"reference-count":36,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2022,3,24]],"date-time":"2022-03-24T00:00:00Z","timestamp":1648080000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"the National Key R&amp;D Program of China","award":["2018YFC0910200"],"award-info":[{"award-number":["2018YFC0910200"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Background: K-mer frequency counting is an upstream process of many bioinformatics data analysis workflows. KMC3 and CHTKC are the representative partition-based k-mer counting and non-partition-based k-mer counting algorithms, respectively. This paper evaluates the two algorithms and presents their best applicable scenarios and potential improvements using multiple hardware contexts and datasets. Results: KMC3 uses less memory and runs faster than CHTKC on a regular configuration server. CHTKC is efficient on high-performance computing platforms with high available memory, multi-thread, and low IO bandwidth. When tested with various datasets, KMC3 is less sensitive to the number of distinct k-mers and is more efficient for tasks with relatively low sequencing quality and long k-mer. CHTKC performs better than KMC3 in counting assignments with large-scale datasets, high sequencing quality, and short k-mer. Both algorithms are affected by IO bandwidth, and decreasing the influence of the IO bottleneck is critical as our tests show improvement by filtering and compressing consecutive first-occurring k-mers in KMC3. Conclusions: KMC3 is more competitive for running counter on ordinary hardware resources, and CHTKC is more competitive for counting k-mers in super-scale datasets on higher-performance computing platforms. Reducing the influence of the IO bottleneck is essential for optimizing the k-mer counting algorithm, and filtering and compressing low-frequency k-mers is critical in relieving IO impact.<\/jats:p>","DOI":"10.3390\/a15040107","type":"journal-article","created":{"date-parts":[[2022,3,25]],"date-time":"2022-03-25T00:05:18Z","timestamp":1648166718000},"page":"107","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["KMC3 and CHTKC: Best Scenarios, Deficiencies, and Challenges in High-Throughput Sequencing Data Analysis"],"prefix":"10.3390","volume":"15","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3796-3965","authenticated-orcid":false,"given":"Deyou","family":"Tang","sequence":"first","affiliation":[{"name":"School of Software Engineering, South China University of Technology, Guangzhou 510006, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daqiang","family":"Tan","sequence":"additional","affiliation":[{"name":"School of Software Engineering, South China University of Technology, Guangzhou 510006, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Weihao","family":"Xiao","sequence":"additional","affiliation":[{"name":"School of Software Engineering, South China University of Technology, Guangzhou 510006, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jiabin","family":"Lin","sequence":"additional","affiliation":[{"name":"School of Software Engineering, South China University of Technology, Guangzhou 510006, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Juan","family":"Fu","sequence":"additional","affiliation":[{"name":"School of Medicine, South China University of Technology, Guangzhou 510006, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2022,3,24]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"R108","DOI":"10.1186\/gb-2009-10-10-r108","article-title":"Genomic DNA k-mer spectra: Models and modalities","volume":"10","author":"Chor","year":"2009","journal-title":"Genome Biol."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1186\/s13059-017-1372-2","article-title":"DE-kupl: Exhaustive capture of biological variation in RNA-seq data through k-mer decomposition","volume":"18","author":"Audoux","year":"2017","journal-title":"Genome Biol."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"578","DOI":"10.1038\/s41598-020-57452-6","article-title":"FQSqueezer: K-mer-based compression of sequencing data","volume":"10","author":"Deorowicz","year":"2020","journal-title":"Sci. Rep."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1186\/s13059-018-1554-6","article-title":"RefSeq database growth influences the accuracy of k-mer-based lowest common ancestor species identification","volume":"19","author":"Nasko","year":"2018","journal-title":"Genome Biol."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"4259479","DOI":"10.1155\/2019\/4259479","article-title":"K-mer-Based Motif Analysis in Insect Species across Anopheles, Drosophila, and Glossina Genera and Its Application to Species Classification","volume":"2019","author":"Cserhati","year":"2019","journal-title":"Comput. Math. Methods Med."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"1574","DOI":"10.1016\/j.ygeno.2018.11.001","article-title":"Genome classification improvements based on k-mer intervals in sequences","volume":"111","author":"Han","year":"2019","journal-title":"Genomics"},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Jaillard, M., Lima, L., Tournoud, M., Mah\u00e9, P., Van Belkum, A., Lacroix, V., and Jacob, L. (2018). A fast and agnostic method for bacterial genome-wide association studies: Bridging the gap between k-mers and genetic events. PLoS Genet., 14.","DOI":"10.1101\/297754"},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Kurtz, S., Narechania, A., Stein, J.C., and Ware, D. (2008). A new method to compute K-mer frequencies and its application to annotate large repetitive plant genomes. BMC Genom., 9.","DOI":"10.1186\/1471-2164-9-517"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"764","DOI":"10.1093\/bioinformatics\/btr011","article-title":"A fast, lock-free approach for efficient parallel counting of occurrences of k-mers","volume":"27","author":"Marcais","year":"2011","journal-title":"Bioinformatics"},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Melsted, P., and Pritchard, J. (2011). Efficient counting of k-mers in DNA sequences using a bloom filter. BMC Bioinform., 12.","DOI":"10.1186\/1471-2105-12-333"},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Deorowicz, S., Debudaj-Grabysz, A., and Grabowski, S. (2013). Disk-based k-mer counting on a PC. BMC Bioinform., 14.","DOI":"10.1186\/1471-2105-14-160"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"1569","DOI":"10.1093\/bioinformatics\/btv022","article-title":"KMC 2: Fast and resource-frugal k-mer counting","volume":"31","author":"Deorowicz","year":"2015","journal-title":"Bioinformatics"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"2759","DOI":"10.1093\/bioinformatics\/btx304","article-title":"KMC 3: Counting and manipulating k-mer statistics","volume":"33","author":"Kokot","year":"2017","journal-title":"Bioinformatics"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"652","DOI":"10.1093\/bioinformatics\/btt020","article-title":"DSK: K-mer counting with very low memory usage","volume":"29","author":"Rizk","year":"2013","journal-title":"Bioinformatics"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"1950","DOI":"10.1093\/bioinformatics\/btu132","article-title":"Turtle: Identifying frequent k-mers with cache-efficient algorithms","volume":"30","author":"Roy","year":"2014","journal-title":"Bioinformatics"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"2070","DOI":"10.1093\/bioinformatics\/btu152","article-title":"KAnalyze: A Fast Versatile Pipelined K-mer Toolkit","volume":"30","author":"Audano","year":"2014","journal-title":"Bioinformatics"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"58","DOI":"10.1186\/s13742-015-0097-y","article-title":"GenomeTester4: A toolkit for performing basic set operations-union, intersection and complement on k-mer lists","volume":"4","author":"Kaplinski","year":"2015","journal-title":"Gigascience"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"900","DOI":"10.12688\/f1000research.6924.1","article-title":"The khmer software package: Enabling efficient nucleotide sequence analysis","volume":"4","author":"Crusoe","year":"2015","journal-title":"F1000Research"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"2783","DOI":"10.1093\/bioinformatics\/btw345","article-title":"KCMBT: A k-mer Counter based on Multiple Burst Trees","volume":"32","author":"Mamun","year":"2016","journal-title":"Bioinformatics"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1186\/s13015-017-0097-9","article-title":"Gerbil: A fast and memory-efficient k-mer counter with GPU-support","volume":"12","author":"Erbert","year":"2017","journal-title":"Algorithms Mol. Biol."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"bbaa063","DOI":"10.1093\/bib\/bbaa063","article-title":"CHTKC: A robust and efficient k-mer counting algorithm based on a lock-free chaining hash table","volume":"22","author":"Wang","year":"2021","journal-title":"Brief. Bioinform."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"933","DOI":"10.1093\/bioinformatics\/btab797","article-title":"KCOSS: An ultra-fast k-mer counter for assembled genome analysis","volume":"38","author":"Tang","year":"2022","journal-title":"Bioinformatics"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"2858","DOI":"10.1093\/bioinformatics\/btab217","article-title":"BLight: Efficient exact associative structure for k-mers","volume":"37","author":"Marchet","year":"2021","journal-title":"Bioinformatics"},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Purcell, C., and Harris, T. (2005, January 26\u201329). Non-blocking Hashtables with Open Addressing. Proceedings of the Distributed Computing, International Conference, DISC, Cracow, Poland.","DOI":"10.1007\/11561927_10"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"192","DOI":"10.1145\/506309.506312","article-title":"Burst tries: A fast, efficient data structure for string keys","volume":"20","author":"Steffen","year":"2002","journal-title":"ACM Trans. Inf. Syst."},{"key":"ref_26","unstructured":"Li, Y., and Yan, X. (2015). MSPKmerCounter: A Fast and Memory Efficient Approach for K-mer Counting. arXiv."},{"key":"ref_27","first-page":"235","article-title":"Sorting Data on Ultra-Large Scale with RADULS","volume":"Volume 716","author":"Kokot","year":"2017","journal-title":"International Conference: Beyond Databases, Architectures and Structures, Proceedings of the 13th International Conference, BDAS 2017, Ustro\u0144, Poland, 30 May\u20132 June 2017"},{"key":"ref_28","first-page":"giy125","article-title":"A benchmark study of k-mer counting methods for high-throughput sequencing","volume":"7","author":"Manekar","year":"2018","journal-title":"Gigascience"},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"568","DOI":"10.1093\/bioinformatics\/btx636","article-title":"Squeakr: An exact and approximate k-mer counting system","volume":"34","author":"Pandey","year":"2018","journal-title":"Bioinformatics"},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Pandey, P., Bender, M.A., Johnson, R., and Patro, R. (2017, January 9). A General-Purpose Counting Filter: Making Every Bit Count. Proceedings of the 2017 ACM International Conference on Management of Data, Association for Computing Machinery, Chicago, IL, USA.","DOI":"10.1145\/3035918.3035963"},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"248","DOI":"10.1089\/cmb.2015.0199","article-title":"Computational Performance Assessment of k-mer Counting Algorithms","volume":"23","author":"Gutierrez","year":"2016","journal-title":"J. Comput. Biol."},{"key":"ref_32","doi-asserted-by":"crossref","unstructured":"Xiao, M., Li, J., Hong, S., Yang, Y., Li, J., Wang, J., Yang, J., Ding, W., and Zhang, L. (2018, January 3\u20136). K-mer Counting: Memory-efficient strategy, parallel computing and field of application for Bioinformatics. Proceedings of the 2018 IEEE International Conference on Bioinformatics and Biomedicine (BIBM), Madrid, Spain.","DOI":"10.1109\/BIBM.2018.8621325"},{"key":"ref_33","unstructured":"Liu, B., Shi, Y., Yuan, J., Hu, X., Zhang, H., Li, N., Li, Z., Chen, Y., Mu, D., and Fan, W. (2013). Estimation of genomic characteristics by analyzing k-mer frequency in de novo genome projects. arXiv."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1038\/nature08696","article-title":"The sequence and de novo assembly of the giant panda genome","volume":"463","author":"Li","year":"2010","journal-title":"Nature"},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"1533","DOI":"10.1093\/bioinformatics\/bts187","article-title":"pIRS: Profile-based Illumina pair-end reads simulator","volume":"28","author":"Hu","year":"2012","journal-title":"Bioinformatics"},{"key":"ref_36","doi-asserted-by":"crossref","unstructured":"Shokrof, M., Brown, C.T., and Mansour, T.A. (2021). MQF and buffered MQF: Quotient filters for efficient storage of k-mers with their counts and metadata. BMC Bioinform., 22.","DOI":"10.1186\/s12859-021-03996-x"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/15\/4\/107\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T22:42:02Z","timestamp":1760136122000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/15\/4\/107"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,3,24]]},"references-count":36,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2022,4]]}},"alternative-id":["a15040107"],"URL":"https:\/\/doi.org\/10.3390\/a15040107","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2022,3,24]]}}}