haystackfm 0.3.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

//! # haystackfm
//!
//! A GPU-accelerated FM-index library for DNA sequence alignment.
//!
//! This crate provides an FM-index data structure built on the Burrows-Wheeler
//! Transform (BWT) for efficient exact-match and approximate-match queries over
//! DNA sequences (A, C, G, T). Construction can run on the CPU or, when the
//! `gpu` feature is enabled, be accelerated via WebGPU compute shaders.
//!
//! ## Features
//!
//! - `cpu` *(default)*: CPU-only BWT, suffix-array, and Occ-table construction.
//! - `gpu`: GPU-accelerated construction via `wgpu` (requires a compatible adapter).
//! - `wasm`: WebAssembly bindings exposing the index to JavaScript/TypeScript.
//!
//! ## Quick Start
//!
//! ```rust
//! use haystackfm::{DnaSequence, FmIndex, FmIndexConfig};
//!
//! let seq = DnaSequence::from_str("ACGTACGT").unwrap();
//! let config = FmIndexConfig { sa_sample_rate: 4, ..Default::default() };
//! let index = FmIndex::build_cpu(&[seq], &config).unwrap();
//!
//! let pattern = [1u8, 2, 3, 4]; // A C G T (encoded)
//! assert_eq!(index.count(&pattern), 2);
//! ```
//!
//! ## Bidirectional FM-index and SMEM Finding
//!
//! For sequence alignment workloads, [`BidirFmIndex`] supports efficient
//! Super-Maximal Exact Match (SMEM) finding via the Lam et al. 2009 algorithm:
//!
//! ```rust
//! use haystackfm::{DnaSequence, BidirFmIndex, FmIndexConfig};
//!
//! let seq = DnaSequence::from_str("ACGTACGT").unwrap();
//! let config = FmIndexConfig { sa_sample_rate: 4, ..Default::default() };
//! let bidir = BidirFmIndex::build_cpu(&[seq], &config).unwrap();
//! let query = DnaSequence::from_str("ACGT").unwrap();
//! let smems = bidir.find_smems(query.as_slice(), 1, /*locate=*/true);
//! ```

pub mod alphabet;
pub mod bwt;
pub mod c_array;
pub mod error;
pub mod fm_index;
pub mod occ;
mod prefetch;
pub mod suffix_array;

#[cfg(feature = "gpu")]
pub mod gpu;

#[cfg(feature = "wasm")]
pub mod wasm;

pub use alphabet::{decode_char, encode_byte, encode_char};
pub use alphabet::{Alphabet, AlphabetFns, DnaSequence, ExactDna, IupacDna};
pub use error::FmIndexError;
pub use fm_index::bidir::BidirInterval;
pub use fm_index::bidir_index::BidirFmIndex;
pub use fm_index::seq_id::SeqId;
pub use fm_index::smem::Mem;
pub use fm_index::{FmIndex, FmIndexConfig};
#[cfg(feature = "gpu")]
pub use gpu::MemHit;
pub use occ::OccEncoding;