Raptor

Raptor performs approximate searching of large collections of nucleotide sequences to enable fast, space-efficient querying of multiple input queries such as next-generation sequencing reads or transcripts using winnowing minimizers and interleaved Bloom filters.

Key Features:

• Winnowing minimizers: Raptor employs winnowing minimizers to select representative k-mers from input sequences, reducing dataset complexity and size for efficient approximate searching.
• Interleaved Bloom Filters (IBFs): The tool uses an extended form of interleaved Bloom filters as the core data structure for set membership testing to handle large nucleotide sequence collections space-efficiently.
• Probabilistic thresholding: Raptor incorporates probabilistic thresholding for minimizers to balance false positives and computational efficiency by adjusting sensitivity and specificity.
• Compression and partitioning: The system supports compression and partitioning of IBFs to enable effective use of secondary memory for datasets that exceed primary memory capacity.

Scientific Applications:

• Approximate sequence querying: Performing approximate searches of large nucleotide sequence collections using multiple queries such as next-generation sequencing reads or transcripts.
• DREAM-Yara re-implementation: Raptor has been used to re-implement DREAM-Yara, a distributed read mapping tool.
• Performance evaluation: Validation and benchmarking have been performed with simulated and real datasets to assess performance and limitations.

Methodology:

Representative k-mers are defined using winnowing minimizers, inserted into an extended interleaved Bloom filter, probabilistic thresholding is applied to adjust sensitivity and specificity, and IBFs are compressed and partitioned to utilize secondary memory.