strobemers-rs

Rust implementation of strobemer generation (MinStrobes, RandStrobes).
Streaming iterators produce 64-bit strobemer hashes over DNA/RNA sequences.

Background

• The original strobemer concept and reference implementation live at ksahlin/strobemers.
• This crate’s design was guided by the Go port found at shenwei356/strobemers, but the code here is a complete Rust‐native rewrite (zero unsafe).
• Strobe selection is verified against that Go port value-by-value in tests/go_conformance.rs. Hash values differ between the two, because they use different ntHash libraries; the tests therefore drive both with the same injected k-mer hasher.
• One deliberate deviation: when w_min > (n-1) * k, the search window for the last few positions starts past the end of the sequence. The Go code silently reuses the previous strobe there; this crate ends iteration instead, so every reported strobe position is a real k-mer.

Overview

Strobemers are an alternative to contiguous k-mer hashing designed to improve sensitivity in long-read alignment and genome comparison.
This crate provides:

• MinStrobes (order 2/3)
  Choose subsequent strobes by selecting the minimum hash within a sliding window.

• RandStrobes (order 2/3)
  Choose subsequent strobes by a pseudo-random but reproducible rule derived from hash values.

Sequences must consist of A, C, G, T/U only. The default hasher skips k-mer windows containing any other base, which would break the mapping from hash index to sequence position, so such sequences are rejected with StrobeError::IncompleteHashValues (as in the Go reference).

Installation

Add to your Cargo.toml via command line.

cargo add strobemers-rs

Quick Start

use strobemers_rs::{MinStrobes, RandStrobes};

fn main() -> anyhow::Result<()> {
    // Example DNA sequence
    let seq = b"ACGATCTGGTACCTAG";
    // k-mer length
    let k = 3;
    // window offsets
    let w_min = 3;
    let w_max = 5;

    // MinStrobes order-2
    // Produces one 64-bit hash per position, selecting the minimum-hash strobe in [i+w_min .. i+w_max].
    let mut min2 = MinStrobes::new(seq, 2, k, w_min, w_max)?;
    while let Some(h) = min2.next() {
        println!("MinStrobes(order=2) hash: {}", h);
    }

    // MinStrobes order-3
    // Two-level selection: pick m2 in [i+w_min .. i+w_max], then m3 in
    // [i+w_max+w_min .. i+2*w_max]. Both windows are anchored on the position of
    // m1, not on where m2 happened to land.
    let mut min3 = MinStrobes::new(seq, 3, k, w_min, w_max)?;
    for (i, h) in min3.take(5).enumerate() {
        let [m1, m2, m3_pos] = min3.indexes();
        println!("MinStrobes(order=3)[{}] m1={} m2={} m3={} -> hash={}",
            i, m1, m2, m3_pos, h);
    }

    // RandStrobes order-2
    // Similar to MinStrobes, but the second strobe is chosen by a pseudo-random rule:
    let mut rand2 = RandStrobes::new(seq, 2, k, w_min, w_max)?;
    while let Some(h) = rand2.next() {
        println!("RandStrobes(order=2) hash: {}", h);
    }

    // RandStrobes order-3
    let mut rand3 = RandStrobes::new(seq, 3, k, w_min, w_max)?;
    for (i, h) in rand3.take(5).enumerate() {
        let [m1, m2, m3_pos] = rand3.indexes();
        println!("RandStrobes(order=3)[{}] m1={} m2={} m3={} -> hash={}",
            i, m1, m2, m3_pos, h);
    }

    Ok(())
}

Performance notes

Both iterators precompute one 64-bit hash per k-mer up front, so scratch memory is 8 bytes per base. MinStrobes also needs the minimum of a sliding window: it precomputes that as a table — another 16 bytes per base — while the table stays cache-resident, and computes it online for longer sequences, keeping only O(w_max) entries. Scratch for a 20 Mbp sequence is therefore 152 MiB rather than 457 MiB, and per-base throughput stops degrading as the sequence grows.

Measured with cargo bench on a Xeon Platinum 8480+ over 1 Mbp of random DNA, k = 31, w_min = 20, w_max = 50:

RandStrobes picks its next strobe by minimising (h1 + h2) & prime over the window. With the default prime that reduces to a branchless 64-bit min, which vectorises into vpminuq when the target has AVX-512 — building with RUSTFLAGS="-C target-cpu=native" (or -C target-cpu=x86-64-v4) is worth about 1.4x there. MinStrobes is unaffected, being bound by memory traffic rather than by that loop.

Both iterators are ExactSizeIterator, so collect() allocates exactly once.

Using a Custom Hash Function

By default, strobemers-rs uses nthash-rs for k-mer hashing. However, you can inject your own hash function by implementing the KmerHasher trait and passing it via the with_hasher method. See the example for more details.

License

This project is MIT‑licensed (see LICENSE).