{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,17]],"date-time":"2026-03-17T23:27:28Z","timestamp":1773790048339,"version":"3.50.1"},"reference-count":38,"publisher":"Oxford University Press (OUP)","issue":"4","license":[{"start":{"date-parts":[[2021,11,26]],"date-time":"2021-11-26T00:00:00Z","timestamp":1637884800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"funder":[{"DOI":"10.13039\/501100012166","name":"National Key R&D Program of China","doi-asserted-by":"crossref","award":["2018YFC0910200"],"award-info":[{"award-number":["2018YFC0910200"]}],"id":[{"id":"10.13039\/501100012166","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100004917","name":"Cancer Prevention and Research Institute of Texas [CPRIT","doi-asserted-by":"crossref","award":["RP180734"],"award-info":[{"award-number":["RP180734"]}],"id":[{"id":"10.13039\/100004917","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022,1,27]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:sec><jats:title>Motivation<\/jats:title><jats:p>The k-mer frequency in whole genome sequences provides researchers with an insightful perspective on genomic complexity, comparative genomics, metagenomics and phylogeny. The current k-mer counting tools are typically slow, and they require large memory and hard disk for assembled genome analysis.<\/jats:p><\/jats:sec><jats:sec><jats:title>Results<\/jats:title><jats:p>We propose a novel and ultra-fast k-mer counting algorithm, KCOSS, to fulfill k-mer counting mainly for assembled genomes with segmented Bloom filter, lock-free queue, lock-free thread pool and cuckoo hash table. We optimize running time and memory consumption by recycling memory blocks, merging multiple consecutive first-occurrence k-mers into C-read, and writing a set of C-reads to disk asynchronously. KCOSS was comparatively tested with Jellyfish2, CHTKC and KMC3 on seven assembled genomes and three sequencing datasets in running time, memory consumption, and hard disk occupation. The experimental results show that KCOSS counts k-mer with less memory and disk while having a shorter running time on assembled genomes. KCOSS can be used to calculate the k-mer frequency not only for assembled genomes but also for sequencing data.<\/jats:p><\/jats:sec><jats:sec><jats:title>Availabilityand implementation<\/jats:title><jats:p>The KCOSS software is implemented in C++. It is freely available on GitHub: https:\/\/github.com\/kcoss-2021\/KCOSS.<\/jats:p><\/jats:sec><jats:sec><jats:title>Supplementary information<\/jats:title><jats:p>Supplementary data are available at Bioinformatics online.<\/jats:p><\/jats:sec>","DOI":"10.1093\/bioinformatics\/btab797","type":"journal-article","created":{"date-parts":[[2021,11,19]],"date-time":"2021-11-19T12:20:58Z","timestamp":1637324458000},"page":"933-940","source":"Crossref","is-referenced-by-count":12,"title":["KCOSS: an ultra-fast k-mer counter for assembled genome analysis"],"prefix":"10.1093","volume":"38","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, Guangdong 510006, China"},{"name":"Center for Precision Health, School of Biomedical Informatics, The University of Texas Health Science Center at Houston , Houston, TX 77030, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yucheng","family":"Li","sequence":"additional","affiliation":[{"name":"School of Software Engineering, South China University of Technology , Guangzhou, Guangdong 510006, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9861-0082","authenticated-orcid":false,"given":"Daqiang","family":"Tan","sequence":"additional","affiliation":[{"name":"School of Software Engineering, South China University of Technology , Guangzhou, Guangdong 510006, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Juan","family":"Fu","sequence":"additional","affiliation":[{"name":"School of Medicine, South China University of Technology , Guangzhou, Guangdong 510006, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yelei","family":"Tang","sequence":"additional","affiliation":[{"name":"School of Software Engineering, South China University of Technology , Guangzhou, Guangdong 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, Guangdong 510006, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rong","family":"Zhao","sequence":"additional","affiliation":[{"name":"School of Software Engineering, South China University of Technology , Guangzhou, Guangdong 510006, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hongli","family":"Du","sequence":"additional","affiliation":[{"name":"School of Biology and Biological Engineering, South China University of Technology , Guangzhou, Guangdong 510006, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3477-0914","authenticated-orcid":false,"given":"Zhongming","family":"Zhao","sequence":"additional","affiliation":[{"name":"Center for Precision Health, School of Biomedical Informatics, The University of Texas Health Science Center at Houston , Houston, TX 77030, USA"},{"name":"Human Genetics Center, School of Public Health, The University of Texas Health Science Center at Houston , Houston, TX 77030, USA"},{"name":"MD Anderson Cancer Center UTHealth Graduate School of Biomedical Sciences , Houston, TX 77030, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2021,11,26]]},"reference":[{"key":"2023020108535277600_btab797-B1","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":"2023020108535277600_btab797-B2","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":"2023020108535277600_btab797-B3","doi-asserted-by":"crossref","first-page":"e00257-18","DOI":"10.1128\/mSystems.00257-18","article-title":"k-mer similarity, networks of microbial genomes, and taxonomic rank","volume":"3","author":"Bernard","year":"2018","journal-title":"mSystems"},{"key":"2023020108535277600_btab797-B4","doi-asserted-by":"crossref","first-page":"437","DOI":"10.1186\/s12859-018-2417-6","article-title":"PanDelos: a dictionary-based method for pan-genome content discovery","volume":"19","author":"Bonnici","year":"2018","journal-title":"BMC Bioinformatics"},{"key":"2023020108535277600_btab797-B5","doi-asserted-by":"crossref","first-page":"3584","DOI":"10.1093\/bioinformatics\/btv419","article-title":"Spaced seeds improve k-mer-based metagenomic classification","volume":"31","author":"B\u0159inda","year":"2015","journal-title":"Bioinformatics"},{"key":"2023020108535277600_btab797-B6","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":"F1000 Research"},{"key":"2023020108535277600_btab797-B7","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":"2023020108535277600_btab797-B8","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":"2023020108535277600_btab797-B9","doi-asserted-by":"crossref","first-page":"160","DOI":"10.1186\/1471-2105-14-160","article-title":"Disk-based k-mer counting on a PC","volume":"14","author":"Deorowicz","year":"2013","journal-title":"BMC Bioinformatics"},{"key":"2023020108535277600_btab797-B10","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":"2023020108535277600_btab797-B11","doi-asserted-by":"crossref","first-page":"1792","DOI":"10.1093\/nar\/gkh340","article-title":"MUSCLE: multiple sequence alignment with high accuracy and high throughput","volume":"32","author":"Edgar","year":"2004","journal-title":"Nucleic Acids Res"},{"key":"2023020108535277600_btab797-B12","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":"2023020108535277600_btab797-B13","first-page":"371","author":"Fan","year":"2013"},{"key":"2023020108535277600_btab797-B14","doi-asserted-by":"crossref","first-page":"3670","DOI":"10.1038\/s41467-020-17302-5","article-title":"Gradual polyploid genome evolution revealed by pan-genomic analysis of Brachypodium hybridum and its diploid progenitors","volume":"11","author":"Gordon","year":"2020","journal-title":"Nat. Commun"},{"key":"2023020108535277600_btab797-B15","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1101\/gr.828403","article-title":"Whole-genome sequence assembly for mammalian genomes: arachne 2","volume":"13","author":"Jaffe","year":"2003","journal-title":"Genome Res"},{"key":"2023020108535277600_btab797-B16","doi-asserted-by":"crossref","first-page":"e1007758","DOI":"10.1371\/journal.pgen.1007758","article-title":"A fast and agnostic method for bacterial genome-wide association studies: bridging the gap between k-mers and genetic events","volume":"14","author":"Jaillard","year":"2018","journal-title":"PLoS Genet"},{"key":"2023020108535277600_btab797-B17","doi-asserted-by":"crossref","first-page":"s13742","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":"2023020108535277600_btab797-B18","doi-asserted-by":"crossref","first-page":"R116","DOI":"10.1186\/gb-2010-11-11-r116","article-title":"Quake: quality-aware detection and correction of sequencing errors","volume":"11","author":"Kelley","year":"2010","journal-title":"Genome Biol"},{"key":"2023020108535277600_btab797-B19","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":"2023020108535277600_btab797-B20","doi-asserted-by":"crossref","first-page":"517","DOI":"10.1186\/1471-2164-9-517","article-title":"A new method to compute K-mer frequencies and its application to annotate large repetitive plant genomes","volume":"9","author":"Kurtz","year":"2008","journal-title":"BMC Genomics"},{"key":"2023020108535277600_btab797-B21","doi-asserted-by":"crossref","first-page":"12797","DOI":"10.1038\/ncomms12797","article-title":"Sequence element enrichment analysis to determine the genetic basis of bacterial phenotypes","volume":"7","author":"Lees","year":"2016","journal-title":"Nat. Commun"},{"key":"2023020108535277600_btab797-B22","first-page":"1","article-title":"Algorithmic improvements for fast concurrent Cuckoo hashing","volume":"2014","author":"Li","year":"2014","journal-title":"Proc. Ninth Eur. Conf. Comput. Syst. EuroSys"},{"key":"2023020108535277600_btab797-B23","author":"Li","year":"2015"},{"key":"2023020108535277600_btab797-B24","doi-asserted-by":"crossref","first-page":"2783","DOI":"10.1093\/bioinformatics\/btw345","article-title":"KCMBT: ak-mer counter based on multiple burst trees","volume":"32","author":"Mamun","year":"2016","journal-title":"Bioinformatics"},{"key":"2023020108535277600_btab797-B25","first-page":"7","article-title":"A benchmark study of k-mer counting methods for high-throughput sequencing","volume":"7","author":"Manekar","year":"2018","journal-title":"Gigascience"},{"key":"2023020108535277600_btab797-B26","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 -mers","volume":"27","author":"Marcais","year":"2011","journal-title":"Bioinformatics"},{"key":"2023020108535277600_btab797-B27","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1186\/1471-2105-12-333","article-title":"Efficient counting of k-mers in DNA sequences using a bloom filter","volume":"12","author":"Melsted","year":"2011","journal-title":"BMC Bioinformatics"},{"key":"2023020108535277600_btab797-B28","doi-asserted-by":"crossref","first-page":"1324","DOI":"10.1093\/bioinformatics\/btw832","article-title":"ntCard: a streaming algorithm for cardinality estimation in genomics data","volume":"33","author":"Mohamadi","year":"2017","journal-title":"Bioinformatics"},{"key":"2023020108535277600_btab797-B29","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":"2023020108535277600_btab797-B30","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":"2023020108535277600_btab797-B31","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":"2023020108535277600_btab797-B32","doi-asserted-by":"crossref","first-page":"e0228070","DOI":"10.1371\/journal.pone.0228070","article-title":"The number of k-mer matches between two DNA sequences as a function of k and applications to estimate phylogenetic distances","volume":"15","author":"R\u00f6hling","year":"2020","journal-title":"PLoS One"},{"key":"2023020108535277600_btab797-B33","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":"2023020108535277600_btab797-B34","doi-asserted-by":"crossref","first-page":"122","DOI":"10.3390\/genes8040122","article-title":"K-mer content, correlation, and position analysis of genome DNA sequences for the identification of function and evolutionary features","volume":"8","author":"Sievers","year":"2017","journal-title":"Genes (Basel)"},{"key":"2023020108535277600_btab797-B35","doi-asserted-by":"crossref","first-page":"e67","DOI":"10.1093\/nar\/gku138","article-title":"Strain\/species identification in metagenomes using genome-specific markers","volume":"42","author":"Tu","year":"2014","journal-title":"Nucleic Acids Res"},{"key":"2023020108535277600_btab797-B36","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1186\/s13062-015-0083-4","article-title":"KGCAK: a K-mer based database for genome-wide phylogeny and complexity evaluation","volume":"10","author":"Wang","year":"2015","journal-title":"Biol. Direct"},{"key":"2023020108535277600_btab797-B37","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":"2020","journal-title":"Brief. Bioinf"},{"key":"2023020108535277600_btab797-B38","doi-asserted-by":"crossref","first-page":"2004958","DOI":"10.1002\/advs.202004958","article-title":"DeepVISP: deep learning for virus site integration prediction and motif discovery","volume":"8","author":"Xu","year":"2021","journal-title":"Adv. Sci"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/advance-article-pdf\/doi\/10.1093\/bioinformatics\/btab797\/41546639\/btab797.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/38\/4\/933\/49009046\/btab797.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/38\/4\/933\/49009046\/btab797.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,12]],"date-time":"2023-11-12T22:04:34Z","timestamp":1699826674000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/38\/4\/933\/6443080"}},"subtitle":[],"editor":[{"given":"Tobias","family":"Marschall","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]}],"short-title":[],"issued":{"date-parts":[[2021,11,26]]},"references-count":38,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,1,27]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btab797","relation":{},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"value":"1367-4803","type":"print"},{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2022,2,15]]},"published":{"date-parts":[[2021,11,26]]}}}