use crate::{base_match, is_acgt};
pub(crate) const W_MATCH: i32 = 2;
pub(crate) const W_MISMATCH: i32 = -7;
pub(crate) const W_INDEL: i32 = -7;
const D_STOP: u8 = 0;
const D_DIAG: u8 = 1;
const D_UP: u8 = 2;
const D_LEFT: u8 = 3;
#[derive(Clone, Debug)]
pub(crate) struct Aln {
pub score: i32,
pub start: usize,
pub end: usize,
pub matches: u32,
pub mismatches: u32,
pub indels: u32,
}
impl Aln {
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
}
}
}
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;
}
let mut prev = vec![0i32; p + 1];
let mut cur = vec![0i32; p + 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;
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;
}
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;
}
#[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);
for v in cur.iter_mut() {
*v = 0;
}
}
if best <= 0 {
return None;
}
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;
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, }
}
Some(Aln {
score: best,
start: first_i - 1, end: best_i - 1,
matches,
mismatches,
indels,
})
}
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; }
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() {
let cons = b"GTTATCTTTTTT";
let seq = b"GTTATCTTTTTTGTTATCTTTTTTG"; 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() {
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() {
let cons = b"ATGC";
let seq = b"ATGCATGCTGCATGCATGC"; 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");
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"; 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";
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";
let a = wraparound_local(seq, cons);
assert!(a.is_none_or(|x| x.score < 20));
}
#[test]
fn consensus_majority_vote() {
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());
}
}