The backpack quotient filter: A dynamic and space-efficient data structure for querying k-mers with abundance.

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• Genomic databases are growing rapidly, necessitating efficient data manipulation and querying.
• Determining sequence presence, absence, and abundance in large datasets is a key challenge.

Purpose of the Study:

• To introduce the Backpack Quotient Filter (BQF), a novel data structure for indexing k-mers.
• To demonstrate the BQF's superior space efficiency compared to existing methods like the Counting Quotient Filter (CQF).

Main Methods:

• Developed the Backpack Quotient Filter (BQF) for indexing k-mers.
• Redefined abundance information handling and implemented a new strategy for space efficiency.
• Evaluated BQF performance on complex datasets, including sea-water metagenomics sequences.

Main Results:

• The BQF provides greater space efficiency than the CQF, using up to four times less space on complex datasets.
• The BQF maintains essential features like abundance information and dynamicity with a very low false positive rate.
• BQF space efficiency increases with larger datasets, offering a scalable solution.

Conclusions:

• The Backpack Quotient Filter (BQF) is a highly space-efficient data structure for k-mer indexing.
• BQF addresses the growing need for scalable solutions in genomic data analysis.
• This method significantly improves the management and querying of large-scale genomic information.