mod wdp;
const MAX_PERIOD: usize = 500;
const MIN_REGION_LEN: usize = 10;
const MIN_COPIES: f64 = 1.9;
const MIN_COPIES_STRONG: f64 = 1.8;
const STRONG_LOWCOPY_SCORE: f32 = 150.0;
const MIN_IDENT: f64 = 0.80;
const MIN_SCORE: f32 = 50.0;
const SEED_MATCH: i64 = 1;
const SEED_MISMATCH: i64 = -3;
const SEED_MIN_SUM: i64 = 8;
const SEED_SUM_PERIOD_DIV: i64 = 8;
const REFINE_MARGIN_PERIODS: usize = 6;
const REFINE_MARGIN_CONST: usize = 50;
const CONS_VOTE_PERIODS: usize = 3;
const MAX_OVERLAP_FRAC: f64 = 0.50;
const PERIOD_PREFER_TOL: f32 = 0.15;
#[derive(Clone, Debug, PartialEq)]
pub struct TandemRepeat {
pub start: usize,
pub end: usize,
pub period: usize,
pub copies: f64,
pub identity: f64,
pub score: f32,
pub consensus_size: usize,
}
#[derive(Clone, Debug)]
struct Cand {
start: usize,
end: usize,
period: usize,
ident: f64,
copies: f64,
score: f32,
}
impl Cand {
#[inline]
fn len(&self) -> usize {
self.end - self.start + 1
}
}
#[inline]
pub(crate) fn is_acgt(b: u8) -> bool {
matches!(b, b'A' | b'C' | b'G' | b'T')
}
#[inline]
pub(crate) fn base_match(a: u8, b: u8) -> bool {
let x = a.to_ascii_uppercase();
x == b.to_ascii_uppercase() && is_acgt(x)
}
const NON_ACGT: u8 = 4;
fn encode(seq: &[u8]) -> Vec<u8> {
seq.iter()
.map(|&b| match b & !0x20 {
b'A' => 0,
b'C' => 1,
b'G' => 2,
b'T' => 3,
_ => NON_ACGT,
})
.collect()
}
const SWAR_LOW: u64 = 0x0101010101010101;
const SWAR_HIGH: u64 = 0x8080808080808080;
const SWAR_VALID: u64 = 0xFCFC_FCFC_FCFC_FCFC;
#[inline]
fn zero_byte_mask(y: u64) -> u64 {
y.wrapping_sub(SWAR_LOW) & !y & SWAR_HIGH
}
#[inline]
fn load8(code: &[u8], i: usize) -> u64 {
let mut a = [0u8; 8];
a.copy_from_slice(&code[i..i + 8]);
u64::from_le_bytes(a)
}
#[derive(Clone, Copy, Debug)]
struct Seed {
left: usize,
right: usize,
}
#[inline]
fn seed_threshold(p: usize) -> i64 {
SEED_MIN_SUM.max(p as i64 / SEED_SUM_PERIOD_DIV)
}
#[inline]
fn passes_copies(copies: f64, score: f32) -> bool {
copies >= MIN_COPIES || (copies >= MIN_COPIES_STRONG && score >= STRONG_LOWCOPY_SCORE)
}
#[inline]
fn next_match(code: &[u8], p: usize, mut t: usize, m: usize) -> usize {
let n = code.len();
while t < m {
if t + 8 <= m && p + t + 8 <= n {
let a = load8(code, t);
let b = load8(code, p + t);
let hits = zero_byte_mask(a ^ b) & zero_byte_mask(a & SWAR_VALID);
if hits != 0 {
return t + (hits.trailing_zeros() as usize / 8);
}
t += 8;
} else {
if code[t] < NON_ACGT && code[p + t] == code[t] {
return t;
}
t += 1;
}
}
m
}
fn scan_period_seeds(code: &[u8], p: usize, out: &mut Vec<Seed>) {
let n = code.len();
if p == 0 || p >= n {
return;
}
let thresh = seed_threshold(p);
let m = n - p;
let mut t = next_match(code, p, 0, m);
while t < m {
let mut sum: i64 = 0;
let mut best_sum: i64 = i64::MIN;
let mut best_end = t;
let mut k = t;
while k < m {
sum += if code[k] < NON_ACGT && code[p + k] == code[k] {
SEED_MATCH
} else {
SEED_MISMATCH
};
if sum > best_sum {
best_sum = sum;
best_end = k;
}
if sum < 0 {
break;
}
k += 1;
}
if best_sum >= thresh {
out.push(Seed {
left: t,
right: p + best_end,
});
}
t = next_match(code, p, best_end + 1, m);
}
}
fn refine(seq: &[u8], seed: Seed, p: usize) -> Option<Cand> {
let n = seq.len();
let vote_span = CONS_VOTE_PERIODS * p;
let margin = REFINE_MARGIN_PERIODS * p + REFINE_MARGIN_CONST;
let wstart = seed.left.saturating_sub(margin);
let wend = (seed.right + margin).min(n - 1);
let window = &seq[wstart..=wend];
let left_vote = (seed.left, (seed.left + vote_span).min(seed.right));
let right_vote = (seed.right.saturating_sub(vote_span).max(seed.left), seed.right);
let mut best: Option<wdp::Aln> = None;
for (vs, ve) in [left_vote, right_vote] {
let Some(cons) = wdp::consensus(seq, vs, ve, p) else {
continue;
};
let Some(aln) = wdp::wraparound_local(window, &cons) else {
continue;
};
if best.as_ref().is_none_or(|b| aln.score > b.score) {
best = Some(aln);
}
}
let aln = best?;
let start = wstart + aln.start;
let end = wstart + aln.end;
let region_len = end - start + 1;
let copies = region_len as f64 / p as f64;
let ident = aln.identity();
let score = aln.score as f32;
if region_len < MIN_REGION_LEN
|| !passes_copies(copies, score)
|| ident < MIN_IDENT
|| score < MIN_SCORE
{
return None;
}
Some(Cand {
start,
end,
period: p,
ident,
copies,
score,
})
}
#[inline]
fn overlap_len(a: &Cand, b: &Cand) -> usize {
let lo = a.start.max(b.start);
let hi = a.end.min(b.end);
if hi >= lo {
hi - lo + 1
} else {
0
}
}
#[inline]
fn clashes(c: &Cand, k: &Cand) -> bool {
let ov = overlap_len(c, k);
ov > 0 && (ov as f64) / (c.len().min(k.len()) as f64) > MAX_OVERLAP_FRAC
}
fn dedup(mut cands: Vec<Cand>) -> Vec<Cand> {
cands.sort_by(|a, b| {
b.score
.partial_cmp(&a.score)
.unwrap_or(std::cmp::Ordering::Equal)
.then(a.period.cmp(&b.period))
.then(b.len().cmp(&a.len()))
.then(
b.ident
.partial_cmp(&a.ident)
.unwrap_or(std::cmp::Ordering::Equal),
)
.then(a.start.cmp(&b.start))
.then(a.end.cmp(&b.end))
});
let mut kept: Vec<Cand> = Vec::new();
for c in cands {
let clashers: Vec<usize> = kept
.iter()
.enumerate()
.filter(|(_, k)| clashes(&c, k))
.map(|(i, _)| i)
.collect();
if clashers.is_empty() {
kept.push(c);
continue;
}
let takeover = clashers.iter().all(|&i| {
let k = &kept[i];
c.period < k.period && c.score >= k.score * (1.0 - PERIOD_PREFER_TOL)
});
if takeover {
for &i in clashers.iter().rev() {
kept.remove(i);
}
kept.push(c);
}
}
kept
}
fn collect_cands(seq: &[u8], code: &[u8], periods: impl Iterator<Item = usize>) -> Vec<Cand> {
let mut cands: Vec<Cand> = Vec::new();
let mut seeds: Vec<Seed> = Vec::new();
for p in periods {
seeds.clear();
scan_period_seeds(code, p, &mut seeds);
for &s in seeds.iter() {
if let Some(c) = refine(seq, s, p) {
cands.push(c);
}
}
}
cands
}
fn finish(mut cands: Vec<Cand>) -> Vec<TandemRepeat> {
let mut kept = dedup(std::mem::take(&mut cands));
kept.sort_by(|a, b| a.start.cmp(&b.start).then(a.end.cmp(&b.end)));
kept.into_iter()
.map(|c| TandemRepeat {
start: c.start + 1, end: c.end + 1,
period: c.period,
copies: c.copies,
identity: c.ident,
score: c.score,
consensus_size: c.period,
})
.collect()
}
pub fn detect(seq: &[u8]) -> Vec<TandemRepeat> {
let n = seq.len();
if n < MIN_REGION_LEN {
return Vec::new();
}
let max_p = MAX_PERIOD.min(n / 2);
let code = encode(seq);
finish(collect_cands(seq, &code, 1..=max_p))
}
pub fn detect_parallel(seq: &[u8], threads: usize) -> Vec<TandemRepeat> {
let n = seq.len();
if n < MIN_REGION_LEN {
return Vec::new();
}
let max_p = MAX_PERIOD.min(n / 2);
let code = encode(seq);
let threads = threads.min(max_p);
if threads <= 1 {
return finish(collect_cands(seq, &code, 1..=max_p));
}
let code = &code;
let cands: Vec<Cand> = std::thread::scope(|scope| {
let handles: Vec<_> = (0..threads)
.map(|tid| {
scope.spawn(move || {
collect_cands(seq, code, (1 + tid..=max_p).step_by(threads))
})
})
.collect();
handles
.into_iter()
.flat_map(|h| h.join().unwrap())
.collect()
});
finish(cands)
}
#[cfg(test)]
mod tests {
use super::*;
const FL_L: &[u8] = b"GACTTCAGGATCCGATACGTTAGCACTG";
const FL_R: &[u8] = b"CATGACTGACAGTGCACTAGCTAGCTAA";
fn covering(reps: &[TandemRepeat], period: usize, s: usize, e: usize, slack: usize) -> bool {
reps.iter()
.any(|r| r.period == period && r.start <= s + slack && r.end + slack >= e)
}
#[test]
fn parallel_matches_serial() {
let mut seq = Vec::new();
seq.extend_from_slice(FL_L);
for _ in 0..20 {
seq.extend_from_slice(b"ACGGTTACGATC"); }
seq.extend_from_slice(FL_R);
for _ in 0..30 {
seq.extend_from_slice(b"ATGCA"); }
seq.extend_from_slice(FL_R);
let mut rep = Vec::new();
for _ in 0..12 {
rep.extend_from_slice(b"GTTATCTTTTCG");
}
rep.remove(50); seq.extend_from_slice(&rep);
let serial = detect(&seq);
assert!(!serial.is_empty());
for threads in [1, 2, 3, 8, 64] {
assert_eq!(
detect_parallel(&seq, threads),
serial,
"detect_parallel(_, {threads}) diverged from detect"
);
}
}
#[test]
fn a_clean_perfect_repeat_period4() {
let mut seq = Vec::new();
seq.extend_from_slice(FL_L);
let rep_start = seq.len();
for _ in 0..10 {
seq.extend_from_slice(b"ATGC"); }
let rep_end = seq.len();
seq.extend_from_slice(FL_R);
let reps = detect(&seq);
let r = reps.iter().find(|r| r.period == 4).expect("period-4 repeat");
assert!(
r.start <= rep_start + 1 && r.end >= rep_end,
"period-4 repeat {}..{} must cover {}..{}",
r.start,
r.end,
rep_start + 1,
rep_end
);
assert_eq!(r.consensus_size, 4);
assert_eq!(r.score, 80.0);
assert_eq!(r.identity, 1.0);
}
#[test]
fn b_homopolymer_period1() {
let seq = b"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA";
let reps = detect(seq);
assert_eq!(reps.len(), 1, "one homopolymer repeat");
let r = &reps[0];
assert_eq!(r.period, 1);
assert_eq!(r.start, 1);
assert_eq!(r.end, 30);
}
#[test]
fn b2_trivial_short_repeat_filtered() {
assert!(
detect(b"AAAAAAAAAA").is_empty(),
"trivial 10bp microsatellite must be filtered by MIN_SCORE"
);
}
#[test]
fn c_no_repeats_empty() {
let seq = b"GACTTCAGGATCCGATACGTTAGCACTGCATGACAGTCAGTGCTAGACT";
let reps = detect(seq);
assert!(
reps.is_empty(),
"non-repetitive sequence must yield no repeats, got {:?}",
reps.iter()
.map(|r| (r.period, r.start, r.end))
.collect::<Vec<_>>()
);
}
#[test]
fn d_imperfect_repeat_still_detected() {
let mut rep = Vec::new();
for _ in 0..14 {
rep.extend_from_slice(b"ATGC");
}
rep[10] = b'A';
rep[22] = b'T';
let mut seq = Vec::new();
seq.extend_from_slice(FL_L);
let rep_start = seq.len();
seq.extend_from_slice(&rep);
let rep_end = seq.len();
seq.extend_from_slice(FL_R);
let reps = detect(&seq);
assert!(
covering(&reps, 4, rep_start + 1, rep_end, 6),
"imperfect period-4 repeat must still be detected, got {:?}",
reps.iter()
.map(|r| (r.period, r.start, r.end))
.collect::<Vec<_>>()
);
}
#[test]
fn e_two_separate_regions() {
let mut seq = Vec::new();
let a_start = seq.len();
for _ in 0..8 {
seq.extend_from_slice(b"ATGC");
}
seq.extend_from_slice(b"CAGTCAGACTGACAGT");
let b_start = seq.len();
for _ in 0..12 {
seq.extend_from_slice(b"CTA");
}
let reps = detect(&seq);
assert_eq!(
reps.len(),
2,
"two separate repeat regions: {:?}",
reps.iter()
.map(|r| (r.period, r.start, r.end))
.collect::<Vec<_>>()
);
assert_eq!(reps[0].period, 4, "first region period 4");
assert_eq!(reps[1].period, 3, "second region period 3");
assert!(reps[0].start <= a_start + 1);
assert!(reps[1].start <= b_start + 1 && reps[1].end >= b_start + 20);
}
#[test]
fn f_mixed_case_and_n_handling() {
let mut seq = Vec::new();
seq.extend_from_slice(FL_L);
for _ in 0..10 {
seq.extend_from_slice(b"atgc"); }
seq.extend_from_slice(FL_R);
seq.extend_from_slice(b"NNNNNNNNNNNNNNNN");
let reps = detect(&seq);
assert!(
reps.iter().any(|r| r.period == 4),
"lower-case repeat detected"
);
let n_start = seq.len() - 16 + 1;
assert!(
!reps.iter().any(|r| r.start >= n_start),
"N run must not be reported as a tandem repeat"
);
}
#[test]
fn g_repeat_with_deletion_is_detected() {
let mut rep = Vec::new();
for _ in 0..12 {
rep.extend_from_slice(b"GTTATCTTTTCG");
}
rep.remove(72);
let mut seq = Vec::new();
seq.extend_from_slice(FL_L);
let rep_start = seq.len();
seq.extend_from_slice(&rep);
let rep_end = seq.len();
seq.extend_from_slice(FL_R);
let reps = detect(&seq);
assert!(
covering(&reps, 12, rep_start + 1, rep_end, 13),
"period-12 repeat with a deletion must be detected end-to-end, got {:?}",
reps.iter()
.map(|r| (r.period, r.start, r.end, r.copies))
.collect::<Vec<_>>()
);
}
#[test]
fn h_repeat_with_insertion_is_detected() {
let mut rep = Vec::new();
for _ in 0..12 {
rep.extend_from_slice(b"GTTATCTTTTCG");
}
rep.insert(72, b'A');
let mut seq = Vec::new();
seq.extend_from_slice(FL_L);
let rep_start = seq.len();
seq.extend_from_slice(&rep);
let rep_end = seq.len();
seq.extend_from_slice(FL_R);
let reps = detect(&seq);
assert!(
covering(&reps, 12, rep_start + 1, rep_end, 13),
"period-12 repeat with an insertion must be detected end-to-end, got {:?}",
reps.iter()
.map(|r| (r.period, r.start, r.end, r.copies))
.collect::<Vec<_>>()
);
}
#[test]
fn i_repeat_with_multiple_indels() {
let mut rep = Vec::new();
for _ in 0..16 {
rep.extend_from_slice(b"ACGGTTACGATC");
}
rep.remove(150);
rep.insert(100, b'T');
rep.remove(50);
let mut seq = Vec::new();
seq.extend_from_slice(FL_L);
let rep_start = seq.len();
seq.extend_from_slice(&rep);
let rep_end = seq.len();
seq.extend_from_slice(FL_R);
let reps = detect(&seq);
assert!(
covering(&reps, 12, rep_start + 1, rep_end, 15),
"period-12 repeat with 3 indels must be detected, got {:?}",
reps.iter()
.map(|r| (r.period, r.start, r.end, r.copies))
.collect::<Vec<_>>()
);
}
#[test]
fn j_two_copy_repeat_at_trf_score_boundary() {
let mut seq = Vec::new();
seq.extend_from_slice(FL_L);
let rep_start = seq.len();
seq.extend_from_slice(b"GTTATCTTTTTTGTTATCTTTTTTG"); let rep_end = seq.len();
seq.extend_from_slice(FL_R);
let reps = detect(&seq);
let r = reps
.iter()
.find(|r| r.period == 12 && r.start <= rep_start + 2)
.unwrap_or_else(|| {
panic!(
"2-copy period-12 repeat must clear MIN_SCORE, got {:?}",
reps.iter()
.map(|r| (r.period, r.start, r.end, r.score))
.collect::<Vec<_>>()
)
});
assert_eq!(r.score, 50.0, "score must match TRF's 2*L convention");
assert_eq!(r.end, rep_end);
}
#[test]
fn k_identity_and_copies_are_sane() {
let mut seq = Vec::new();
seq.extend_from_slice(FL_L);
for _ in 0..10 {
seq.extend_from_slice(b"ATGCAG"); }
seq.extend_from_slice(FL_R);
let reps = detect(&seq);
let r = reps.iter().find(|r| r.period == 6).expect("period-6 repeat");
assert_eq!(r.identity, 1.0);
assert!((r.copies - 10.0).abs() < 0.2, "copies ~10, got {}", r.copies);
assert_eq!(r.consensus_size, 6);
}
}