sBWT

sBWT implements efficient indexing and alignment of NGS data by constructing an FM-index (Full-text index in Minute space) derived from a Burrows-Wheeler transform variant, the Schindler transform, to enable hardware-accelerated fast string matching across large genomic datasets and collections of sequencing reads.

Key Features:

• FM-index support: Uses the Full-text index in Minute space (FM-index) derived from the Burrows-Wheeler transform for fast exact and inexact string matching.
• Schindler transform: Employs a BWT variant called the Schindler transform for index construction.
• Hardware-acceleration-friendly algorithms: Index construction algorithms are adapted for hardware parallelism to improve speed and scalability.
• CPU and GPU implementations: Implemented in C++ with both CPU-only and GPU-accelerated versions.
• Optimized for repetitive references: Indexing and search methods are designed to perform efficiently on repetitive reference sequences.
• High-throughput NGS support: Targets large collections of sequencing reads and large genomic datasets for rapid search and alignment.
• Performance improvements: Demonstrates substantial speed improvements over other BWT-based indexing approaches, including those relying on CPU-based index construction or blockwise suffix sorting.

Scientific Applications:

• Read alignment: Rapid alignment of sequencing reads against complex genomes using FM-index-based string matching.
• Large-scale indexing: Construction of scalable indices for large genomic datasets and extensive sequencing-read collections.
• Accelerated genomic searches: High-throughput search and retrieval in repetitive reference sequences enabled by hardware-parallelizable indexing.
• NGS data processing: High-performance indexing and search workflows for next-generation sequencing analyses.

Methodology:

Index construction uses the Schindler transform (a Burrows-Wheeler transform variant) to build an FM-index (Full-text index in Minute space); implemented in C++ with CPU-only and GPU-accelerated versions and hardware-parallelizable indexing algorithms aimed at accelerating indexing and searching compared with CPU-based or blockwise suffix-sorting approaches.