# Pipeline Architecture

kira-ls-aligner is organized as a strict multi-stage pipeline. Each stage lives in its own file under `src/pipeline/` and has explicit input/output structs. This keeps data flow clear, makes stages testable in isolation, and enables targeted optimization.

## Data Flow (High-Level)

1. **Stage 0 - Input** (`stage0_input.rs`)
   - Reads a batch of input reads (FASTA/FASTQ). Multiple input files are supported.
   - Output: `InputBatch { reads }`.

2. **Stage 1 - Sketch** (`stage1_sketch.rs`)
   - Computes minimizers for each read (minimap2-style canonical k-mers).
   - Emits basic per-batch stats (read length p50/p90, avg minimizers, avg read length).
   - Output: `SketchBatch { reads, sketches }`.

3. **Stage 2 - Seeding** (`stage2_seeding.rs`)
   - Ranked/pruned seeding with diagonal aggregation.
   - Each minimizer bucket emits only top-K hits (deterministic).
   - Minimizers on the same diagonal are collapsed into ProtoAnchors.
   - Exact MEM extension is optional and only applied to top candidates.
   - Output: `SeedBatch { reads, anchors, stats }`.

4. **Stage 3 - Chaining** (`stage3_chaining.rs`)
   - RMQ/Fenwick LIS-like chaining in O(n log n).
   - Gap penalties combine linear and logarithmic components.
   - Early pruning removes dominated anchors and emits only competitive chains.
   - Output: `ChainBatch { reads, chains, stats }`.

5. **Stage 4 - Alignment** (`stage4_alignment.rs`)
   - Runs ungapped prefilter on top chains (top-K by chaining score).
   - Adds chain-confidence ACCEPT path using score margin, diagonal consistency, coverage ratio, and normalized ungapped score.
   - Prefilter may ACCEPT (skip DP), REJECT, or FALLBACK to DP.
   - Performs banded Smith-Waterman for FALLBACK chains, with SIMD (AVX2/NEON) batching where possible.
   - Uses X-drop and safe early-abort bounds to reduce wasted DP work.
   - Output: `AlignBatch { reads, alignments }`.

6. **Stage 5 - Scoring** (`stage5_scoring.rs`)
   - Assigns MAPQ, primary/secondary flags, and suboptimal score (`XS`).
   - Output: `ScoredBatch { reads, alignments }`.

7. **Stage 6 - Output** (`stage6_output.rs`)
   - Writes SAM records with bwa-mem compatible flags and tags (NM, MD, AS, XS, RG).

## Auto Mode Selection

When `-x auto` (default), the first batch is used to classify the dataset as short, long, or hybrid using:
- Read length distribution (p50/p90)
- Ungapped identity/mismatch stats from the prefilter
- Chain density (chains/read) and minimizer density

The selected mode is applied to subsequent batches and logged once when `KIRA_STATS=1`.

## Stage Details

### Stage 0 - Input
- **Input:** one or more FASTA/FASTQ files.
- **Output:** `InputBatch` containing `Vec<ReadRecord>`.
- **Notes:** uses `needletail` and mmap-backed I/O; batches are sized by CLI option `-K` (bases).

### Stage 1 - Sketch (Minimizers)
- **Input:** `InputBatch`.
- **Output:** `SketchBatch` with `ReadSketch` per read.
- **Algorithm:**
  - Canonical k-mers, rolling hash, windowed minimizers via monotonic deque.
- **Performance:**
  - O(n) per read; SIMD hooks prepared in `simd` module for future hashing acceleration.

### Stage 2 - Seeding
- **Input:** `SketchBatch` + index.
- **Output:** `SeedBatch` with pruned anchors and seeding stats.
- **Algorithm:**
  - Minimizer lookup into per-hash buckets, emit only top-K hits per bucket.
  - Aggregate hits by diagonal into ProtoAnchors before extension.
  - Exact MEM extension is optional and only applied to top candidates.
  - Hard caps for anchors per read and per diagonal are enforced before chaining.
- **Performance:**
  - Fewer anchors reduce chaining and DP pressure dramatically.

### Stage 3 - Chaining
- **Input:** `SeedBatch`.
- **Output:** `ChainBatch` with chaining stats.
- **Algorithm:**
  - Sort anchors by reference position.
  - O(n log n) RMQ/Fenwick chaining (LIS-like).
  - Gap penalties use linear + log terms.
  - Early pruning drops dominated anchors.
- **Performance:**
  - Sub-quadratic chaining even with high anchor counts.

### Stage 4 - Alignment
- **Input:** `ChainBatch` + reference.
- **Output:** `AlignBatch`.
- **Algorithm:**
  - Ungapped prefilter on top chains (top-K by chaining score).
  - Chain-confidence ACCEPT uses score margin, diagonal consistency, coverage ratio, and normalized ungapped score.
  - FALLBACK path runs banded Smith-Waterman around chain diagonals.
  - X-drop and safe early-abort bounds reduce wasted DP work.
- **Performance:**
  - Banded DP reduces memory to O(bandwidth * read_len).
  - SIMD batching is used when read lengths and windows match.

### Stage 5 - Scoring / MAPQ
- **Input:** `AlignBatch`.
- **Output:** `ScoredBatch`.
- **Algorithm:**
  - Primary alignment = best score.
  - Secondary alignments flagged with MAPQ 0.
  - MAPQ approximates bwa-mem/minimap2 behavior with a 60 cap.

### Stage 6 - Output
- **Input:** `ScoredBatch` + `SamWriter`.
- **Output:** SAM records.
- **Tags:** NM, MD, AS, XS, RG (with fast-output optionally suppressing heavy tags).
- **Flags:** primary/secondary/supplementary compatible with bwa-mem semantics.

## Performance Notes

- Thread parallelism is applied at the per-read level via Rayon.
- The reference index is immutable and shared across threads.
- Batch processing avoids unbounded memory usage and improves cache locality.
- CUDA support is optional behind the `cuda` feature gate and accelerates the
  batched Spectral Sieve prefilter. Builds with a stub PTX are rejected when
  the GPU backend is initialized.

## Extensibility

Each stage can be optimized independently (SIMD hashing, RMQ chaining, GPU offload) without altering the pipeline boundaries. This keeps algorithmic changes contained and testable.
