fimpera

fimpera enhances counting Approximate Membership Query (cAMQ) data structures to index k-mers with abundance information for efficient querying of petabyte-scale high-throughput sequencing datasets.

Key Features:

• cAMQ compatibility: Enhances counting Approximate Membership Query (cAMQ) data structures, including counting Bloom filters.
• k-mer abundance indexing: Indexes large numbers of k-mers together with their abundance counts.
• False positive reduction and precision: When applied to counting Bloom filters, reduces the false positive rate by two orders of magnitude, improving precision of reported k-mer abundances.
• Filter size reduction mode: Provides an alternative mode that reduces counting Bloom filter size by two orders of magnitude without compromising precision.
• Memory and performance: Does not add memory overhead and can reduce query times.
• Scalability: Targets petabyte-scale datasets produced by high-throughput sequencing technologies.

Scientific Applications:

• Metagenomics: Improves detection and abundance estimation of k-mers in metagenomic datasets.
• Large-scale sequence indexing: Enables indexing and abundance-aware queries on petabyte-scale sequencing datasets.
• Abundance-based analyses: Supports analyses that require precise k-mer abundance information.

Methodology:

Leverages counting Approximate Membership Queries (cAMQ) data structures such as counting Bloom filters and applies a novel algorithm to reduce false positives or reduce filter size without introducing additional memory overhead.