Skip to main content

Crate tandemox

Crate tandemox 

Source
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.

  1. Seeding — for each period p, walk the “period-p diagonal”, comparing seq[i] with seq[i - p], scoring +1 / -3 and 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-p structure near here”, not to decide what the repeat is or where it ends.

  2. 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 / -7 weights. 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.

  3. 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§

TandemRepeat
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 to threads OS 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.