FM-index

FM-index implements a compressed full-text index enabling efficient exact-match counting and locating in nucleotide and amino acid sequence analysis.

Key Features:

• AWFM-index implementation: AvxWindowedFMindex (AWFM-index) provides an FM-index implementation optimized for nucleotide and amino acid sequence analysis.
• Exact-match queries: Performs exact match count and locate queries on sequence data.
• Performance improvements vs SeqAn3: Delivers approximately 2–4× faster exact-match count and locate queries for nucleotide searches and 2–6× faster for amino acid searches in single-threaded comparisons to SeqAn3.
• Strided bit-vector storage: Employs a novel strided bit-vector format to store FM-index data and optimize memory access patterns.
• AVX2 bitwise computation: Uses AVX2 bitwise instructions to accelerate computation of the FM-index occurrence function.
• Cache-efficient k-mer lookup tables: Incorporates cache-efficient lookup tables for partial k-mer searches to reduce latency for frequent queries.
• Parallelization: Designed to trivially parallelize across multiple threads for scalable multi-threaded execution.
• On-disk suffix array support: Supports efficient on-disk storage for the memory-intensive suffix array component.

Scientific Applications:

• Genome assembly: Accelerates pattern matching steps in genome assembly workflows via faster exact-match queries.
• Variant calling: Speeds sequence search operations used in variant detection and genotyping pipelines.
• Comparative genomics: Enables rapid matching of nucleotide and amino acid sequences for comparative analyses.
• Genetic and proteomic research: Supports high-throughput analyses of genetic and proteomic sequence datasets by reducing computational time for substring queries.

Methodology:

The implementation stores FM-index data in a strided bit-vector format, computes the occurrence function using AVX2 bitwise instructions, employs cache-efficient lookup tables for partial k-mer searches, and supports multithreading and on-disk suffix array storage.