Expand description
§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 viawgpu(requires a compatible adapter).wasm: WebAssembly bindings exposing the index to JavaScript/TypeScript.
§Quick Start
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:
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);Re-exports§
pub use alphabet::decode_char;pub use alphabet::encode_byte;pub use alphabet::encode_char;pub use alphabet::Alphabet;pub use alphabet::AlphabetFns;pub use alphabet::DnaSequence;pub use alphabet::ExactDna;pub use alphabet::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;pub use fm_index::FmIndexConfig;pub use occ::OccEncoding;