tandemox/lib.rs
1//! Tandem repeat detection — DB-free, pure-Rust, no external tools.
2//!
3//! Finds approximate tandem repeats (period 1..=500, tolerating both mismatches
4//! and indels) in a DNA sequence and returns them as [`TandemRepeat`] records.
5//!
6//! ```
7//! let seq = b"GACTTCAGGATCCGATACGTTAGCACTGATGCATGCATGCATGCATGCATGCATGCATGCATGCATGCCATGACTGACAGT";
8//! let repeats = tandemox::detect(seq);
9//! assert_eq!(repeats[0].period, 4);
10//! ```
11//!
12//! Tandem Repeats Finder (TRF) is license-restricted, so no code is derived from
13//! it. This is an independent implementation built from the published
14//! literature — the wraparound alignment of Fischetti, Landau, Schmidt and
15//! Sellers (CPM 1992) — and *validated against* TRF's output for concordance.
16//!
17//! ## Algorithm
18//!
19//! Detection runs in two stages: a cheap linear scan proposes candidates, and a
20//! dynamic-programming alignment adjudicates them.
21//!
22//! 1. **Seeding** — for each period `p`, walk the "period-`p` diagonal",
23//! comparing `seq[i]` with `seq[i - p]`, scoring `+1` / `-3` and pulling out
24//! maximal-scoring runs (Kadane). This is only a *detector*: it is
25//! deliberately permissive, because an indel shifts the diagonal permanently
26//! and so a gapped repeat only ever shows up here as a partial run. Its job
27//! is to answer "is there any period-`p` structure near here", not to decide
28//! what the repeat is or where it ends.
29//!
30//! 2. **Refinement** — each seed's ungapped run votes for a consensus motif, and
31//! wraparound DP aligns a generous window around the seed against that motif
32//! repeated end-to-end, under TRF's `2 / -7 / -7` weights. The alignment
33//! supplies everything that gets reported: the true score, the
34//! match/mismatch/indel tallies, and the repeat's boundaries. Indels are
35//! absorbed here, which is what the seeding stage structurally cannot do.
36//!
37//! 3. **Gating** — a refined candidate must clear the significance floor
38//! (score >= 50, >= ~1.9 copies, >= 80% identity to the consensus), then
39//! greedy overlap dedup keeps one call per region so a repeat is reported at
40//! its fundamental period rather than once per harmonic.
41//!
42//! Scoring the *whole region* against the consensus — rather than just the
43//! `len - p` diagonal pairs — is what puts that score floor on TRF's scale: a
44//! perfect repeat of length `L` scores `2L`, matching TRF exactly.
45//!
46//! Seeding is linear per period and random sequence essentially never sustains a
47//! positive run, so the practical cost sits far below the `O(n · 500)` bound.
48//! The match-track scan advances a machine word at a time (SWAR), skipping runs
49//! of non-matching positions in bulk. Periods are independent, so [`detect`] is
50//! single-threaded and composable while [`detect_parallel`] spreads the same
51//! work across threads for a single large sequence, with identical output.
52
53mod wdp;
54
55// ---- tunables (TRF `2 7 7 80 10 50 500` defaults) ----------------------------
56
57/// Largest repeat period considered, matching TRF's `MaxPeriod` argument.
58const MAX_PERIOD: usize = 500;
59/// Shortest reportable repeat region.
60const MIN_REGION_LEN: usize = 10;
61/// TRF reports repeats down to roughly two copies.
62const MIN_COPIES: f64 = 1.9;
63/// Lower copies floor, allowed only for high-scoring long repeats (see
64/// [`passes_copies`]). TRF's own minimum is ~1.82 copies.
65const MIN_COPIES_STRONG: f64 = 1.8;
66/// Score a sub-[`MIN_COPIES`] repeat must reach to be kept. Set well above the
67/// significance floor so only long, unambiguous arrays qualify.
68const STRONG_LOWCOPY_SCORE: f32 = 150.0;
69/// Minimum identity between the repeat and its consensus (TRF's `PM = 80`).
70const MIN_IDENT: f64 = 0.80;
71/// TRF-default significance gate (`Minscore = 50`). Because refinement scores
72/// the full region against the consensus, this is directly comparable to the
73/// score in TRF's `.dat` output.
74const MIN_SCORE: f32 = 50.0;
75
76// ---- seeding tunables --------------------------------------------------------
77
78const SEED_MATCH: i64 = 1;
79/// Break-even identity for the seed track sits at 75%, just under [`MIN_IDENT`],
80/// so the detector stays slightly more permissive than the final gate.
81const SEED_MISMATCH: i64 = -3;
82/// Floor on a seed run's score. Low on purpose: seeds only have to notice a
83/// repeat, and gapped repeats present as short partial runs. Refinement is what
84/// rejects the noise.
85const SEED_MIN_SUM: i64 = 8;
86/// For long periods the floor scales up (`p / SEED_SUM_PERIOD_DIV`). A genuine
87/// long-period repeat still shows a long clean run somewhere, while this keeps
88/// random long-period seeds — whose refinement windows are the expensive ones —
89/// from ever being proposed.
90const SEED_SUM_PERIOD_DIV: i64 = 8;
91
92/// Refinement window margin either side of a seed, as a multiple of the period,
93/// letting WDP recover copies the ungapped seed run never reached.
94const REFINE_MARGIN_PERIODS: usize = 6;
95const REFINE_MARGIN_CONST: usize = 50;
96
97/// How many periods of a seed to poll when voting for its consensus motif.
98///
99/// Deliberately short, and anchored at a seed's edge rather than spanning it. A
100/// seed run is *not* indel-free: a deletion shifts `seq[i]` and `seq[i - p]` by
101/// the same amount, so the period-`p` diagonal only breaks for the ~`p`
102/// positions where one side has crossed the indel and the other has not, and
103/// then recovers — the Kadane run rides straight through. Voting across that
104/// span mixes two reading registers and yields a meaningless consensus, so the
105/// vote is kept inside a stretch too short to reach an indel. WDP is what spans
106/// the indels afterwards.
107const CONS_VOTE_PERIODS: usize = 3;
108
109/// Greedy dedup threshold: drop a candidate overlapping a kept one by more than
110/// this fraction of the shorter region.
111const MAX_OVERLAP_FRAC: f64 = 0.50;
112
113/// When a shorter-period candidate overlaps a kept longer-period one, the
114/// shorter (fundamental) period is preferred as long as its score is within this
115/// fraction of the kept one's.
116///
117/// A repeat carrying indels can always be re-described at a longer period that
118/// folds each indel into the motif — twelve copies of a 12-mer with one inserted
119/// base is also two copies of a 73-mer — and, paying no indel penalty, the
120/// longer period scores a little higher. That is not a better explanation, just
121/// a coarser one, so within this relative band the fundamental period wins. A
122/// genuinely different longer repeat scores far more than a few indel penalties
123/// better and stays outside the band, so it is still reported at its own period.
124const PERIOD_PREFER_TOL: f32 = 0.15;
125
126/// A single detected tandem repeat on one sequence.
127#[derive(Clone, Debug, PartialEq)]
128pub struct TandemRepeat {
129 /// 1-based inclusive left coordinate on the sequence.
130 pub start: usize,
131 /// 1-based inclusive right coordinate on the sequence.
132 pub end: usize,
133 /// Repeat period (motif length) in bp.
134 pub period: usize,
135 /// Fractional number of copies (`region_len / period`).
136 pub copies: f64,
137 /// Fractional identity to the consensus, in `0..=1`.
138 pub identity: f64,
139 /// TRF-comparable alignment score under `2 / -7 / -7` weights.
140 pub score: f32,
141 /// Consensus (motif) size in bp; equal to `period`.
142 pub consensus_size: usize,
143}
144
145/// A refined candidate region (0-based, inclusive).
146#[derive(Clone, Debug)]
147struct Cand {
148 start: usize,
149 end: usize,
150 period: usize,
151 ident: f64,
152 copies: f64,
153 score: f32,
154}
155
156impl Cand {
157 #[inline]
158 fn len(&self) -> usize {
159 self.end - self.start + 1
160 }
161}
162
163#[inline]
164pub(crate) fn is_acgt(b: u8) -> bool {
165 matches!(b, b'A' | b'C' | b'G' | b'T')
166}
167
168/// Case-insensitive base match. Anything non-ACGT (including `N`) never matches,
169/// so repeats never bridge ambiguous runs or assembly gaps.
170#[inline]
171pub(crate) fn base_match(a: u8, b: u8) -> bool {
172 let x = a.to_ascii_uppercase();
173 x == b.to_ascii_uppercase() && is_acgt(x)
174}
175
176/// Per-base code for the non-ACGT sentinel. Kept `>= 4` so it never equals an
177/// ACGT code (0..=3) — two ambiguous bases therefore never count as a match —
178/// while staying small enough that the `& 0xFC == 0` validity test below holds
179/// exactly for ACGT and fails for it.
180const NON_ACGT: u8 = 4;
181
182/// Encode a sequence to per-base codes: `A/C/G/T` (any case) → `0..=3`, anything
183/// else (including `N`) → [`NON_ACGT`].
184///
185/// Computed once per sequence so the seeding scan never re-folds case or
186/// re-tests ACGT per comparison, and so match tracks can be scanned a machine
187/// word at a time (see [`next_match`]).
188fn encode(seq: &[u8]) -> Vec<u8> {
189 seq.iter()
190 .map(|&b| match b & !0x20 {
191 // `& !0x20` upper-cases ASCII letters; only A/C/G/T fold onto these.
192 b'A' => 0,
193 b'C' => 1,
194 b'G' => 2,
195 b'T' => 3,
196 _ => NON_ACGT,
197 })
198 .collect()
199}
200
201// SWAR (SIMD-within-a-register) helpers for scanning a period's match track a
202// word at a time. Random DNA matches at ~1/4 of positions, so advancing one
203// base per non-match — as a scalar scan must — is where the old seeding spent
204// most of its time; these let it skip 8 positions per step.
205const SWAR_LOW: u64 = 0x0101010101010101;
206const SWAR_HIGH: u64 = 0x8080808080808080;
207/// `0xFC` in every byte — masks off the low two bits, so a byte ANDed with this
208/// is zero exactly when the original was an ACGT code (`0..=3`).
209const SWAR_VALID: u64 = 0xFCFC_FCFC_FCFC_FCFC;
210
211/// Classic "which bytes are zero" test: `0x80` in each byte position of `y` that
212/// holds zero, `0x00` elsewhere. Exact, no false marks.
213#[inline]
214fn zero_byte_mask(y: u64) -> u64 {
215 y.wrapping_sub(SWAR_LOW) & !y & SWAR_HIGH
216}
217
218/// Read `code[i..i + 8]` as a little-endian word, so byte 0 is `code[i]`.
219#[inline]
220fn load8(code: &[u8], i: usize) -> u64 {
221 let mut a = [0u8; 8];
222 a.copy_from_slice(&code[i..i + 8]);
223 u64::from_le_bytes(a)
224}
225
226/// An ungapped period-`p` run proposed by the seeding scan (0-based, inclusive).
227#[derive(Clone, Copy, Debug)]
228struct Seed {
229 /// Start of the *earlier* copy on the sequence.
230 left: usize,
231 /// End of the ungapped run on the diagonal (the later copy's last base).
232 right: usize,
233}
234
235/// Minimum seed run score for period `p`.
236#[inline]
237fn seed_threshold(p: usize) -> i64 {
238 SEED_MIN_SUM.max(p as i64 / SEED_SUM_PERIOD_DIV)
239}
240
241/// Copies/score gate. Accepts a repeat with at least [`MIN_COPIES`] copies, or a
242/// shorter one (down to [`MIN_COPIES_STRONG`]) only when it is long and scores
243/// well past the significance floor.
244///
245/// The relaxation exists because TRF reports genuine repeats down to ~1.82
246/// copies, and the strongest of those — a period-229 array scoring 744, say —
247/// are unmistakable. Dropping the copies floor outright, however, lets in a
248/// flood of weak ~1.8-copy microsatellites that TRF's probabilistic model
249/// rejects, so the relaxation is gated on a high score that only long,
250/// well-supported repeats reach.
251#[inline]
252fn passes_copies(copies: f64, score: f32) -> bool {
253 copies >= MIN_COPIES || (copies >= MIN_COPIES_STRONG && score >= STRONG_LOWCOPY_SCORE)
254}
255
256/// Smallest `t' >= t` (with `t' < m`) that is a period-`p` diagonal match — i.e.
257/// `code[t']` is ACGT and equals `code[p + t']` — or `m` if there is none.
258///
259/// While a full 8-code window fits on both sides of the diagonal it tests all
260/// eight at once: equal codes XOR to a zero byte, and ACGT codes clear under
261/// [`SWAR_VALID`], so the byte-zero tests intersect to exactly the matching
262/// valid positions. `trailing_zeros` then points at the lowest one.
263#[inline]
264fn next_match(code: &[u8], p: usize, mut t: usize, m: usize) -> usize {
265 let n = code.len();
266 while t < m {
267 if t + 8 <= m && p + t + 8 <= n {
268 let a = load8(code, t);
269 let b = load8(code, p + t);
270 let hits = zero_byte_mask(a ^ b) & zero_byte_mask(a & SWAR_VALID);
271 if hits != 0 {
272 return t + (hits.trailing_zeros() as usize / 8);
273 }
274 t += 8;
275 } else {
276 if code[t] < NON_ACGT && code[p + t] == code[t] {
277 return t;
278 }
279 t += 1;
280 }
281 }
282 m
283}
284
285/// Scan the period-`p` diagonal of the encoded sequence, emitting ungapped runs
286/// worth refining. Takes codes from [`encode`] rather than raw bases so the
287/// no-match stretches — the bulk of the work — can be skipped a word at a time.
288fn scan_period_seeds(code: &[u8], p: usize, out: &mut Vec<Seed>) {
289 let n = code.len();
290 if p == 0 || p >= n {
291 return;
292 }
293 let thresh = seed_threshold(p);
294 // Track index `t` maps to sequence position `p + t`, compared against
295 // `code[t]` — the copy one period earlier.
296 let m = n - p;
297 let mut t = next_match(code, p, 0, m);
298 while t < m {
299 // Kadane from the matching position: keep the arg-max end, close the run
300 // once the running sum goes negative. Runs are intentionally short and
301 // local — WDP re-derives the real extent later.
302 let mut sum: i64 = 0;
303 let mut best_sum: i64 = i64::MIN;
304 let mut best_end = t;
305 let mut k = t;
306 while k < m {
307 sum += if code[k] < NON_ACGT && code[p + k] == code[k] {
308 SEED_MATCH
309 } else {
310 SEED_MISMATCH
311 };
312 if sum > best_sum {
313 best_sum = sum;
314 best_end = k;
315 }
316 if sum < 0 {
317 break;
318 }
319 k += 1;
320 }
321
322 if best_sum >= thresh {
323 out.push(Seed {
324 left: t,
325 right: p + best_end,
326 });
327 }
328 t = next_match(code, p, best_end + 1, m);
329 }
330}
331
332/// Turn a seed into a scored candidate via wraparound DP, or reject it.
333///
334/// The consensus motif is voted from a short stretch at each end of the seed
335/// (see [`CONS_VOTE_PERIODS`]) and the two resulting alignments are compared;
336/// the higher-scoring one wins. Two anchors are cheap insurance: if one end of
337/// the seed happens to sit on a divergent copy, the other usually does not, and
338/// for a clean seed both converge on the same motif.
339fn refine(seq: &[u8], seed: Seed, p: usize) -> Option<Cand> {
340 let n = seq.len();
341 let vote_span = CONS_VOTE_PERIODS * p;
342
343 // Window is generous; WDP's local semantics trim it, and a mismatch costing
344 // -7 against a match's +2 stops extension through a spacer almost at once.
345 let margin = REFINE_MARGIN_PERIODS * p + REFINE_MARGIN_CONST;
346 let wstart = seed.left.saturating_sub(margin);
347 let wend = (seed.right + margin).min(n - 1);
348 let window = &seq[wstart..=wend];
349
350 // Left-anchored and right-anchored consensus votes, each over a short span
351 // unlikely to straddle an indel.
352 let left_vote = (seed.left, (seed.left + vote_span).min(seed.right));
353 let right_vote = (seed.right.saturating_sub(vote_span).max(seed.left), seed.right);
354
355 let mut best: Option<wdp::Aln> = None;
356 for (vs, ve) in [left_vote, right_vote] {
357 let Some(cons) = wdp::consensus(seq, vs, ve, p) else {
358 continue;
359 };
360 let Some(aln) = wdp::wraparound_local(window, &cons) else {
361 continue;
362 };
363 if best.as_ref().is_none_or(|b| aln.score > b.score) {
364 best = Some(aln);
365 }
366 }
367 let aln = best?;
368
369 let start = wstart + aln.start;
370 let end = wstart + aln.end;
371 let region_len = end - start + 1;
372 let copies = region_len as f64 / p as f64;
373 let ident = aln.identity();
374 let score = aln.score as f32;
375
376 if region_len < MIN_REGION_LEN
377 || !passes_copies(copies, score)
378 || ident < MIN_IDENT
379 || score < MIN_SCORE
380 {
381 return None;
382 }
383 Some(Cand {
384 start,
385 end,
386 period: p,
387 ident,
388 copies,
389 score,
390 })
391}
392
393/// Overlap length (bp) of two inclusive 0-based intervals.
394#[inline]
395fn overlap_len(a: &Cand, b: &Cand) -> usize {
396 let lo = a.start.max(b.start);
397 let hi = a.end.min(b.end);
398 if hi >= lo {
399 hi - lo + 1
400 } else {
401 0
402 }
403}
404
405/// True if `c` overlaps `k` by more than [`MAX_OVERLAP_FRAC`] of the shorter.
406#[inline]
407fn clashes(c: &Cand, k: &Cand) -> bool {
408 let ov = overlap_len(c, k);
409 ov > 0 && (ov as f64) / (c.len().min(k.len()) as f64) > MAX_OVERLAP_FRAC
410}
411
412/// Greedy dedup: keep one call per overlapping region.
413///
414/// Candidates are processed strongest-first (highest score). A new candidate
415/// that clashes with something already kept is normally dropped — except when it
416/// has a *smaller* period and scores within [`PERIOD_PREFER_TOL`] of every
417/// clasher, in which case it replaces them, so a repeat is reported at its
418/// fundamental period rather than a coarser indel-absorbing multiple. The
419/// replacement only ever swaps a longer period for an equally-strong shorter
420/// one over the same span, so it cannot introduce a region that was not already
421/// going to be reported.
422fn dedup(mut cands: Vec<Cand>) -> Vec<Cand> {
423 cands.sort_by(|a, b| {
424 b.score
425 .partial_cmp(&a.score)
426 .unwrap_or(std::cmp::Ordering::Equal)
427 .then(a.period.cmp(&b.period))
428 .then(b.len().cmp(&a.len()))
429 .then(
430 b.ident
431 .partial_cmp(&a.ident)
432 .unwrap_or(std::cmp::Ordering::Equal),
433 )
434 .then(a.start.cmp(&b.start))
435 .then(a.end.cmp(&b.end))
436 });
437
438 let mut kept: Vec<Cand> = Vec::new();
439 for c in cands {
440 let clashers: Vec<usize> = kept
441 .iter()
442 .enumerate()
443 .filter(|(_, k)| clashes(&c, k))
444 .map(|(i, _)| i)
445 .collect();
446
447 if clashers.is_empty() {
448 kept.push(c);
449 continue;
450 }
451
452 // Take over only if `c` is the more fundamental description of the same
453 // region: a smaller period, scoring within tolerance of every clasher.
454 // Kept candidates were processed first, so each has score >= c.score.
455 let takeover = clashers.iter().all(|&i| {
456 let k = &kept[i];
457 c.period < k.period && c.score >= k.score * (1.0 - PERIOD_PREFER_TOL)
458 });
459 if takeover {
460 for &i in clashers.iter().rev() {
461 kept.remove(i);
462 }
463 kept.push(c);
464 }
465 }
466 kept
467}
468
469/// Seed and refine every period in `periods`, collecting surviving candidates.
470/// Periods are independent, so this is the unit of parallel work.
471fn collect_cands(seq: &[u8], code: &[u8], periods: impl Iterator<Item = usize>) -> Vec<Cand> {
472 let mut cands: Vec<Cand> = Vec::new();
473 let mut seeds: Vec<Seed> = Vec::new();
474 for p in periods {
475 seeds.clear();
476 scan_period_seeds(code, p, &mut seeds);
477 for &s in seeds.iter() {
478 if let Some(c) = refine(seq, s, p) {
479 cands.push(c);
480 }
481 }
482 }
483 cands
484}
485
486/// Assemble the final sorted repeat list from raw candidates.
487fn finish(mut cands: Vec<Cand>) -> Vec<TandemRepeat> {
488 let mut kept = dedup(std::mem::take(&mut cands));
489 kept.sort_by(|a, b| a.start.cmp(&b.start).then(a.end.cmp(&b.end)));
490 kept.into_iter()
491 .map(|c| TandemRepeat {
492 start: c.start + 1, // 1-based inclusive
493 end: c.end + 1,
494 period: c.period,
495 copies: c.copies,
496 identity: c.ident,
497 score: c.score,
498 consensus_size: c.period,
499 })
500 .collect()
501}
502
503/// Detect tandem repeats in one sequence (ASCII ACGTN, mixed case).
504///
505/// Returns repeats sorted left-to-right, with 1-based inclusive coordinates.
506/// Callers with multi-record FASTA loop over contigs themselves. Single-threaded
507/// and allocation-light, so it composes cleanly when the caller is already
508/// running one sequence per core; for a one-off large sequence see
509/// [`detect_parallel`].
510pub fn detect(seq: &[u8]) -> Vec<TandemRepeat> {
511 let n = seq.len();
512 if n < MIN_REGION_LEN {
513 return Vec::new();
514 }
515 let max_p = MAX_PERIOD.min(n / 2);
516 let code = encode(seq);
517 finish(collect_cands(seq, &code, 1..=max_p))
518}
519
520/// Same result as [`detect`], but the per-period work is split across up to
521/// `threads` OS threads. Identical output regardless of thread count — the final
522/// dedup imposes a total order — so this is purely a latency optimisation for a
523/// single large sequence.
524///
525/// `threads <= 1` runs inline with no threads spawned. Periods are assigned
526/// round-robin so the cheap-seed/expensive-refine long periods spread evenly.
527/// When processing many sequences, prefer running [`detect`] once per sequence
528/// across your own pool over calling this per sequence — that avoids
529/// oversubscribing the CPU.
530pub fn detect_parallel(seq: &[u8], threads: usize) -> Vec<TandemRepeat> {
531 let n = seq.len();
532 if n < MIN_REGION_LEN {
533 return Vec::new();
534 }
535 let max_p = MAX_PERIOD.min(n / 2);
536 let code = encode(seq);
537
538 let threads = threads.min(max_p);
539 if threads <= 1 {
540 return finish(collect_cands(seq, &code, 1..=max_p));
541 }
542
543 let code = &code;
544 let cands: Vec<Cand> = std::thread::scope(|scope| {
545 let handles: Vec<_> = (0..threads)
546 .map(|tid| {
547 scope.spawn(move || {
548 collect_cands(seq, code, (1 + tid..=max_p).step_by(threads))
549 })
550 })
551 .collect();
552 handles
553 .into_iter()
554 .flat_map(|h| h.join().unwrap())
555 .collect()
556 });
557 finish(cands)
558}
559
560#[cfg(test)]
561mod tests {
562 use super::*;
563
564 // Non-repetitive filler used to flank repeats. Hand-checked to contain no
565 // homopolymer run >= 3 and no short-period tandem structure.
566 const FL_L: &[u8] = b"GACTTCAGGATCCGATACGTTAGCACTG";
567 const FL_R: &[u8] = b"CATGACTGACAGTGCACTAGCTAGCTAA";
568
569 /// Repeat of `period` covering `s..=e` (1-based), allowing boundary drift.
570 fn covering(reps: &[TandemRepeat], period: usize, s: usize, e: usize, slack: usize) -> bool {
571 reps.iter()
572 .any(|r| r.period == period && r.start <= s + slack && r.end + slack >= e)
573 }
574
575 #[test]
576 fn parallel_matches_serial() {
577 // detect_parallel must return exactly detect's result at any thread count
578 // — the SWAR seeding and threaded period split must not perturb output.
579 let mut seq = Vec::new();
580 seq.extend_from_slice(FL_L);
581 for _ in 0..20 {
582 seq.extend_from_slice(b"ACGGTTACGATC"); // period-12 array
583 }
584 seq.extend_from_slice(FL_R);
585 for _ in 0..30 {
586 seq.extend_from_slice(b"ATGCA"); // period-5 microsatellite
587 }
588 seq.extend_from_slice(FL_R);
589 let mut rep = Vec::new();
590 for _ in 0..12 {
591 rep.extend_from_slice(b"GTTATCTTTTCG");
592 }
593 rep.remove(50); // an indel, exercising the refinement path too
594 seq.extend_from_slice(&rep);
595
596 let serial = detect(&seq);
597 assert!(!serial.is_empty());
598 for threads in [1, 2, 3, 8, 64] {
599 assert_eq!(
600 detect_parallel(&seq, threads),
601 serial,
602 "detect_parallel(_, {threads}) diverged from detect"
603 );
604 }
605 }
606
607 #[test]
608 fn a_clean_perfect_repeat_period4() {
609 let mut seq = Vec::new();
610 seq.extend_from_slice(FL_L);
611 let rep_start = seq.len();
612 for _ in 0..10 {
613 seq.extend_from_slice(b"ATGC"); // 40 bp, period 4
614 }
615 let rep_end = seq.len();
616 seq.extend_from_slice(FL_R);
617
618 let reps = detect(&seq);
619 let r = reps.iter().find(|r| r.period == 4).expect("period-4 repeat");
620 assert!(
621 r.start <= rep_start + 1 && r.end >= rep_end,
622 "period-4 repeat {}..{} must cover {}..{}",
623 r.start,
624 r.end,
625 rep_start + 1,
626 rep_end
627 );
628 assert_eq!(r.consensus_size, 4);
629 // Perfect 40 bp repeat: every base matches the consensus -> 2 * 40.
630 assert_eq!(r.score, 80.0);
631 assert_eq!(r.identity, 1.0);
632 }
633
634 #[test]
635 fn b_homopolymer_period1() {
636 // 30 A's: a perfect period-1 run scoring 2 * 30 = 60 >= MIN_SCORE.
637 let seq = b"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA";
638 let reps = detect(seq);
639 assert_eq!(reps.len(), 1, "one homopolymer repeat");
640 let r = &reps[0];
641 assert_eq!(r.period, 1);
642 assert_eq!(r.start, 1);
643 assert_eq!(r.end, 30);
644 }
645
646 #[test]
647 fn b2_trivial_short_repeat_filtered() {
648 // A 10 bp homopolymer scores 20, below the TRF significance gate.
649 assert!(
650 detect(b"AAAAAAAAAA").is_empty(),
651 "trivial 10bp microsatellite must be filtered by MIN_SCORE"
652 );
653 }
654
655 #[test]
656 fn c_no_repeats_empty() {
657 let seq = b"GACTTCAGGATCCGATACGTTAGCACTGCATGACAGTCAGTGCTAGACT";
658 let reps = detect(seq);
659 assert!(
660 reps.is_empty(),
661 "non-repetitive sequence must yield no repeats, got {:?}",
662 reps.iter()
663 .map(|r| (r.period, r.start, r.end))
664 .collect::<Vec<_>>()
665 );
666 }
667
668 #[test]
669 fn d_imperfect_repeat_still_detected() {
670 // "ATGC" x 14 with two point mutations.
671 let mut rep = Vec::new();
672 for _ in 0..14 {
673 rep.extend_from_slice(b"ATGC");
674 }
675 rep[10] = b'A';
676 rep[22] = b'T';
677
678 let mut seq = Vec::new();
679 seq.extend_from_slice(FL_L);
680 let rep_start = seq.len();
681 seq.extend_from_slice(&rep);
682 let rep_end = seq.len();
683 seq.extend_from_slice(FL_R);
684
685 let reps = detect(&seq);
686 assert!(
687 covering(&reps, 4, rep_start + 1, rep_end, 6),
688 "imperfect period-4 repeat must still be detected, got {:?}",
689 reps.iter()
690 .map(|r| (r.period, r.start, r.end))
691 .collect::<Vec<_>>()
692 );
693 }
694
695 #[test]
696 fn e_two_separate_regions() {
697 // (ATGC)x8, a non-repetitive spacer, then (CTA)x12. Period 3 is coprime
698 // with 4, so neither region's track can bridge the spacer into the other.
699 let mut seq = Vec::new();
700 let a_start = seq.len();
701 for _ in 0..8 {
702 seq.extend_from_slice(b"ATGC");
703 }
704 seq.extend_from_slice(b"CAGTCAGACTGACAGT");
705 let b_start = seq.len();
706 for _ in 0..12 {
707 seq.extend_from_slice(b"CTA");
708 }
709
710 let reps = detect(&seq);
711 assert_eq!(
712 reps.len(),
713 2,
714 "two separate repeat regions: {:?}",
715 reps.iter()
716 .map(|r| (r.period, r.start, r.end))
717 .collect::<Vec<_>>()
718 );
719 assert_eq!(reps[0].period, 4, "first region period 4");
720 assert_eq!(reps[1].period, 3, "second region period 3");
721 assert!(reps[0].start <= a_start + 1);
722 assert!(reps[1].start <= b_start + 1 && reps[1].end >= b_start + 20);
723 }
724
725 #[test]
726 fn f_mixed_case_and_n_handling() {
727 let mut seq = Vec::new();
728 seq.extend_from_slice(FL_L);
729 for _ in 0..10 {
730 seq.extend_from_slice(b"atgc"); // lower-case period-4 repeat
731 }
732 seq.extend_from_slice(FL_R);
733 seq.extend_from_slice(b"NNNNNNNNNNNNNNNN");
734
735 let reps = detect(&seq);
736 assert!(
737 reps.iter().any(|r| r.period == 4),
738 "lower-case repeat detected"
739 );
740 let n_start = seq.len() - 16 + 1;
741 assert!(
742 !reps.iter().any(|r| r.start >= n_start),
743 "N run must not be reported as a tandem repeat"
744 );
745 }
746
747 // ---- indel-bearing repeats: the cases the ungapped scan cannot reach -----
748
749 #[test]
750 fn g_repeat_with_deletion_is_detected() {
751 // 12 copies of a 12-mer with one base deleted in the middle. The
752 // deletion shifts the period-12 diagonal permanently, so an ungapped
753 // scan sees two shorter repeats at best; WDP spans the whole thing.
754 let mut rep = Vec::new();
755 for _ in 0..12 {
756 rep.extend_from_slice(b"GTTATCTTTTCG");
757 }
758 rep.remove(72); // delete one base mid-repeat
759
760 let mut seq = Vec::new();
761 seq.extend_from_slice(FL_L);
762 let rep_start = seq.len();
763 seq.extend_from_slice(&rep);
764 let rep_end = seq.len();
765 seq.extend_from_slice(FL_R);
766
767 let reps = detect(&seq);
768 assert!(
769 covering(&reps, 12, rep_start + 1, rep_end, 13),
770 "period-12 repeat with a deletion must be detected end-to-end, got {:?}",
771 reps.iter()
772 .map(|r| (r.period, r.start, r.end, r.copies))
773 .collect::<Vec<_>>()
774 );
775 }
776
777 #[test]
778 fn h_repeat_with_insertion_is_detected() {
779 let mut rep = Vec::new();
780 for _ in 0..12 {
781 rep.extend_from_slice(b"GTTATCTTTTCG");
782 }
783 rep.insert(72, b'A'); // insert one base mid-repeat
784
785 let mut seq = Vec::new();
786 seq.extend_from_slice(FL_L);
787 let rep_start = seq.len();
788 seq.extend_from_slice(&rep);
789 let rep_end = seq.len();
790 seq.extend_from_slice(FL_R);
791
792 let reps = detect(&seq);
793 assert!(
794 covering(&reps, 12, rep_start + 1, rep_end, 13),
795 "period-12 repeat with an insertion must be detected end-to-end, got {:?}",
796 reps.iter()
797 .map(|r| (r.period, r.start, r.end, r.copies))
798 .collect::<Vec<_>>()
799 );
800 }
801
802 #[test]
803 fn i_repeat_with_multiple_indels() {
804 // Three separate indels across the repeat — the diagonal is broken
805 // repeatedly, and each break is bridged independently by the alignment.
806 let mut rep = Vec::new();
807 for _ in 0..16 {
808 rep.extend_from_slice(b"ACGGTTACGATC");
809 }
810 rep.remove(150);
811 rep.insert(100, b'T');
812 rep.remove(50);
813
814 let mut seq = Vec::new();
815 seq.extend_from_slice(FL_L);
816 let rep_start = seq.len();
817 seq.extend_from_slice(&rep);
818 let rep_end = seq.len();
819 seq.extend_from_slice(FL_R);
820
821 let reps = detect(&seq);
822 assert!(
823 covering(&reps, 12, rep_start + 1, rep_end, 15),
824 "period-12 repeat with 3 indels must be detected, got {:?}",
825 reps.iter()
826 .map(|r| (r.period, r.start, r.end, r.copies))
827 .collect::<Vec<_>>()
828 );
829 }
830
831 #[test]
832 fn j_two_copy_repeat_at_trf_score_boundary() {
833 // The exact shape the old `len - p` scoring dropped: ~2 copies of a
834 // 12-mer, 25 bp, perfect. TRF scores this 50 and reports it; scoring
835 // only the 13 diagonal pairs gives 26 and silently loses it.
836 let mut seq = Vec::new();
837 seq.extend_from_slice(FL_L);
838 let rep_start = seq.len();
839 seq.extend_from_slice(b"GTTATCTTTTTTGTTATCTTTTTTG"); // 25 bp
840 let rep_end = seq.len();
841 seq.extend_from_slice(FL_R);
842
843 let reps = detect(&seq);
844 let r = reps
845 .iter()
846 .find(|r| r.period == 12 && r.start <= rep_start + 2)
847 .unwrap_or_else(|| {
848 panic!(
849 "2-copy period-12 repeat must clear MIN_SCORE, got {:?}",
850 reps.iter()
851 .map(|r| (r.period, r.start, r.end, r.score))
852 .collect::<Vec<_>>()
853 )
854 });
855 assert_eq!(r.score, 50.0, "score must match TRF's 2*L convention");
856 assert_eq!(r.end, rep_end);
857 }
858
859 #[test]
860 fn k_identity_and_copies_are_sane() {
861 let mut seq = Vec::new();
862 seq.extend_from_slice(FL_L);
863 for _ in 0..10 {
864 seq.extend_from_slice(b"ATGCAG"); // 60 bp, period 6
865 }
866 seq.extend_from_slice(FL_R);
867
868 let reps = detect(&seq);
869 let r = reps.iter().find(|r| r.period == 6).expect("period-6 repeat");
870 assert_eq!(r.identity, 1.0);
871 assert!((r.copies - 10.0).abs() < 0.2, "copies ~10, got {}", r.copies);
872 assert_eq!(r.consensus_size, 6);
873 }
874}
875
876
877