tandemox 0.1.0

Pure-Rust tandem repeat finder: indel-tolerant detection of approximate tandem repeats in DNA, validated for concordance against Tandem Repeats Finder (TRF).
Documentation
//! Wraparound dynamic programming (WDP) — indel-tolerant alignment of a
//! sequence against a consensus motif repeated end-to-end.
//!
//! This is the classic wraparound alignment of Fischetti, Landau, Schmidt and
//! Sellers (*Identifying periodic occurrences of a template with applications to
//! protein structure*, CPM 1992), implemented here from the published algorithm.
//! It is the same technique Tandem Repeats Finder uses to score a candidate
//! repeat, which is why scores produced here line up with TRF's.
//!
//! ## Why wraparound
//!
//! A tandem repeat of period `p` is, by definition, a stretch of sequence that
//! aligns well to some motif `C` (`|C| = p`) written over and over: `C C C C…`.
//! Rather than materialising `C*` and running a quadratic alignment against it,
//! WDP keeps a DP table only `p` columns wide and *wraps* the right edge back
//! onto the left edge: finishing consensus position `p` and stepping to position
//! `1` simply means a new copy has begun. The table is therefore
//! `O(len × p)` regardless of how many copies the repeat contains.
//!
//! ## The circular dependency, and why one extra pass settles it
//!
//! Wrapping makes row `i` depend on itself: the gap-in-sequence (horizontal)
//! edge into column 1 comes from column `p` *of the same row*. Fischetti et al.
//! resolve this with a second pass over the row. It is sufficient because every
//! horizontal step costs `W_INDEL < 0`, so travelling all the way around the
//! consensus is strictly losing — there is no positive-weight cycle, and the
//! improvement chain started from column `p` can only ever extend over a
//! shrinking prefix before it stops paying. We therefore propagate once from
//! the wrapped value and stop at the first column that does not improve.
//!
//! ## Local (Smith–Waterman) semantics
//!
//! Cells floor at zero and the traceback stops there, so the alignment finds the
//! *best-scoring sub-stretch* of the supplied window on its own. Boundaries do
//! not have to be known in advance — the caller passes a generous window and WDP
//! trims it. Because a mismatch costs `-7` against a match's `+2`, extension
//! through a non-repetitive spacer stops almost immediately, which is what keeps
//! this from over-extending the way a plain X-drop does.

use crate::{base_match, is_acgt};

/// TRF-default alignment weights (`trf … 2 7 7 …`): match `+2`, mismatch `-7`,
/// indel `-7`. Reproducing these exactly is what makes [`Aln::score`]
/// comparable to the score in TRF's `.dat` output.
pub(crate) const W_MATCH: i32 = 2;
pub(crate) const W_MISMATCH: i32 = -7;
pub(crate) const W_INDEL: i32 = -7;

/// Traceback direction codes stored per DP cell.
const D_STOP: u8 = 0;
const D_DIAG: u8 = 1;
/// Consume a sequence base against a gap in the consensus.
const D_UP: u8 = 2;
/// Consume a consensus base against a gap in the sequence.
const D_LEFT: u8 = 3;

/// A wraparound local alignment of a window against a repeated consensus.
#[derive(Clone, Debug)]
pub(crate) struct Aln {
    /// Alignment score under TRF's `2 / -7 / -7` weights.
    pub score: i32,
    /// 0-based inclusive offsets *into the window slice* that were aligned.
    pub start: usize,
    pub end: usize,
    pub matches: u32,
    pub mismatches: u32,
    /// Insertions plus deletions in the alignment.
    pub indels: u32,
}

impl Aln {
    /// Fraction of aligned columns that are matches, in `0..=1`.
    ///
    /// The denominator counts indel columns too, so a repeat held together only
    /// by heavy gapping cannot pass an identity gate.
    pub fn identity(&self) -> f64 {
        let denom = self.matches + self.mismatches + self.indels;
        if denom == 0 {
            0.0
        } else {
            self.matches as f64 / denom as f64
        }
    }
}

