A fast, lock-free approach for efficient parallel counting of occurrences of k -mers
Open accessAbstract
Motivation: Counting the number of occurrences of every k-mer (substring of length k) in a long string is a central subproblem in many applications, including genome assembly, error correction of sequencing reads, fast multiple sequence alignment and repeat detection. Recently, the deep sequence coverage generated by next-generation sequencing technologies has caused the amount of sequence to be processed during a genome project to grow rapidly, and has rendered current k-mer counting tools too slow and memory intensive. At the same time, large multicore computers have become commonplace in research facilities allowing for a new parallel computational paradigm. Results: We propose a new k-mer counting algorithm and associated implementation, called Jellyfish, which is fast and memory efficient. It is based on a multithreaded, lock-free hash table optimized for counting k-mers up to 31 bases in length. Due to their flexibility, suffix arrays have been the data structure of choice for solving many string problems. For the task of k-mer counting, important in many biological applications, Jellyfish offers a much faster and more memory-efficient solution. Availability: The Jellyfish software is written in C++ and is GPL licensed. It is available for download at http://www.cbcb.umd.edu/software/jellyfish. Contact: gmarcais@umd.edu Supplementary information: Supplementary data are available at Bioinformatics online.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
The saola genome assembly had a total length of 2.7 Gbp, consistent with the k-mer-based genome size estimate of 2.77 Gb.
“had a total length of 2.7 Gbp, consistent with the k-mer-based genome size estimate of 2.77 Gb.37”
From Genomes of critically endangered saola are shaped by population structure and purging (2025) · cites this paper as [37]
Cites
The sequence and de novo assembly of the giant panda genome
Li, R., Fan, W., Tian, G., Zhu, H., He, L., Cai, J., Huang, Q., Cai, Q., Li, B., Bai, Y., et al. (2010) · Nature · doi:10.1038/nature08696 · Cited by 1,180 · see citing works
Dalloul, R. A., Long, J. A., Zimin, A. V., Aslam, L., Beal, K., Ann Blomberg, L., Bouffard, P., Burt, D. W., Crasta, O., Crooijmans, R. P. M. A., et al. (2010) · PLoS Biology · doi:10.1371/journal.pbio.1000475 · Cited by 416 · see citing works
Flagged first, then by citations
Cited by
Sorted by citations
Kraken: ultrafast metagenomic sequence classification using exact alignments
Wood, D. E., & Salzberg, S. L. (2014) · Genome Biology · doi:10.1186/gb-2014-15-3-r46 · Cited by 4,521 · see citing works
Molecular and genetic properties of tumors associated with local immune cytolytic activity
Rooney, M. S., Shukla, S. A., Wu, C. J., Getz, G., & Hacohen, N. (2015) · Cell · doi:10.1016/j.cell.2014.12.033 · Cited by 3,825 · see citing works
Centrifuge: rapid and sensitive classification of metagenomic sequences
Kim, D., Song, L., Breitwieser, F. P., & Salzberg, S. L. (2016) · Genome Research · doi:10.1101/gr.210641.116 · Cited by 1,438 · see citing works
Spatial proteogenomics reveals distinct and evolutionarily conserved hepatic macrophage niches
Guilliams, M., Bonnardel, J., Haest, B., Vanderborght, B., Wagner, C., Remmerie, A., Bujko, A., Martens, L., Thoné, T., Browaeys, R., et al. (2022) · Cell · doi:10.1016/j.cell.2021.12.018 · Cited by 985 · see citing works
SCENIC+: single-cell multiomic inference of enhancers and gene regulatory networks
Bravo González-Blas, C., De Winter, S., Hulselmans, G., Hecker, N., Matetovici, I., Christiaens, V., Poovathingal, S., Wouters, J., Aibar, S., & Aerts, S. (2023) · Nature Methods · doi:10.1038/s41592-023-01938-4 · Cited by 778 · see citing works
Readhead, B., Haure-Mirande, J.-V., Funk, C. C., Richards, M. A., Shannon, P., Haroutunian, V., Sano, M., Liang, W. S., Beckmann, N. D., Price, N. D., et al. (2018) · Neuron · doi:10.1016/j.neuron.2018.05.023 · Cited by 708 · see citing works
Patro, R., Mount, S. M., & Kingsford, C. (2014) · Nature Biotechnology · doi:10.1038/nbt.2862 · Cited by 586 · see citing works
Self-citationComplete genomic and epigenetic maps of human centromeres
Altemose, N., Logsdon, G. A., Bzikadze, A. V., Sidhwani, P., Langley, S. A., Caldas, G. V., Hoyt, S. J., Uralsky, L., Ryabov, F. D., Shew, C. J., et al. (2022) · Science · doi:10.1126/science.abl4178 · Cited by 618 · see citing works
Ancient gene linkages support ctenophores as sister to other animals
Schultz, D. T., Haddock, S. H. D., Bredeson, J. V., Green, R. E., Simakov, O., & Rokhsar, D. S. (2023) · Nature · doi:10.1038/s41586-023-05936-6 · Cited by 362 · see citing works
Alterations in Enteric Virome Are Associated With Colorectal Cancer and Survival Outcomes
Nakatsu, G., Zhou, H., Wu, W. K. K., Wong, S. H., Coker, O. O., Dai, Z., Li, X., Szeto, C.-H., Sugimura, N., Lam, T. Y.-T., et al. (2018) · Gastroenterology · doi:10.1053/j.gastro.2018.04.018 · Cited by 386 · see citing works
Ebler, J., Ebert, P., Clarke, W. E., Rausch, T., Audano, P. A., Houwaart, T., Mao, Y., Korbel, J. O., Eichler, E. E., Zody, M. C., et al. (2022) · Nature Genetics · doi:10.1038/s41588-022-01043-w · Cited by 277 · see citing works
Pendleton, A. L., Shen, F., Taravella, A. M., Emery, S., Veeramah, K. R., Boyko, A. R., & Kidd, J. M. (2018) · BMC Biology · doi:10.1186/s12915-018-0535-2 · Cited by 156 · see citing works
A survey of k-mer methods and applications in bioinformatics
Moeckel, C., Mareboina, M., Konnaris, M. A., Chan, C. S. Y., Mouratidis, I., Montgomery, A., Chantzi, N., Pavlopoulos, G. A., & Georgakopoulos-Soares, I. (2024) · Computational and Structural Biotechnology Journal · doi:10.1016/j.csbj.2024.05.025 · Cited by 131 · see citing works
“…contamination by comparing observed k-mers against a BFCounter[201], CHTKC [202], Discount[203], DSK2 [204], GECKO[205], Gerbil [206], Jellyfish2[8], KAnalyze [207], KCMBT[208], KCOSS [209], KHMer[210], KMC3 [45], KmerAnalysis.jl [211], Kmerator[212], Kounta[213], Krust[214], Meryl[46],…”
BackgroundMethodInfluentialHu, S., Liu, S., Bian, Y., Poddar, M., Singh, S., Cao, C., McGaughey, J., Bell, A., Blazer, L. L., Adams, J. J., et al. (2022) · Cell Reports Medicine · doi:10.1016/j.xcrm.2022.100754 · Cited by 118 · see citing works
SCENIC+: single-cell multiomic inference of enhancers and gene regulatory networks
González-Blas, C. B., De Winter, S., Hulselmans, G., Hecker, N., Matetovici, I., Christiaens, V., Poovathingal, S., Wouters, J., Aibar, S., & Aerts, S. (2022) · doi:10.1101/2022.08.19.504505 · Cited by 778 · see citing works
A reference genome of the Chinese hamster based on a hybrid assembly strategy
Rupp, O., MacDonald, M. L., Li, S., Dhiman, H., Polson, S., Griep, S., Heffner, K., Hernandez, I., Brinkrolf, K., Jadhav, V., et al. (2018) · Biotechnology and Bioengineering · doi:10.1002/bit.26722 · Cited by 107 · see citing works
Bravo González-Blas, C., Matetovici, I., Hillen, H., Taskiran, I. I., Vandepoel, R., Christiaens, V., Sansores-García, L., Verboven, E., Hulselmans, G., Poovathingal, S., et al. (2024) · Nature Cell Biology · doi:10.1038/s41556-023-01316-4 · Cited by 85 · see citing works
“To filter highly repetitive regions, the abundance of k -mers was obtained from the background transcriptome using Jellyfish 84 .”
Genome-Wide Signatures of Adaptation to Extreme Environments in Red Algae
Cho, C. H., Park, S. I., Huang, T.-Y., Lee, Y., Ciniglia, C., Yadavalli, H. C., Yang, S. W., Bhattacharya, D., & Yoon, H. S. (2023) · Nature Communications · doi:10.1038/s41467-022-35566-x · Cited by 83 · see citing works
Single and multiple gene knockouts by CRISPR–Cas9 in maize
Doll, N. M., Gilles, L. M., Gérentes, M.-F., Richard, C., Just, J., Fierlej, Y., Borrelli, V. M. G., Gendrot, G., Ingram, G. C., Rogowsky, P. M., et al. (2019) · Plant Cell Reports · doi:10.1007/s00299-019-02378-1 · Cited by 71 · see citing works
A chromosome-scale genome assembly and karyotype of the ctenophore <i>Hormiphora californensis</i>
Schultz, D. T., Francis, W. R., McBroome, J. D., Christianson, L. M., Haddock, S. H. D., & Green, R. E. (2021) · G3 Genes|Genomes|Genetics · doi:10.1093/g3journal/jkab302 · Cited by 35 · see citing works
Genomes of critically endangered saola are shaped by population structure and purging
Garcia-Erill, G., Liu, S., Le, M. D., Hurley, M. M., Nguyen, H. D., Nguyen, D. Q., Nguyen, D. H., Santander, C. G., Sánchez Barreiro, F., Gomes Martins, N. F., et al. (2025) · Cell · doi:10.1016/j.cell.2025.03.040 · Cited by 10 · see citing works
Enhancer grammar of liver cell types and hepatocyte zonation states
González-Blas, C. B., Matetovici, I., Hillen, H., Taskiran, I. I., Vandepoel, R., Christiaens, V., Sansores-García, L., Verboven, E., Hulselmans, G., Poovathingal, S., et al. (2022) · doi:10.1101/2022.12.08.519575 · Cited by 5 · see citing works
- Authors
- Marçais, G., & Kingsford, C.
- Affiliations
- University of Maryland, College Park (US)
- Corresponding author
- Marçais, Guillaume
- Venue
- Bioinformatics
- Publisher
- Oxford University Press (OUP)
- Published
- 2011-01-07
- Volume
- 27
- Issue
- 6
- Pages
- 764-770
- ISSN
- 1367-4803 (ISSN-L)
- 1367-4811
- PMC
- PMC3051319
- OpenAlex
- W2096128575
- Cited by
- 4,661
- References
- 2
- Citations by year
- 2026: 471 · 2025: 706 · 2024: 637 · 2023: 479 · 2022: 504 · 2021: 547 · 2020: 348 · 2019: 246 · 2018: 204 · 2017: 150 · 2016: 125 · 2015: 87 · 2014: 82 · 2013: 47 · 2012: 15
- FWCI
- 45.06
- Type
- journal article
- Language
- en
- Open access
- bronze
- doi.org
- Locations
- Bioinformatics (publishedVersion)
- PubMed Central (publishedVersion)
- PubMed (publishedVersion)
- Funders
- National Science Foundation (0616585, 0849899, 0812111)
- National Institutes of Health
- National Human Genome Research Institute (1R01HG0294501)
- National Institute of Allergy and Infectious Diseases (R21AI085376)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Algorithms and Data Compression
- Life Sciences › Biochemistry, Genetics and Molecular Biology › Molecular Biology › Genomics and Phylogenetic Studies
- Life Sciences › Biochemistry, Genetics and Molecular Biology › Molecular Biology › Fractal and DNA sequence analysis
- Keywords
- k-mer counting, jellyfish, multithreaded algorithms, suffix arrays, genome assembly, memory efficiency
- MeSH terms
- Algorithms, Animals, Base Sequence, Humans, Software, Sequence Alignment, Genome, Sequence Analysis, DNA, Computational Biology
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
