English | 简体中文
A BWA-MEM style short-read aligner implemented in Rust from scratch. Supports FASTA/FASTQ input and SAM output.
- FM-Index Construction — Suffix array, BWT, occurrence table, with configurable SA sampling rate
- SMEM Seeding — Super-Maximal Exact Match seed finding with bidirectional extension
- Seed Chaining — Dynamic programming-based seed chain scoring
- Smith-Waterman — Banded local alignment with affine gap penalties and CIGAR generation
- Full Pipeline — Index building + read mapping in a single binary
- FASTA/FASTQ I/O — Multi-line FASTA and standard FASTQ parsing
- SAM Output — Standard SAM format with proper flags, MAPQ, and timestamps
├── src/
│ ├── main.rs # CLI entry (clap)
│ ├── lib.rs # Library entry
│ ├── error.rs # Custom error types (BwaError / BwaResult)
│ ├── io/ # FASTA/FASTQ parsing, SAM output
│ ├── index/ # FM index (SA, BWT, FM, Builder)
│ ├── align/ # Alignment (SMEM, Chain, SW, Pipeline)
│ └── util/ # DNA encoding/decoding/reverse complement
├── tests/ # Integration tests
├── benches/ # Benchmarks
├── examples/ # Examples
├── data/ # Test data (toy.fa / toy_reads.fq)
└── docs/ # Architecture, tutorial, full replication plan
git clone https://github.com/LessUp/bwa-rust.git
cd bwa-rust
cargo build --releaseBinary at target/release/bwa-rust.
- Rust 1.70+
- Linux, macOS, Windows
cargo test
# test result: ok. 133 passed; 0 failed; 0 ignoredcargo benchcargo run --example simple_align| Document | Description |
|---|---|
docs/architecture.md |
Module architecture, index format, algorithm flow |
docs/tutorial.md |
Tutorial: implement a BWA-style aligner from scratch |
docs/plan.md |
Full BWA replication roadmap |
ROADMAP.md |
Development roadmap & version strategy |
CHANGELOG.md |
Version changelog |
Contributions welcome! See CONTRIBUTING.md.