/// Best local alignment of `seq` against `cons` repeated end-to-end.
///
/// Returns `None` when the inputs are degenerate or nothing scores above zero.
/// Cost is `O(seq.len() × cons.len())` in time and memory.
pub(crate) fn wraparound_local(seq: &[u8], cons: &[u8]) -> Option<Aln> {
    let l = seq.len();
    let p = cons.len();
    if l == 0 || p == 0 {
        return None;
    }

    // Columns are 1..=p; index 0 is unused padding so that `j - 1` is safe.
    let mut prev = vec![0i32; p + 1];
    let mut cur = vec![0i32; p + 1];
    // Traceback grid, row-major: dir[(i - 1) * p + (j - 1)].
    let mut dir = vec![D_STOP; l * p];

    let mut best = 0i32;
    let mut best_i = 0usize;
    let mut best_j = 0usize;

    for i in 1..=l {
        let b = seq[i - 1];
        let row = (i - 1) * p;

        // --- pass 1: ordinary DP, with the diagonal edge into column 1 wrapped
        // from the previous row's column p (i.e. a copy boundary was crossed).
        // The horizontal edge into column 1 needs cur[p], which does not exist
        // yet, so it is deferred to pass 2.
        for j in 1..=p {
            let sub = if base_match(b, cons[j - 1]) {
                W_MATCH
            } else {
                W_MISMATCH
            };
            let diag = if j == 1 { prev[p] } else { prev[j - 1] } + sub;
            let up = prev[j] + W_INDEL;

            let mut v = 0i32;
            let mut d = D_STOP;
            if diag > v {
                v = diag;
                d = D_DIAG;
            }
            if up > v {
                v = up;
                d = D_UP;
            }
            if j > 1 {
                let left = cur[j - 1] + W_INDEL;
                if left > v {
                    v = left;
                    d = D_LEFT;
                }
            }
            cur[j] = v;
            dir[row + j - 1] = d;
        }

        // --- pass 2: propagate the wrapped horizontal edge from column p. Each
        // step costs W_INDEL, so the chain strictly decays; the first column it
        // fails to improve is where it can never improve again.
        let mut carry = cur[p] + W_INDEL;
        for j in 1..=p {
            if carry <= cur[j] {
                break;
            }
            cur[j] = carry;
            dir[row + j - 1] = D_LEFT;
            carry += W_INDEL;
        }

        // Track the best cell in this row (its column becomes the traceback
        // seed, so the index is load-bearing — not a plain max over values).
        #[allow(clippy::needless_range_loop)]
        for j in 1..=p {
            if cur[j] > best {
                best = cur[j];
                best_i = i;
                best_j = j;
            }
        }

        std::mem::swap(&mut prev, &mut cur);
        // `cur` now holds the stale row two back; clear it for reuse.
        for v in cur.iter_mut() {
            *v = 0;
        }
    }

    if best <= 0 {
        return None;
    }

    // --- traceback from the best cell back to the first zero (SW start).
    let (mut i, mut j) = (best_i, best_j);
    let (mut matches, mut mismatches, mut indels) = (0u32, 0u32, 0u32);
    let mut first_i = best_i; // smallest sequence index consumed

    while i > 0 {
        match dir[(i - 1) * p + (j - 1)] {
            D_DIAG => {
                if base_match(seq[i - 1], cons[j - 1]) {
                    matches += 1;
                } else {
                    mismatches += 1;
                }
                first_i = i;
                i -= 1;
                j = if j == 1 { p } else { j - 1 };
            }
            D_UP => {
                indels += 1;
                first_i = i;
                i -= 1;
            }
            D_LEFT => {
                indels += 1;
                j = if j == 1 { p } else { j - 1 };
            }
            _ => break, // D_STOP: alignment starts just after this cell
        }
    }

    Some(Aln {
        score: best,
        start: first_i - 1, // back to 0-based offsets into `seq`
        end: best_i - 1,
        matches,
        mismatches,
        indels,
    })
}

/// Majority-vote consensus of length `p` over `seq[start..=end]`.
///
/// Column `k` polls `seq[start + k]`, `seq[start + k + p]`, … and takes the most
/// common ACGT base. Ambiguity codes are skipped; a column with no ACGT vote at
/// all makes the whole consensus meaningless, so `None` is returned.
///
/// This vote assumes the source stretch is indel-free, which is why callers pass
/// the ungapped seed run rather than the full candidate region — the alignment
/// is what absorbs the indels afterwards.
pub(crate) fn consensus(seq: &[u8], start: usize, end: usize, p: usize) -> Option<Vec<u8>> {
    if p == 0 || start > end || end >= seq.len() {
        return None;
    }
    let mut cons = Vec::with_capacity(p);
    for k in 0..p {
        let mut count = [0u32; 4];
        let mut idx = start + k;
        while idx <= end {
            if let Some(b) = base_index(seq[idx]) {
                count[b] += 1;
            }
            idx += p;
        }
        let mut best_b = 0usize;
        let mut best_c = 0u32;
        for (b, &c) in count.iter().enumerate() {
            if c > best_c {
                best_c = c;
                best_b = b;
            }
        }
        if best_c == 0 {
            return None; // all-N column
        }
        cons.push(b"ACGT"[best_b]);
    }
    Some(cons)
}

