KCOSS: an ultra-fast k-mer counter for assembled genome analysis
- 26 November 2021
- journal article
- research article
- Published by Oxford University Press (OUP) in Bioinformatics
- Vol. 38 (4) , 933-940
Abstract
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. 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. The KCOSS software is implemented in C++. It is freely available on GitHub: https://github.com/kcoss-2021/KCOSS. Supplementary data are available at Bioinformatics online.Keywords
Funding Information
- National Key R&D Program of China (2018YFC0910200)
- Cancer Prevention and Research Institute of Texas [CPRIT (RP180734)
This publication has 34 references indexed in Scilit:
- Turtle: Identifying frequent k -mers with cache-efficient algorithmsBioinformatics, 2014
- Strain/species identification in metagenomes using genome-specific markersNucleic Acids Research, 2014
- Disk-based k-mer counting on a PCBMC Bioinformatics, 2013
- DSK: k-mer counting with very low memory usageBioinformatics, 2013
- Efficient counting of k-mers in DNA sequences using a bloom filterBMC Bioinformatics, 2011
- A fast, lock-free approach for efficient parallel counting of occurrences of k-mersBioinformatics, 2011
- Quake: quality-aware detection and correction of sequencing errorsGenome Biology, 2010
- A new method to compute K-mer frequencies and its application to annotate large repetitive plant genomesBMC Genomics, 2008
- MUSCLE: multiple sequence alignment with high accuracy and high throughputNucleic Acids Research, 2004
- Whole-Genome Sequence Assembly for Mammalian Genomes: Arachne 2Genome Research, 2003