Efficient counting of k-mers in DNA sequences using a bloom filter.

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• K-mer counting is fundamental for DNA sequence analysis, including genome assembly and error correction.
• Large datasets pose memory challenges, with erroneous singleton k-mers consuming significant storage.
• Existing methods struggle with memory limitations when processing massive sequence data.

Purpose of the Study:

• To develop a memory-efficient method for counting k-mers in large DNA sequence datasets.
• To address the challenge of memory overflow caused by sequencing errors and singleton k-mers.
• To improve the performance of bioinformatics algorithms reliant on k-mer analysis.

Main Methods:

• Utilizes a Bloom filter, a probabilistic data structure, for implicit in-memory storage of observed k-mers.
• Employs a two-sweep approach: first, identify non-unique k-mers using the Bloom filter, then count them exactly.
• Implements the methodology in a C++ software called BFCounter.

Main Results:

• Achieves significant memory savings, up to 50% in example datasets, compared to current software.
• Identifies all non-unique k-mers accurately after the initial filtering.
• Demonstrates a practical reduction in memory requirements for k-mer counting algorithms.
• Reports modest increases in computational time as a trade-off for memory efficiency.

Conclusions:

• The BFCounter software provides an efficient solution for memory-intensive k-mer counting.
• This method is applicable to various bioinformatics pipelines dealing with large-scale sequence data.
• The approach effectively mitigates memory issues caused by sequencing errors in k-mer analysis.