research-article

A fast, lock-free approach for efficient parallel counting of occurrences of k-mers

Authors:

Guillaume Marçais,

Carl KingsfordAuthors Info & Claims

Bioinformatics, Volume 27, Issue 6

Pages 764 - 770

https://doi.org/10.1093/bioinformatics/btr011

Published: 01 March 2011 Publication History

Abstract

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: [email protected]

Supplementary information: Supplementary data are available at Bioinformatics online.

Cited By

View all

Wu LZhou MXu WVenkat ARosing TSkadron K(2023)Abakus: Accelerating k-mer Counting with Storage TechnologyACM Transactions on Architecture and Code Optimization10.1145/363295221:1(1-26)Online publication date: 21-Nov-2023
https://dl.acm.org/doi/10.1145/3632952
Islam RYusuf MBiswas SRahman A(2023)Optimal K-mer Analysis for Alignment Free Phylogenetic TreeProceedings of the 2023 10th International Conference on Bioinformatics Research and Applications10.1145/3632047.3632058(67-73)Online publication date: 22-Sep-2023
https://dl.acm.org/doi/10.1145/3632047.3632058
Kromer-Edwards CWang MYoon B(2023)Optimizing K-Mer Fingerprint Generation for Machine LearningProceedings of the 14th ACM International Conference on Bioinformatics, Computational Biology, and Health Informatics10.1145/3584371.3612946(1-5)Online publication date: 3-Sep-2023
https://dl.acm.org/doi/10.1145/3584371.3612946
Show More Cited By

A fast, lock-free approach for efficient parallel counting of occurrences of k-mers
1. Applied computing
  1. Life and medical sciences

Recommendations

How independent are the appearances of n-mers in different genomes?

Motivation: Analysis of statistical properties of DNA sequences is important for evolutional biology as well as for DNA probe and PCR technologies. These technologies, in turn, can be used for organism identification, which implies applications in ...
Effective Parallel Multicore-Optimized K-mers Counting Algorithm
Proceedings of the 42nd International Conference on SOFSEM 2016: Theory and Practice of Computer Science - Volume 9587

For many bioinformatics applications it is crucial to know frequencies of all subsequences of length k k-mers constructed from reads short-reads that are obtained in process of DNA sequencing. We present an effective parallel algorithm for k-mers ...
Frigate: a fast, in-memory tool for counting and querying k-mers
ICBBT '21: Proceedings of the 2021 13th International Conference on Bioinformatics and Biomedical Technology

K-mer counting is an important step in many bioinformatics applications including genome assembly, sequence error correction, and sequence alignment. As the advancements in next generation sequencing technologies have resulted in tremendous growth of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Bioinformatics Volume 27, Issue 6

March 2011

149 pages

ISSN:1367-4803

Issue’s Table of Contents

Publisher

Oxford University Press, Inc.

United States

Publication History

Published: 01 March 2011

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

45
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 19 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Wu LZhou MXu WVenkat ARosing TSkadron K(2023)Abakus: Accelerating k-mer Counting with Storage TechnologyACM Transactions on Architecture and Code Optimization10.1145/363295221:1(1-26)Online publication date: 21-Nov-2023
https://dl.acm.org/doi/10.1145/3632952
Islam RYusuf MBiswas SRahman A(2023)Optimal K-mer Analysis for Alignment Free Phylogenetic TreeProceedings of the 2023 10th International Conference on Bioinformatics Research and Applications10.1145/3632047.3632058(67-73)Online publication date: 22-Sep-2023
https://dl.acm.org/doi/10.1145/3632047.3632058
Kromer-Edwards CWang MYoon B(2023)Optimizing K-Mer Fingerprint Generation for Machine LearningProceedings of the 14th ACM International Conference on Bioinformatics, Computational Biology, and Health Informatics10.1145/3584371.3612946(1-5)Online publication date: 3-Sep-2023
https://dl.acm.org/doi/10.1145/3584371.3612946
Narayanan VDetweiler DHuang TBurtsev AFedorova ANarayanan DDi Luna GQuerzoni L(2023)DRAMHiT: A Hash Table Architected for the Speed of DRAMProceedings of the Eighteenth European Conference on Computer Systems10.1145/3552326.3587457(817-834)Online publication date: 8-May-2023
https://dl.acm.org/doi/10.1145/3552326.3587457
dos Santos RRamachandran RVieira MSukhatme G(2023)Parallel multi-speed Pursuit-Evasion Game algorithmsRobotics and Autonomous Systems10.1016/j.robot.2023.104382163:COnline publication date: 1-May-2023
https://dl.acm.org/doi/10.1016/j.robot.2023.104382
Edippuliarachchi BGamlath DAmaratunga RBrihadiswaran GJayasena S(2022)Quill: A Memory Efficient k-mer Counting and k-mer Querying Tool for Commodity ClustersProceedings of the 14th International Conference on Bioinformatics and Biomedical Technology10.1145/3543377.3543389(79-88)Online publication date: 27-May-2022
https://dl.acm.org/doi/10.1145/3543377.3543389
Andriotis PKirby MTakasu A(2022)Bu-Dash: a universal and dynamic graphical password scheme (extended version)International Journal of Information Security10.1007/s10207-022-00642-222:2(381-401)Online publication date: 4-Dec-2022
https://dl.acm.org/doi/10.1007/s10207-022-00642-2
Mocheng LZhiguang CNong XYang LXi LTao C(2022)TopKmer: Parallel High Frequency K-mer Counting on Distributed MemoryNetwork and Parallel Computing10.1007/978-3-031-21395-3_9(96-107)Online publication date: 24-Sep-2022
https://dl.acm.org/doi/10.1007/978-3-031-21395-3_9
Zhang XYu YMok CMacLeod JLiu JJiang HHuang XZhang J(2021)GazelleProceedings of the 12th ACM International Conference on Bioinformatics, Computational Biology, and Health Informatics10.1145/3459930.3469548(1-8)Online publication date: 1-Aug-2021
https://dl.acm.org/doi/10.1145/3459930.3469548
Kashfeen AMcMillan LJiang HHuang XZhang J(2021)FrontierProceedings of the 12th ACM International Conference on Bioinformatics, Computational Biology, and Health Informatics10.1145/3459930.3469545(1-10)Online publication date: 1-Aug-2021
https://dl.acm.org/doi/10.1145/3459930.3469545
Show More Cited By

Abstract

Cited By

Recommendations

How independent are the appearances of n-mers in different genomes?

Effective Parallel Multicore-Optimized K-mers Counting Algorithm

Frigate: a fast, in-memory tool for counting and querying k-mers

Comments

Information

Published In

Publisher

Publication History

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations