use super::*;
const FAR_K: usize = 12;
const FAR_LEN: usize = 100;
const FLANK: usize = 16;
const MINOR_BASE_DIVISOR: usize = 20;
const IDENTIFYING_PERCENT: usize = 90;
const IDENTIFIED_FRACTION: f64 = 0.25;
const FAMILY_DIVISOR: usize = 4;
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub(super) enum TemplateStart {
Before(usize),
Inside(usize),
Behind,
}
struct Columns {
bases: Vec<Vec<u8>>,
far: Vec<Vec<u64>>,
outer: Vec<usize>,
}
fn inward(seq: &[u8], end: End) -> Vec<u8> {
match end {
End::Five => seq.to_vec(),
End::Three => seq.iter().rev().copied().collect(),
}
}
fn base_code(base: Option<&u8>) -> u8 {
base.and_then(|b| encode_kmer(std::slice::from_ref(b)))
.map_or(4, |code| code as u8)
}
fn far_kmers(window: &[u8], from: usize) -> Vec<u64> {
let stop = (from + FAR_LEN).min(window.len().saturating_sub(FAR_K - 1));
let mut codes: Vec<u64> = (from..stop)
.filter_map(|start| encode_kmer(&window[start..start + FAR_K]))
.collect();
codes.sort_unstable();
codes.dedup();
codes
}
impl Columns {
fn of_candidate(seq: &[u8], windows: &[&[u8]], end: End, edits: usize) -> Self {
let pattern = inward(seq, end);
let texts: Vec<Vec<u8>> = windows.iter().map(|w| inward(w, end)).collect();
let texts: Vec<&[u8]> = texts.iter().map(Vec::as_slice).collect();
let mut searcher = crate::adapter::search::new_searcher_fwd();
let mut best: Vec<Option<sassy::Match>> = vec![None; texts.len()];
for hit in searcher.search_texts(&pattern, &texts, edits) {
let entry = &mut best[hit.text_idx];
if entry
.as_ref()
.is_none_or(|old| (hit.cost, hit.text_start) < (old.cost, old.text_start))
{
*entry = Some(hit.clone());
}
}
let inner = FLANK + pattern.len();
let mut columns = Self {
bases: Vec::new(),
far: Vec::new(),
outer: Vec::new(),
};
for (text, hit) in texts.iter().zip(best) {
let Some(hit) = hit else { continue };
let mut bases = vec![4u8; inner + FLANK];
for (offset, base) in bases[..FLANK].iter_mut().rev().enumerate() {
*base = base_code(
hit.text_start
.checked_sub(offset + 1)
.and_then(|at| text.get(at)),
);
}
let path = hit.to_path();
for (i, pos) in path.iter().enumerate() {
let next = path
.get(i + 1)
.map(|p| (p.0, p.1))
.unwrap_or((pattern.len() as i32, hit.text_end as i32));
if next.0 == pos.0 + 1 && next.1 == pos.1 + 1 {
bases[FLANK + pos.0 as usize] = base_code(text.get(pos.1 as usize));
}
}
for (offset, base) in bases[inner..].iter_mut().enumerate() {
*base = base_code(text.get(hit.text_end + offset));
}
columns.bases.push(bases);
columns.far.push(far_kmers(text, hit.text_end + FLANK));
columns.outer.push(hit.text_start);
}
columns
}
fn at_boundary(windows: &[&[u8]], end: End) -> Self {
let mut columns = Self {
bases: Vec::new(),
far: Vec::new(),
outer: Vec::new(),
};
for window in windows {
let text = inward(window, end);
columns
.bases
.push((0..FLANK).map(|at| base_code(text.get(at))).collect());
columns.far.push(far_kmers(&text, FLANK));
columns.outer.push(0);
}
columns
}
fn median_outer(&self) -> usize {
let mut outer = self.outer.clone();
outer.sort_unstable();
outer.get(outer.len() / 2).copied().unwrap_or(usize::MAX)
}
fn counts(&self, column: usize) -> [usize; 4] {
let mut counts = [0usize; 4];
for bases in &self.bases {
if let Some(&b) = bases.get(column).filter(|&&b| b < 4) {
counts[b as usize] += 1;
}
}
counts
}
fn follows_template(&self, column: usize) -> bool {
let counts = self.counts(column);
let total: usize = counts.iter().sum();
let mut ranked = [0usize, 1, 2, 3];
ranked.sort_by_key(|&b| (std::cmp::Reverse(counts[b]), b));
let (first, second) = (ranked[0] as u8, ranked[1] as u8);
if counts[second as usize] < MIN_SUPPORT_WINDOWS.max(total / MINOR_BASE_DIVISOR) {
return false;
}
let allele = |bases: &[u8]| match bases[column] {
b if b == first => Some(0),
b if b == second => Some(1),
_ => None,
};
let mut presence: KmerMap<[u32; 2]> = KmerMap::default();
for (bases, far) in self.bases.iter().zip(&self.far) {
if let Some(a) = allele(bases) {
for &code in far {
presence.entry(code).or_default()[a] += 1;
}
}
}
let identifies = |code: &u64, a: usize| {
presence.get(code).is_some_and(|held| {
let n = (held[0] + held[1]) as usize;
n >= MIN_SUPPORT_WINDOWS && held[a] as usize * 100 >= n * IDENTIFYING_PERCENT
})
};
let mut identified = [0usize; 2];
let mut windows = [0usize; 2];
for (bases, far) in self.bases.iter().zip(&self.far) {
if let Some(a) = allele(bases) {
windows[a] += 1;
identified[a] += usize::from(far.iter().any(|code| identifies(code, a)));
}
}
(0..2).all(|a| identified[a] as f64 >= IDENTIFIED_FRACTION * windows[a] as f64)
&& self.continue_alike(column, first, second)
}
fn continue_alike(&self, column: usize, first: u8, second: u8) -> bool {
let width = self.bases.first().map_or(0, Vec::len);
let span = column + 1..(column + 1 + FLANK).min(width);
let mut tallies = vec![[[0usize; 4]; 2]; span.len()];
for bases in &self.bases {
let group = match bases[column] {
b if b == first => 0,
b if b == second => 1,
_ => continue,
};
for (tally, &b) in tallies.iter_mut().zip(&bases[span.clone()]) {
if b < 4 {
tally[group][b as usize] += 1;
}
}
}
let top = |counts: &[usize; 4]| (0..4).max_by_key(|&b| (counts[b], std::cmp::Reverse(b)));
let (mut read, mut agree) = (0, 0);
for [a, b] in &tallies {
let floor = MIN_SUPPORT_WINDOWS / 2;
if a.iter().sum::<usize>() >= floor && b.iter().sum::<usize>() >= floor {
read += 1;
agree += usize::from(top(a) == top(b));
}
}
read > 0 && 3 * agree >= 2 * read
}
}
pub(super) fn template_start(
seq: &[u8],
windows: &[&[u8]],
end: End,
error_rate: f64,
) -> (Option<TemplateStart>, usize) {
let columns = Columns::of_candidate(seq, windows, end, edit_budget(error_rate, seq.len()));
let depth = columns.median_outer();
if columns.bases.len() < MIN_SUPPORT_WINDOWS {
return (None, depth);
}
let inner = FLANK + seq.len();
if let Some(column) = (0..FLANK).find(|&c| columns.follows_template(c)) {
return (Some(TemplateStart::Before(FLANK - column)), depth);
}
if let Some(column) = (FLANK..inner).find(|&c| columns.follows_template(c)) {
return (Some(TemplateStart::Inside(column - FLANK)), depth);
}
let behind = columns.follows_template(inner);
(behind.then_some(TemplateStart::Behind), depth)
}
pub(super) fn hit_spans(
seq: &[u8],
windows: &[&[u8]],
end: End,
edits: usize,
) -> Vec<Option<(usize, usize)>> {
let pattern = inward(seq, end);
let texts: Vec<Vec<u8>> = windows.iter().map(|w| inward(w, end)).collect();
let texts: Vec<&[u8]> = texts.iter().map(Vec::as_slice).collect();
let mut searcher = crate::adapter::search::new_searcher_fwd();
let mut best: Vec<Option<(i32, usize, usize)>> = vec![None; texts.len()];
for hit in searcher.search_texts(&pattern, &texts, edits) {
let entry = &mut best[hit.text_idx];
if entry.is_none_or(|(cost, _, _)| hit.cost < cost) {
*entry = Some((hit.cost, hit.text_start, hit.text_end));
}
}
best.into_iter()
.map(|hit| hit.map(|(_, outer, inner)| (outer, inner)))
.collect()
}
pub(super) fn read_through(
spans: &[Option<(usize, usize)>],
primer: &[Option<(usize, usize)>],
) -> usize {
let mut excess: Vec<isize> = spans
.iter()
.zip(primer)
.filter_map(|(own, primer)| {
Some(own.as_ref()?.1.cast_signed() - primer.as_ref()?.1.cast_signed())
})
.collect();
if excess.len() < MIN_SUPPORT_WINDOWS {
return 0;
}
excess.sort_unstable();
let median = excess[excess.len() / 2];
if 2 * excess.iter().filter(|&&e| e > 0).count() > excess.len() {
median.max(0).cast_unsigned()
} else {
0
}
}
pub(super) fn continued_into(
seq: &[u8],
primer: &[u8],
spans: &[Option<(usize, usize)>],
primer_spans: &[Option<(usize, usize)>],
end: End,
) -> Option<Vec<u8>> {
let mut shared = 0;
let mut offsets = Vec::new();
for (own, other) in spans.iter().zip(primer_spans) {
if let (Some((_, inner)), Some((outer, stop))) = (own, other) {
shared += 1;
if inner > outer && inner < stop {
offsets.push(inner - outer);
}
}
}
if shared < MIN_SUPPORT_WINDOWS || 2 * offsets.len() <= shared {
return None;
}
offsets.sort_unstable();
let offset = offsets[offsets.len() / 2];
let primer = inward(primer, end);
let mut joined = inward(seq, end);
joined.extend_from_slice(primer.get(offset..)?);
Some(inward(&joined, end))
}
pub(super) fn template_at_boundary(windows: &[&[u8]], end: End) -> bool {
if windows.len() < MIN_SUPPORT_WINDOWS {
return false;
}
let columns = Columns::at_boundary(windows, end);
if (0..MIN_PATTERN_LEN).any(|c| columns.follows_template(c)) {
return true;
}
let mut counts: KmerMap<u32> = KmerMap::default();
for far in &columns.far {
for &code in far {
*counts.entry(code).or_default() += 1;
}
}
let Some(common) = counts
.iter()
.max_by_key(|&(code, count)| (*count, std::cmp::Reverse(*code)))
.map(|(&code, _)| code)
else {
return false;
};
let mut families: [Vec<&[u8]>; 2] = [Vec::new(), Vec::new()];
for (&window, far) in windows.iter().zip(&columns.far) {
families[usize::from(far.binary_search(&common).is_err())].push(window);
}
families.iter().any(|family| {
family.len() >= MIN_SUPPORT_WINDOWS.max(windows.len() / FAMILY_DIVISOR) && {
let columns = Columns::at_boundary(family, end);
(0..MIN_PATTERN_LEN).any(|c| columns.follows_template(c))
}
})
}
const OVERLAP_MIN: usize = 7;
fn compatible(base: u8, code: u8) -> bool {
let bases = |c| crate::adapter::search::iupac_bases(c).unwrap_or(&[]);
bases(base).iter().all(|b| bases(code).contains(b))
}
pub(super) fn past_boundary(seq: &[u8], boundary: &[u8], end: End) -> Option<usize> {
let (seq, boundary) = (inward(seq, end), inward(boundary, end));
let matches = |s: &[u8], b: &[u8]| s.iter().zip(b).all(|(&x, &y)| compatible(x, y));
if boundary.len() >= MIN_PATTERN_LEN {
let tail = &boundary[boundary.len() - MIN_PATTERN_LEN..];
if let Some(at) = seq.windows(tail.len()).position(|w| matches(w, tail)) {
return Some(at + tail.len()).filter(|&keep| keep < seq.len());
}
}
(OVERLAP_MIN..seq.len().min(boundary.len() + 1))
.rev()
.find(|&n| matches(&seq[..n], &boundary[boundary.len() - n..]))
}
pub(super) fn end_at_insert_boundaries(
candidates: &mut Vec<Candidate>,
boundaries: &[Vec<u8>],
end: End,
) {
for (seq, _, boundary, _, unbounded, _) in candidates.iter_mut() {
let keep = boundaries
.iter()
.filter(|b| *b != seq)
.filter_map(|b| past_boundary(seq, b, end))
.min();
if let Some(keep) = keep {
tracing::debug!(sequence = %String::from_utf8_lossy(seq), keep, "Candidate reads past an insert boundary");
*seq = outer_part(seq, keep, end);
*boundary = true;
*unbounded = false;
}
}
candidates.retain(|(seq, _, _, _, _, _)| seq.len() >= MIN_PATTERN_LEN);
}
pub(super) fn outer_part(seq: &[u8], keep: usize, end: End) -> Vec<u8> {
match end {
End::Five => seq[..keep].to_vec(),
End::Three => seq[seq.len() - keep..].to_vec(),
}
}
pub(super) fn marker_primer_end(seq: &[u8], end: End, error_rate: f64) -> Option<usize> {
let mut searcher = crate::adapter::search::new_searcher_fwd();
let seq = seq.to_ascii_uppercase();
crate::adapter::catalog::MARKER_PRIMERS
.iter()
.filter_map(|&primer| {
let pattern = match end {
End::Five => primer[primer.len() - KMER_K..].to_vec(),
End::Three => crate::adapter::reverse_complement(primer)[..KMER_K].to_vec(),
};
hits(
&mut searcher,
&pattern,
&seq,
edit_budget(error_rate, KMER_K),
)
.into_iter()
.min_by_key(|hit| hit.cost)
.map(|hit| match end {
End::Five => hit.end,
End::Three => seq.len() - hit.start,
})
})
.filter(|&keep| keep >= MIN_PATTERN_LEN)
.min()
}