simd_minimizers/lib.rs
1//! A library to quickly compute (canonical) minimizers of DNA and text sequences.
2//!
3//! The main functions are:
4//! - [`minimizer_positions`]: compute the positions of all minimizers of a sequence.
5//! - [`canonical_minimizer_positions`]: compute the positions of all _canonical_ minimizers of a sequence.
6//!
7//! Adjacent equal positions are deduplicated, but since the canonical minimizer is _not_ _forward_, a position could appear more than once.
8//!
9//! The implementation uses SIMD by splitting each sequence into 8 chunks and processing those in parallel.
10//!
11//! When using super-k-mers, use the `_and_superkmer` variants to additionally return a vector containing the index of the first window the minimizer is minimal.
12//!
13//! The minimizer of a single window can be found using [`one_minimizer`] and [`one_canonical_minimizer`], but note that these functions are not nearly as efficient.
14//!
15//! The `scalar` versions are mostly for testing only, and basically always slower.
16//!
17//! ## Minimizers
18//!
19//! The code is explained in detail in our [paper](https://doi.org/10.4230/LIPIcs.SEA.2025.20):
20//!
21//! > SimdMinimizers: Computing random minimizers, fast.
22//! > Ragnar Groot Koerkamp, Igor Martayan, SEA 2025
23//!
24//! Briefly, minimizers are defined using two parameters `k` and `w`.
25//! Given a sequence of characters, all k-mers (substrings of length `k`) are hashed,
26//! and for each _window_ of `w` consecutive k-mers (of length `l = w + k - 1` characters),
27//! (the position of) the smallest k-mer is sampled.
28//!
29//! Minimizers are found as follows:
30//! 1. Split the input to 8 chunks that are processed in parallel using SIMD.
31//! 2. Compute a 32-bit ntHash rolling hash of the k-mers.
32//! 3. Use the 'two stacks' sliding window minimum on the top 16 bits of each hash.
33//! 4. Break ties towards the leftmost position by storing the position in the bottom 16 bits.
34//! 5. Compute 8 consecutive minimizer positions, and dedup them.
35//! 6. Collect the deduplicated minimizer positions from all 8 chunks into a single vector.
36//!
37//! ## Canonical minimizers
38//!
39//! _Canonical_ minimizers have the property that the sampled k-mers of a DNA sequence are the same as those sampled from the _reverse complement_ sequence.
40//!
41//! This works as follows:
42//! 1. ntHash is modified to use the canonical version that computes the xor of the hash of the forward and reverse complement k-mer.
43//! 2. Compute the leftmost and rightmost minimal k-mer.
44//! 3. Compute the 'preferred' strand of the current window as the one with more `TG` characters. This requires `l=w+k-1` to be odd for proper tie-breaking.
45//! 4. Return either the leftmost or rightmost smallest k-mer, depending on the preferred strand.
46//!
47//! ## Syncmers
48//!
49//! _Syncmers_ are (in our notation) windows of length `l = w + k - 1` characters where the minimizer k-mer is a prefix or suffix.
50//! (Or, in classical notation, `k`-mers with the smallest `s`-mer as prefix or suffix.)
51//! These can be computed by using [`fn@syncmers`] or [`canonical_syncmers`] instead of [`minimizers`] or [`canonical_minimizers`].
52//! To obtain their values via [`Output::values_u64`], `l` (rather than `k`) has to be at most 32.
53//!
54//! Note that canonical syncmers are chosen as the minimum of the forward and reverse-complement k-mer representation.
55//!
56//! ## Input types
57//!
58//! This crate depends on [`packed_seq`] to handle generic types of input sequences.
59//! Most commonly, one should use [`packed_seq::PackedSeqVec`] for packed DNA sequences, but one can also simply wrap a sequence of `ACTGactg` characters in [`packed_seq::AsciiSeqVec`].
60//! Additionally, `simd_minimizers` works on general (ASCII) `&[u8]` text.
61//!
62//! The main function provided by [`packed_seq`] is [`packed_seq::Seq::iter_bp`], which splits the input into 8 chunks and iterates them in parallel using SIMD.
63//!
64//! When the input is ASCII-encoded DNA, either use the `AsciiSeq` and `AsciiSeqVec` types, or (usually preferred) first convert to `PackedSeqVec`.
65//!
66//! ## Hash function
67//!
68//! By default, the library uses the `ntHash` hash function, which maps each DNA base `ACTG` to a pseudo-random value using a table lookup.
69//! This hash function is specifically designed to be fast for hashing DNA sequences with input type [`packed_seq::PackedSeq`] and [`packed_seq::AsciiSeq`].
70//!
71//! For general ASCII sequences (`&[u8]`), `mulHash` is used instead, which instead multiplies each character value by a pseudo-random constant.
72//! The `mul_hash` module provides functions that _always_ use mulHash, also for DNA sequences.
73//!
74//! ## Performance
75//!
76//! This library depends on AVX2 or NEON SIMD instructions to achieve good performance.
77//! Make sure to compile with `-C target-cpu=native` to enable these instructions.
78//! See the [ensure_simd](https://github.com/ragnargrootkoerkamp/ensure_simd) crate for more details.
79//!
80//! All functions take a `out_vec: &mut Vec<u32>` parameter to which positions are _appended_.
81//! For best performance, re-use the same `out_vec` between invocations, and [`Vec::clear`] it before or after each call.
82//!
83//! ## Examples
84//!
85//! #### Scalar `AsciiSeq`
86//!
87//! ```
88//! // Scalar ASCII version.
89//! use simd_minimizers::packed_seq;
90//! use packed_seq::{SeqVec, AsciiSeq};
91//!
92//! let seq = b"ACGTGCTCAGAGACTCAG";
93//! let ascii_seq = AsciiSeq(seq);
94//!
95//! let k = 5;
96//! let w = 7;
97//!
98//! let positions = simd_minimizers::minimizer_positions(ascii_seq, k, w);
99//! assert_eq!(positions, vec![4, 5, 8, 13]);
100//! ```
101//!
102//! #### SIMD `PackedSeq`
103//!
104//! ```
105//! // Packed SIMD version.
106//! use simd_minimizers::packed_seq;
107//! use packed_seq::{PackedSeqVec, SeqVec, Seq};
108//!
109//! let seq = b"ACGTGCTCAGAGACTCAGAGGA";
110//! let packed_seq = PackedSeqVec::from_ascii(seq);
111//!
112//! let k = 5;
113//! let w = 7;
114//!
115//! // Unfortunately, `PackedSeqVec` can not `Deref` into a `PackedSeq`, so `as_slice` is needed.
116//! // Since we also need the values, this uses the Builder API.
117//! let mut fwd_pos = vec![];
118//! let fwd_vals: Vec<_> = simd_minimizers::canonical_minimizers(k, w).run(packed_seq.as_slice(), &mut fwd_pos).values_u64().collect();
119//! assert_eq!(fwd_pos, vec![0, 7, 9, 15]);
120//! assert_eq!(fwd_vals, vec![
121//! // T G C A C, CACGT is rc of ACGTG at pos 0
122//! 0b10_11_01_00_01,
123//! // G A G A C, CAGAG is at pos 7
124//! 0b11_00_11_00_01,
125//! // C A G A G, GAGAC is at pos 9
126//! 0b01_00_11_00_11,
127//! // G A G A C, CAGAG is at pos 15
128//! 0b11_00_11_00_01
129//! ]);
130//!
131//! // Check that reverse complement sequence has minimizers at 'reverse' positions.
132//! let rc_packed_seq = packed_seq.as_slice().to_revcomp();
133//! let mut rc_pos = Vec::new();
134//! let mut rc_vals: Vec<_> = simd_minimizers::canonical_minimizers(k, w).run(rc_packed_seq.as_slice(), &mut rc_pos).values_u64().collect();
135//! assert_eq!(rc_pos, vec![2, 8, 10, 17]);
136//! for (fwd, &rc) in std::iter::zip(fwd_pos, rc_pos.iter().rev()) {
137//! assert_eq!(fwd as usize, seq.len() - k - rc as usize);
138//! }
139//! rc_vals.reverse();
140//! assert_eq!(rc_vals, fwd_vals);
141//! ```
142//!
143//! #### Seeded hasher
144//!
145//! ```
146//! // Packed SIMD version with seeded hashes.
147//! use simd_minimizers::{packed_seq, seq_hash};
148//! use packed_seq::{PackedSeqVec, SeqVec};
149//!
150//! let seq = b"ACGTGCTCAGAGACTCAG";
151//! let packed_seq = PackedSeqVec::from_ascii(seq);
152//!
153//! let k = 5;
154//! let w = 7;
155//! let seed = 101010;
156//! // Canonical by default. Use `NtHasher<false>` for forward-only.
157//! let hasher = <seq_hash::NtHasher>::new_with_seed(k, seed);
158//!
159//! let fwd_pos = simd_minimizers::canonical_minimizers(k, w).hasher(&hasher).run_once(packed_seq.as_slice());
160//! ```
161
162#![allow(clippy::missing_transmute_annotations)]
163
164/// Re-export of the `seq-hash` crate.
165pub use seq_hash;
166/// Re-export of the `packed-seq` crate.
167pub use seq_hash::packed_seq;
168
169mod canonical;
170pub mod collect;
171mod minimizers;
172mod sliding_min;
173pub mod syncmers;
174mod intrinsics {
175 mod dedup;
176 pub use dedup::{append_filtered_vals, append_unique_vals, append_unique_vals_2};
177}
178
179#[cfg(test)]
180mod test;
181
182/// Re-exported internals. Used for benchmarking, and not part of the semver-compatible stable API.
183pub mod private {
184 pub mod canonical {
185 pub use crate::canonical::*;
186 }
187 pub mod minimizers {
188 pub use crate::minimizers::*;
189 }
190 pub mod sliding_min {
191 pub use crate::sliding_min::*;
192 }
193 pub use seq_hash::packed_seq::u32x8 as S;
194}
195
196use collect::CollectAndDedup;
197use collect::collect_and_dedup_into_scalar;
198use collect::collect_and_dedup_with_index_into_scalar;
199use minimizers::canonical_minimizers_skip_ambiguous_windows;
200use packed_seq::PackedNSeq;
201use packed_seq::PackedSeq;
202
203use minimizers::{
204 canonical_minimizers_seq_scalar, canonical_minimizers_seq_simd, minimizers_seq_scalar,
205 minimizers_seq_simd,
206};
207use packed_seq::Seq;
208use packed_seq::u32x8 as S;
209use seq_hash::KmerHasher;
210
211pub use minimizers::one_minimizer;
212use seq_hash::NtHasher;
213pub use sliding_min::Cache;
214use syncmers::CollectSyncmers;
215use syncmers::collect_syncmers_scalar;
216
217thread_local! {
218 static CACHE: std::cell::RefCell<(Cache, Vec<S>, Vec<S>)> = std::cell::RefCell::new(Default::default());
219}
220
221/// `CANONICAL`: true for canonical minimizers.
222/// `H`: the kmer hasher to use.
223/// `SkPos`: type of super-k-mer position storage. Use `()` to disable super-k-mers.
224/// `SYNCMER`: 0 for minimizers, 1 for closed syncmers, 2 for open syncmers.
225pub struct Builder<'h, const CANONICAL: bool, H: KmerHasher, SkPos, const SYNCMER: u8> {
226 k: usize,
227 w: usize,
228 hasher: Option<&'h H>,
229 sk_pos: SkPos,
230}
231
232pub struct Output<'o, const CANONICAL: bool, S> {
233 /// k for minimizers, k+w-1 for syncmers
234 len: usize,
235 seq: S,
236 min_pos: &'o Vec<u32>,
237}
238
239#[must_use]
240pub const fn minimizers(k: usize, w: usize) -> Builder<'static, false, NtHasher<false>, (), 0> {
241 Builder {
242 k,
243 w,
244 hasher: None,
245 sk_pos: (),
246 }
247}
248
249#[must_use]
250pub const fn canonical_minimizers(
251 k: usize,
252 w: usize,
253) -> Builder<'static, true, NtHasher<true>, (), 0> {
254 Builder {
255 k,
256 w,
257 hasher: None,
258 sk_pos: (),
259 }
260}
261
262/// Return positions/values of *closed* syncmers of length `k+w-1`.
263///
264/// These are windows with the minimizer at the start or end of the window.
265///
266/// `k` here corresponds to `s` in original syncmer notation: the minimizer length.
267/// `k+w-1` corresponds to `k` in original syncmer notation: the length of the extracted string.
268#[must_use]
269pub const fn closed_syncmers(
270 k: usize,
271 w: usize,
272) -> Builder<'static, false, NtHasher<false>, (), 1> {
273 Builder {
274 k,
275 w,
276 hasher: None,
277 sk_pos: (),
278 }
279}
280
281#[must_use]
282pub const fn canonical_closed_syncmers(
283 k: usize,
284 w: usize,
285) -> Builder<'static, true, NtHasher<true>, (), 1> {
286 Builder {
287 k,
288 w,
289 hasher: None,
290 sk_pos: (),
291 }
292}
293
294/// Return positions/values of *open* syncmers of length `k+w-1`.
295///
296/// These are windows with the minimizer in the middle of the window. This requires `w` to be odd.
297///
298/// `k` here corresponds to `s` in original syncmer notation: the minimizer length.
299/// `k+w-1` corresponds to `k` in original syncmer notation: the length of the extracted string.
300#[must_use]
301pub const fn open_syncmers(k: usize, w: usize) -> Builder<'static, false, NtHasher<false>, (), 2> {
302 Builder {
303 k,
304 w,
305 hasher: None,
306 sk_pos: (),
307 }
308}
309
310#[must_use]
311pub const fn canonical_open_syncmers(
312 k: usize,
313 w: usize,
314) -> Builder<'static, true, NtHasher<true>, (), 2> {
315 Builder {
316 k,
317 w,
318 hasher: None,
319 sk_pos: (),
320 }
321}
322
323impl<const CANONICAL: bool, const SYNCMERS: u8>
324 Builder<'static, CANONICAL, NtHasher<CANONICAL>, (), SYNCMERS>
325{
326 #[must_use]
327 pub const fn hasher<'h, H2: KmerHasher>(
328 &self,
329 hasher: &'h H2,
330 ) -> Builder<'h, CANONICAL, H2, (), SYNCMERS> {
331 Builder {
332 k: self.k,
333 w: self.w,
334 sk_pos: (),
335 hasher: Some(hasher),
336 }
337 }
338}
339impl<'h, const CANONICAL: bool, H: KmerHasher> Builder<'h, CANONICAL, H, (), 0> {
340 #[must_use]
341 pub const fn super_kmers<'o2>(
342 &self,
343 sk_pos: &'o2 mut Vec<u32>,
344 ) -> Builder<'h, CANONICAL, H, &'o2 mut Vec<u32>, 0> {
345 Builder {
346 k: self.k,
347 w: self.w,
348 hasher: self.hasher,
349 sk_pos,
350 }
351 }
352}
353
354/// Without-superkmer version
355impl<'h, const CANONICAL: bool, H: KmerHasher, const SYNCMERS: u8>
356 Builder<'h, CANONICAL, H, (), SYNCMERS>
357{
358 pub fn run_scalar_once<'s, SEQ: Seq<'s>>(&self, seq: SEQ) -> Vec<u32> {
359 let mut min_pos = vec![];
360 self.run_impl::<false, _>(seq, &mut min_pos);
361 min_pos
362 }
363
364 pub fn run_once<'s, SEQ: Seq<'s>>(&self, seq: SEQ) -> Vec<u32> {
365 let mut min_pos = vec![];
366 self.run_impl::<true, _>(seq, &mut min_pos);
367 min_pos
368 }
369
370 pub fn run_scalar<'s, 'o, SEQ: Seq<'s>>(
371 &self,
372 seq: SEQ,
373 min_pos: &'o mut Vec<u32>,
374 ) -> Output<'o, CANONICAL, SEQ> {
375 self.run_impl::<false, _>(seq, min_pos)
376 }
377
378 pub fn run<'s, 'o, SEQ: Seq<'s>>(
379 &self,
380 seq: SEQ,
381 min_pos: &'o mut Vec<u32>,
382 ) -> Output<'o, CANONICAL, SEQ> {
383 self.run_impl::<true, _>(seq, min_pos)
384 }
385
386 fn run_impl<'s, 'o, const SIMD: bool, SEQ: Seq<'s>>(
387 &self,
388 seq: SEQ,
389 min_pos: &'o mut Vec<u32>,
390 ) -> Output<'o, CANONICAL, SEQ> {
391 let default_hasher = self.hasher.is_none().then(|| H::new(self.k));
392 let hasher = self
393 .hasher
394 .unwrap_or_else(|| default_hasher.as_ref().unwrap());
395
396 CACHE.with_borrow_mut(|cache| match (SIMD, CANONICAL, SYNCMERS) {
397 (false, false, 0) => collect_and_dedup_into_scalar(
398 minimizers_seq_scalar(seq, hasher, self.w, &mut cache.0),
399 min_pos,
400 ),
401 (false, false, 1) => collect_syncmers_scalar::<false>(
402 self.w,
403 minimizers_seq_scalar(seq, hasher, self.w, &mut cache.0),
404 min_pos,
405 ),
406 (false, false, 2) => collect_syncmers_scalar::<true>(
407 self.w,
408 minimizers_seq_scalar(seq, hasher, self.w, &mut cache.0),
409 min_pos,
410 ),
411 (false, true, 0) => collect_and_dedup_into_scalar(
412 canonical_minimizers_seq_scalar(seq, hasher, self.w, &mut cache.0),
413 min_pos,
414 ),
415 (false, true, 1) => collect_syncmers_scalar::<false>(
416 self.w,
417 canonical_minimizers_seq_scalar(seq, hasher, self.w, &mut cache.0),
418 min_pos,
419 ),
420 (false, true, 2) => collect_syncmers_scalar::<true>(
421 self.w,
422 canonical_minimizers_seq_scalar(seq, hasher, self.w, &mut cache.0),
423 min_pos,
424 ),
425 (true, false, 0) => minimizers_seq_simd(seq, hasher, self.w, &mut cache.0)
426 .collect_and_dedup_into::<false>(min_pos),
427 (true, false, 1) => minimizers_seq_simd(seq, hasher, self.w, &mut cache.0)
428 .collect_syncmers_into::<false>(self.w, min_pos),
429 (true, false, 2) => minimizers_seq_simd(seq, hasher, self.w, &mut cache.0)
430 .collect_syncmers_into::<true>(self.w, min_pos),
431 (true, true, 0) => canonical_minimizers_seq_simd(seq, hasher, self.w, &mut cache.0)
432 .collect_and_dedup_into::<false>(min_pos),
433 (true, true, 1) => canonical_minimizers_seq_simd(seq, hasher, self.w, &mut cache.0)
434 .collect_syncmers_into::<false>(self.w, min_pos),
435 (true, true, 2) => canonical_minimizers_seq_simd(seq, hasher, self.w, &mut cache.0)
436 .collect_syncmers_into::<true>(self.w, min_pos),
437 _ => unreachable!("SYNCMERS generic must be 0 (no syncmers), 1 (closed syncmers), or 2 (open syncmers)."),
438 });
439 Output {
440 len: if SYNCMERS != 0 {
441 self.k + self.w - 1
442 } else {
443 self.k
444 },
445 seq,
446 min_pos,
447 }
448 }
449}
450
451impl<'h, H: KmerHasher, const SYNCMERS: u8> Builder<'h, true, H, (), SYNCMERS> {
452 pub fn run_skip_ambiguous_windows_once<'s>(&self, nseq: PackedNSeq<'s>) -> Vec<u32> {
453 let mut min_pos = vec![];
454 self.run_skip_ambiguous_windows(nseq, &mut min_pos);
455 min_pos
456 }
457 pub fn run_skip_ambiguous_windows<'s, 'o>(
458 &self,
459 nseq: PackedNSeq<'s>,
460 min_pos: &'o mut Vec<u32>,
461 ) -> Output<'o, true, PackedSeq<'s>> {
462 CACHE
463 .with_borrow_mut(|cache| self.run_skip_ambiguous_windows_with_buf(nseq, min_pos, cache))
464 }
465 pub fn run_skip_ambiguous_windows_with_buf<'s, 'o>(
466 &self,
467 nseq: PackedNSeq<'s>,
468 min_pos: &'o mut Vec<u32>,
469 cache: &mut (Cache, Vec<S>, Vec<S>),
470 ) -> Output<'o, true, PackedSeq<'s>> {
471 let default_hasher = self.hasher.is_none().then(|| H::new(self.k));
472 let hasher = self
473 .hasher
474 .unwrap_or_else(|| default_hasher.as_ref().unwrap());
475 match SYNCMERS {
476 0 => canonical_minimizers_skip_ambiguous_windows(nseq, hasher, self.w, cache)
477 .collect_and_dedup_into::<true>(min_pos),
478 1 => canonical_minimizers_skip_ambiguous_windows(nseq, hasher, self.w, cache)
479 .collect_syncmers_into::<false>(self.w, min_pos),
480 2 => canonical_minimizers_skip_ambiguous_windows(nseq, hasher, self.w, cache)
481 .collect_syncmers_into::<true>(self.w, min_pos),
482 _ => panic!(
483 "SYNCMERS generic must be 0 (no syncmers), 1 (closed syncmers), or 2 (open syncmers)."
484 ),
485 }
486 Output {
487 len: if SYNCMERS != 0 {
488 self.k + self.w - 1
489 } else {
490 self.k
491 },
492 seq: nseq.seq,
493 min_pos,
494 }
495 }
496}
497
498/// With-superkmer version
499///
500/// (does not work in combination with syncmers)
501impl<'h, 'o2, const CANONICAL: bool, H: KmerHasher>
502 Builder<'h, CANONICAL, H, &'o2 mut Vec<u32>, 0>
503{
504 pub fn run_scalar_once<'s, SEQ: Seq<'s>>(self, seq: SEQ) -> Vec<u32> {
505 let mut min_pos = vec![];
506 self.run_scalar(seq, &mut min_pos);
507 min_pos
508 }
509
510 pub fn run_scalar<'s, 'o, SEQ: Seq<'s>>(
511 self,
512 seq: SEQ,
513 min_pos: &'o mut Vec<u32>,
514 ) -> Output<'o, CANONICAL, SEQ> {
515 let default_hasher = self.hasher.is_none().then(|| H::new(self.k));
516 let hasher = self
517 .hasher
518 .unwrap_or_else(|| default_hasher.as_ref().unwrap());
519
520 CACHE.with_borrow_mut(|cache| match CANONICAL {
521 false => collect_and_dedup_with_index_into_scalar(
522 minimizers_seq_scalar(seq, hasher, self.w, &mut cache.0),
523 min_pos,
524 self.sk_pos,
525 ),
526 true => collect_and_dedup_with_index_into_scalar(
527 canonical_minimizers_seq_scalar(seq, hasher, self.w, &mut cache.0),
528 min_pos,
529 self.sk_pos,
530 ),
531 });
532 Output {
533 len: self.k,
534 seq,
535 min_pos,
536 }
537 }
538
539 pub fn run_once<'s, SEQ: Seq<'s>>(self, seq: SEQ) -> Vec<u32> {
540 let mut min_pos = vec![];
541 self.run(seq, &mut min_pos);
542 min_pos
543 }
544
545 pub fn run<'s, 'o, SEQ: Seq<'s>>(
546 self,
547 seq: SEQ,
548 min_pos: &'o mut Vec<u32>,
549 ) -> Output<'o, CANONICAL, SEQ> {
550 CACHE.with_borrow_mut(|cache| self.run_with_buf(seq, min_pos, &mut cache.0))
551 }
552
553 #[inline(always)]
554 fn run_with_buf<'s, 'o, SEQ: Seq<'s>>(
555 self,
556 seq: SEQ,
557 min_pos: &'o mut Vec<u32>,
558 cache: &mut Cache,
559 ) -> Output<'o, CANONICAL, SEQ> {
560 let default_hasher = self.hasher.is_none().then(|| H::new(self.k));
561 let hasher = self
562 .hasher
563 .unwrap_or_else(|| default_hasher.as_ref().unwrap());
564
565 match CANONICAL {
566 false => minimizers_seq_simd(seq, hasher, self.w, cache)
567 .collect_and_dedup_with_index_into(min_pos, self.sk_pos),
568 true => canonical_minimizers_seq_simd(seq, hasher, self.w, cache)
569 .collect_and_dedup_with_index_into(min_pos, self.sk_pos),
570 };
571 Output {
572 len: self.k,
573 seq,
574 min_pos,
575 }
576 }
577}
578
579impl<'s, 'o, const CANONICAL: bool, SEQ: Seq<'s>> Output<'o, CANONICAL, SEQ> {
580 /// Iterator over (canonical) u64 kmer-values associated with all minimizer positions.
581 ///
582 /// For syncmers, this returns `l=w+k-1`-mers.
583 #[must_use]
584 pub fn values_u64(&self) -> impl ExactSizeIterator<Item = u64> {
585 self.pos_and_values_u64().map(|(_pos, val)| val)
586 }
587 /// Iterator over (canonical) u128 kmer-values associated with all minimizer positions.
588 ///
589 /// For syncmers, this returns `l=w+k-1`-mers.
590 #[must_use]
591 pub fn values_u128(&self) -> impl ExactSizeIterator<Item = u128> {
592 self.pos_and_values_u128().map(|(_pos, val)| val)
593 }
594 /// Iterator over positions and (canonical) u64 kmer-values associated with all minimizer positions.
595 ///
596 /// For syncmers, this returns `l=w+k-1`-mer values.
597 #[must_use]
598 pub fn pos_and_values_u64(&self) -> impl ExactSizeIterator<Item = (u32, u64)> {
599 self.min_pos.iter().map(
600 #[inline(always)]
601 move |&pos| {
602 let val = if CANONICAL {
603 let a = self.seq.read_kmer(self.len, pos as usize);
604 let b = self.seq.read_revcomp_kmer(self.len, pos as usize);
605 core::cmp::min(a, b)
606 } else {
607 self.seq.read_kmer(self.len, pos as usize)
608 };
609 (pos, val)
610 },
611 )
612 }
613 /// Iterator over positions and (canonical) u128 kmer-values associated with all minimizer positions.
614 #[must_use]
615 pub fn pos_and_values_u128(&self) -> impl ExactSizeIterator<Item = (u32, u128)> {
616 self.min_pos.iter().map(
617 #[inline(always)]
618 move |&pos| {
619 let val = if CANONICAL {
620 let a = self.seq.read_kmer_u128(self.len, pos as usize);
621 let b = self.seq.read_revcomp_kmer_u128(self.len, pos as usize);
622 core::cmp::min(a, b)
623 } else {
624 self.seq.read_kmer_u128(self.len, pos as usize)
625 };
626 (pos, val)
627 },
628 )
629 }
630}
631
632/// Positions of all minimizers in the sequence.
633///
634/// See [`minimizers`], [`canonical_minimizers`], and [`Builder`] for more
635/// configurations supporting a custom hasher, super-kmer positions, and
636/// returning kmer-values.
637///
638/// Positions are appended to a reusable `min_pos` vector to avoid allocations.
639pub fn minimizer_positions<'s>(seq: impl Seq<'s>, k: usize, w: usize) -> Vec<u32> {
640 minimizers(k, w).run_once(seq)
641}
642
643/// Positions of all canonical minimizers in the sequence.
644///
645/// See [`minimizers`], [`canonical_minimizers`], and [`Builder`] for more
646/// configurations supporting a custom hasher, super-kmer positions, and
647/// returning kmer-values.
648///
649/// `l=w+k-1` must be odd to determine the strand of each window.
650///
651/// Positions are appended to a reusable `min_pos` vector to avoid allocations.
652pub fn canonical_minimizer_positions<'s>(seq: impl Seq<'s>, k: usize, w: usize) -> Vec<u32> {
653 canonical_minimizers(k, w).run_once(seq)
654}