haystackfm 0.4.0

GPU-accelerated FM-index construction for DNA sequences via WebGPU
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129

# Changelog

All notable changes to this project are documented in this file.

The format is based on [Keep a Changelog](https://keepachangelog.com/en/1.1.0/),
and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0.html).
Before 1.0, a breaking change bumps the **minor** version.

## [Unreleased]

## [0.4.0] - 2026-07-28

Breaking behavior change. The public API is unchanged — `cargo semver-checks` reports no
semver update required — but `find_mems` returns materially different results, so this takes
a minor bump under the pre-1.0 policy above rather than the patch bump an API-only check
would allow.

### Fixed
- **Breaking.** `BidirFmIndex::find_mems` now enumerates MEMs in the MUMmer / BWA sense:
  a query interval is reported when **at least one** of its occurrences is maximal in both
  directions *at that occurrence*. It previously required **every** occurrence to be
  maximal, so a single extendable occurrence in any one reference deleted the interval.
  Both the right-maximality test (the forward loop stopped only when the occurrence set went
  empty, discarding occurrences that dropped out mid-extension) and the left-maximality test
  (rejecting the interval if *any* occurrence was left-extendable) were affected.

  Consequences of the old behavior: at most one interval per query start position, and a
  result set that collapsed onto `find_smems`, making MEM-vs-SMEM comparisons through this
  API a guaranteed null result. In a database of near-identical references, per-reference
  match recovery was systematically sparse.

  For `query = ACGTACGTAC` against `ACGTACGTAC` and `ACGTACT` with `min_len = 2`, the result
  goes from `{(0,10)}` to `{(0,2), (0,6), (0,10), (4,10), (8,10)}`.

  `find_smems` is unaffected and unchanged: the containment-maximal MEMs under the new
  definition are exactly the SMEMs it already returned.

### Changed
- **Breaking.** `Mem::match_count` and `Mem::positions` from `find_mems` now cover only the
  maximal occurrences of a match, not every occurrence of the matched substring.
- `find_mems` output size is now bounded by O(|query|²) rather than |query|; `min_len` is the
  only guard. Expect `benches/mem_bench.rs` and `benches/mem_positions_bench.rs` timings to
  move accordingly.

### Known issues
- `find_mems_gpu` still runs the previous whole-set algorithm and is **not** equivalent to
  `find_mems`. The `shaders/mem_find.wgsl` MODE_MEM port is tracked in `KNOWN-ISSUES.md`.

## [0.3.0] - 2026-07-24

Breaking release: the index now retains the indexed text and can serve the bases of any
sequence, so callers no longer need to keep their own copy of every reference.

### Added
- `FmIndex::sequence(SeqId)` / `BidirFmIndex::sequence(SeqId)` — the bases of one indexed
  sequence as a borrowed slice, in O(1), with the trailing sentinel excluded. Returns
  alphabet codes (`A = 1`, `C = 2`, …), not ASCII; use `decode_char` to render them.
- `FmIndex::sequence_by_header(&str)` / `BidirFmIndex::sequence_by_header(&str)` — the same
  by header, equivalent to `seq_id(h).and_then(|id| self.sequence(id))`.
- `encode_byte`, `encode_char` and `decode_char` re-exported at the crate root, so callers
  can move queries into (and results out of) the alphabet's code space without reaching
  into the `alphabet` module.

### Changed
- **Breaking.** The serialized layout gains a `text` field, so indexes written by 0.2.0 and
  earlier are rejected by `from_bytes` and must be rebuilt.
- The concatenated text is no longer dropped after BWT construction. This costs ~n bytes of
  resident and serialized size and forgoes a build-time peak-memory reduction, in exchange
  for random-access substrings. An FM-index can otherwise only recover text by LF-walking
  backwards one symbol at a time — far too slow for a caller rescoring a read against a
  candidate diagonal, which is the case this exists to serve.
- Only the forward half of a `BidirFmIndex` retains text. The reverse half's copy is a
  redundant reversal that is never served, so it is released at build time, keeping the
  overhead at ~n rather than ~2n.

## [0.2.0] - 2026-07-24

Breaking release: match locations are now reported by integer sequence id instead of by
FASTA header string.

### Changed
- **Breaking.** Queries report match locations as `(SeqId, offset)` rather than
  `(String, offset)`, so no header string is allocated per occurrence — the cost was per
  occurrence rather than per seed, and scaled with seed multiplicity. Affects
  `FmIndex::locate`, `FmIndex::locate_gpu`, `FmIndex::map_position`,
  `BidirFmIndex::locate_interval`, `Mem::positions` and `MemHit::positions`, and the WASM
  `locate`. Callers that need labels resolve ids through `seq_header()`, or build an
  `id -> label` table once from `seq_headers()` and index it by `SeqId::index()`.
- **Breaking.** Sequence headers must now be unique; a collision fails the build with
  `FmIndexError::DuplicateHeader`. This is what makes `seq_id` an exact inverse of
  `seq_header`. Sequences supplied without a header are still auto-named `seq_{i}`, so this
  only fires on genuinely repeated names.

### Added
- `SeqId`, a stable 0-based identifier for an indexed reference. Assigned in build order and
  preserved across `to_bytes` / `from_bytes`.
- Sequence-id accessors on `FmIndex` and `BidirFmIndex` — `seq_headers()`, `seq_header(id)`
  and `seq_id(header)`. Both directions are O(1), backed by a header map built at
  construction and rebuilt on deserialization (it is derived, so it is not serialized).
- `FmIndexError::DuplicateHeader`.
- WASM bindings for the accessors: `seq_header`, `seq_id`, `seq_headers`.

The on-disk index format is unchanged — a `SeqId` is the position in the already-serialized
header list, and the header map is rebuilt on load rather than stored — so indexes written by
0.1.0 deserialize under 0.2.0, with one exception: an index built by 0.1.0 from *duplicate*
headers is now rejected by `from_bytes` with `DuplicateHeader`, since 0.1.0 permitted
collisions that 0.2.0 does not. Rebuild those indexes with unique headers.

## [0.1.0] - 2026-07-16

First release under the `haystackfm` name. The project was previously published as
`webgpu-fmidx` (versions 0.1.0–0.5.1); version numbering restarts at 0.1.0 under the new
name, and its earlier history is not carried over here.

### Added
- GPU-accelerated FM-index construction (suffix array, BWT, Occ table) via WebGPU compute
  shaders, alongside CPU construction.
- `count` / `locate` queries; bidirectional index with MEM / SMEM finding (CPU and GPU paths).
- Full 16-symbol IUPAC ambiguity alphabet with a pluggable `Alphabet` trait
  (`IupacDna` default, `ExactDna` for exact ACGT matching).
- WASM bindings for in-browser WebGPU use; index serialization (`to_bytes` / `from_bytes`).
- Community health files, CI (fmt / clippy / build / test on `--all-features`), and Dependabot.

### Changed
- Licensed under Apache-2.0.

[Unreleased]: https://github.com/sriram98v/haystackfm/commits/main
[0.4.0]: https://crates.io/crates/haystackfm/0.4.0
[0.1.0]: https://crates.io/crates/haystackfm/0.1.0