#[inline]
fn base_index(b: u8) -> Option<usize> {
    let u = b.to_ascii_uppercase();
    if !is_acgt(u) {
        return None;
    }
    Some(match u {
        b'A' => 0,
        b'C' => 1,
        b'G' => 2,
        _ => 3,
    })
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn perfect_repeat_scores_two_per_base() {
        // 25 bp of a perfect period-12 repeat aligns to its consensus with every
        // base matching, so the score is 2 * 25 = 50. This is the exact case TRF
        // reports as score 50, and is why the whole region (not just the L-p
        // diagonal pairs) has to be scored.
        let cons = b"GTTATCTTTTTT";
        let seq = b"GTTATCTTTTTTGTTATCTTTTTTG"; // 25 bp
        let a = wraparound_local(seq, cons).expect("alignment");
        assert_eq!(a.score, 50);
        assert_eq!(a.matches, 25);
        assert_eq!(a.mismatches, 0);
        assert_eq!(a.indels, 0);
        assert_eq!((a.start, a.end), (0, 24));
    }

    #[test]
    fn wraparound_spans_many_copies() {
        // 10 copies of a 4-mer: 40 matching bases -> 80.
        let cons = b"ATGC";
        let seq = b"ATGCATGCATGCATGCATGCATGCATGCATGCATGCATGC";
        let a = wraparound_local(seq, cons).expect("alignment");
        assert_eq!(a.score, 80);
        assert_eq!(a.matches, 40);
    }

    #[test]
    fn deletion_is_bridged() {
        // Copy 3 is missing its leading 'A'. An ungapped diagonal scan loses the
        // register permanently here; WDP pays one indel and carries on.
        let cons = b"ATGC";
        let seq = b"ATGCATGCTGCATGCATGC"; // 19 bp, one base deleted
        let a = wraparound_local(seq, cons).expect("alignment");
        assert_eq!(a.indels, 1, "the deleted base costs exactly one indel");
        assert_eq!(a.mismatches, 0, "no mismatches once the gap is paid");
        // All 19 surviving bases align; the gap consumes a consensus base only.
        assert_eq!(a.matches, 19);
        assert_eq!(a.score, 19 * W_MATCH + W_INDEL);
    }

    #[test]
    fn insertion_is_bridged() {
        let cons = b"ATGC";
        let seq = b"ATGCATGCTATGCATGCATGC"; // an extra 'T' inserted
        let a = wraparound_local(seq, cons).expect("alignment");
        assert_eq!(a.indels, 1);
        assert_eq!(a.mismatches, 0);
        assert_eq!(a.matches, 20);
    }

    #[test]
    fn local_trims_nonrepetitive_flanks() {
        let cons = b"ATGC";
        // Flank / 8 copies / flank. The alignment must cover only the repeat.
        let seq = b"GACTTCAGGATCCGATACGTTAGCACTGATGCATGCATGCATGCATGCATGCATGCATGCCATGACTGACAGTGCACTAGC";
        let a = wraparound_local(seq, cons).expect("alignment");
        assert_eq!(a.start, 28, "left boundary at the first repeat base");
        assert_eq!(a.end, 59, "right boundary at the last repeat base");
        assert_eq!(a.matches, 32);
        assert_eq!(a.score, 64);
    }

    #[test]
    fn no_alignment_in_random_sequence() {
        let cons = b"ATGCATGCATGC";
        let seq = b"TTTTTTTTTTTTTTTT";
        // Nothing should score positively enough to be a real repeat.
        let a = wraparound_local(seq, cons);
        assert!(a.is_none_or(|x| x.score < 20));
    }

    #[test]
    fn consensus_majority_vote() {
        // Three copies of ATGC; copy 2 has a point change that must be outvoted.
        let seq = b"ATGCAAGCATGC";
        let c = consensus(seq, 0, 11, 4).expect("consensus");
        assert_eq!(&c, b"ATGC");
    }

    #[test]
    fn consensus_rejects_all_n_column() {
        let seq = b"NNNNNNNNNNNN";
        assert!(consensus(seq, 0, 11, 4).is_none());
    }
}