Expand description
Tandem repeat detection — DB-free, pure-Rust, no external tools.
Finds approximate tandem repeats (period 1..=500, tolerating both mismatches
and indels) in a DNA sequence and returns them as TandemRepeat records.
let seq = b"GACTTCAGGATCCGATACGTTAGCACTGATGCATGCATGCATGCATGCATGCATGCATGCATGCATGCCATGACTGACAGT";
let repeats = tandemox::detect(seq);
assert_eq!(repeats[0].period, 4);Tandem Repeats Finder (TRF) is license-restricted, so no code is derived from it. This is an independent implementation built from the published literature — the wraparound alignment of Fischetti, Landau, Schmidt and Sellers (CPM 1992) — and validated against TRF’s output for concordance.
§Algorithm
Detection runs in two stages: a cheap linear scan proposes candidates, and a dynamic-programming alignment adjudicates them.
-
Seeding — for each period
p, walk the “period-pdiagonal”, comparingseq[i]withseq[i - p], scoring+1/-3and pulling out maximal-scoring runs (Kadane). This is only a detector: it is deliberately permissive, because an indel shifts the diagonal permanently and so a gapped repeat only ever shows up here as a partial run. Its job is to answer “is there any period-pstructure near here”, not to decide what the repeat is or where it ends. -
Refinement — each seed’s ungapped run votes for a consensus motif, and wraparound DP aligns a generous window around the seed against that motif repeated end-to-end, under TRF’s
2 / -7 / -7weights. The alignment supplies everything that gets reported: the true score, the match/mismatch/indel tallies, and the repeat’s boundaries. Indels are absorbed here, which is what the seeding stage structurally cannot do. -
Gating — a refined candidate must clear the significance floor (score >= 50, >= ~1.9 copies, >= 80% identity to the consensus), then greedy overlap dedup keeps one call per region so a repeat is reported at its fundamental period rather than once per harmonic.
Scoring the whole region against the consensus — rather than just the
len - p diagonal pairs — is what puts that score floor on TRF’s scale: a
perfect repeat of length L scores 2L, matching TRF exactly.
Seeding is linear per period and random sequence essentially never sustains a
positive run, so the practical cost sits far below the O(n · 500) bound.
The match-track scan advances a machine word at a time (SWAR), skipping runs
of non-matching positions in bulk. Periods are independent, so detect is
single-threaded and composable while detect_parallel spreads the same
work across threads for a single large sequence, with identical output.
Structs§
- Tandem
Repeat - A single detected tandem repeat on one sequence.
Functions§
- detect
- Detect tandem repeats in one sequence (ASCII ACGTN, mixed case).
- detect_
parallel - Same result as
detect, but the per-period work is split across up tothreadsOS threads. Identical output regardless of thread count — the final dedup imposes a total order — so this is purely a latency optimisation for a single large sequence.