Turtle: identifying frequent k-mers with cache-efficient algorithms.

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• K-mer frequency counting is crucial for high-throughput sequencing data analysis.
• Infrequent k-mers often indicate sequencing errors, while frequent k-mers are vital for error correction and de novo assembly.
• Current methods face challenges with memory requirements, especially for large datasets and genomes.

Purpose of the Study:

• To develop a novel method for efficient k-mer frequency counting that balances time, space, and accuracy.
• To reduce memory footprint and improve computational speed for analyzing high-coverage sequencing libraries and large genomes.

Main Methods:

• Utilizes a pattern-blocked Bloom filter to efficiently discard infrequent k-mers.
• Employs a novel sort-and-compact scheme for k-mer counting, optimizing for cache efficiency.
• A variant incorporates a counting Bloom filter for further memory reduction, accepting a false-negative rate.

Main Results:

• The proposed method significantly reduces memory requirements and running times compared to state-of-the-art approaches.
• Achieves efficient k-mer extraction for large-scale datasets, including human genomes.
• Demonstrates improved performance by minimizing cache misses through its specialized data structures and algorithms.

Conclusions:

• The novel k-mer counting method offers a more efficient and scalable solution for genomic data analysis.
• Provides a valuable tool for read error correction and de novo assembly, particularly for large and complex genomes.
• The software is publicly available, facilitating its adoption in the research community.