use super::*;
pub(super) fn terminal_support(
seq: &[u8],
windows: &[&[u8]],
end: End,
edits: usize,
) -> (usize, usize) {
let mut searcher = crate::adapter::search::new_searcher_fwd();
let mut best = vec![None; windows.len()];
for hit in searcher.search_texts(seq, windows, edits) {
let distance = match end {
End::Five => hit.text_start,
End::Three => windows[hit.text_idx].len() - hit.text_end,
};
let key = (hit.cost, distance);
let entry = &mut best[hit.text_idx];
if entry.is_none_or(|old| key < old) {
*entry = Some(key);
}
}
let present = best.iter().filter(|hit| hit.is_some()).count();
let anchored = best
.iter()
.flatten()
.filter(|(_, distance)| *distance <= ANCHOR_SLACK)
.count();
(present, anchored)
}
pub(super) fn windows_containing(
searcher: &mut AmbiguousSearcher,
pattern: &[u8],
windows: &[&[u8]],
max_edits: usize,
) -> u32 {
let mut seen = vec![false; windows.len()];
crate::adapter::search::for_each_hit_in_texts(
searcher,
pattern,
windows,
max_edits,
|index, _| seen[index] = true,
);
seen.into_iter().filter(|&present| present).count() as u32
}
pub(super) fn windows_with(
searcher: &mut AmbiguousSearcher,
pattern: &[u8],
windows: &[&[u8]],
max_edits: usize,
) -> Vec<bool> {
let mut seen = vec![false; windows.len()];
crate::adapter::search::for_each_hit_in_texts(
searcher,
pattern,
windows,
max_edits,
|index, _| seen[index] = true,
);
seen
}
pub(super) fn windows_covered(
searcher: &mut AmbiguousSearcher,
pattern: &[u8],
windows: &[&[u8]],
max_edits: usize,
) -> Vec<bool> {
let mut seen = vec![false; windows.len()];
crate::adapter::search::for_each_hit_in_texts(
searcher,
pattern,
windows,
max_edits,
|index, hit| {
if hit.clip_start + hit.clip_end < crate::adapter::MIN_OVERLAP {
seen[index] = true;
}
},
);
seen
}
pub(super) fn same_adapter(a: &[u8], b: &[u8], error_rate: f64) -> bool {
let (short, long) = if a.len() <= b.len() { (a, b) } else { (b, a) };
if short.len() < MIN_PATTERN_LEN {
return short == long;
}
let k = edit_budget(error_rate, short.len());
let mut s = new_ambiguous_searcher();
!hits(&mut s, short, long, k).is_empty()
}
pub(super) fn name_against(seq: &[u8], refs: &[Adapter], error_rate: f64) -> Vec<(String, f32)> {
let mut s = new_ambiguous_searcher();
let mut named: Vec<(String, f32)> = Vec::new();
for r in refs.iter().filter(|r| !crate::adapter::is_construct(r)) {
let (short, long) = if seq.len() <= r.seq.len() {
(seq, r.seq.as_slice())
} else {
(r.seq.as_slice(), seq)
};
if short.len() < MIN_PATTERN_LEN {
continue;
}
let k = edit_budget(error_rate, short.len());
if let Some(h) = hits(&mut s, short, long, k)
.into_iter()
.min_by_key(|h| h.cost)
{
let pct = 100.0 * (1.0 - h.cost as f32 / short.len() as f32);
if pct >= NAME_IDENTITY_MIN {
named.push((r.name.clone(), pct));
}
}
}
named.sort_by(|a, b| b.1.partial_cmp(&a.1).unwrap().then(a.0.cmp(&b.0)));
named.truncate(3);
named
}
pub(super) fn stride_sample<'a>(windows: &[&'a [u8]], cap: usize) -> Vec<&'a [u8]> {
let step = windows.len().div_ceil(cap.max(1)).max(1);
windows.iter().step_by(step).copied().collect()
}
pub(super) fn same_family(a: &[u8], b: &[u8], error_rate: f64) -> bool {
same_adapter(a, b, error_rate)
|| shared_substring(a, b) * 100 >= a.len().min(b.len()) * FAMILY_OVERLAP_PERCENT
}
pub(super) fn other_end_form(
seq: &[u8],
end: End,
candidates: &[(Vec<u8>, f64, u64, End)],
other_windows: &[&[u8]],
error_rate: f64,
) -> Option<(Vec<u8>, f64)> {
let mut searcher = crate::adapter::search::new_searcher_fwd();
let (other, support, oriented_hit) = candidates
.iter()
.filter(|(other, _, _, other_end)| {
*other_end != end
&& other.len() >= KMER_K
&& other.len() * 2 >= seq.len()
&& other.len() < seq.len()
})
.filter_map(|(other, support, weight, _)| {
let oriented = crate::adapter::reverse_complement(other);
let hit = searcher
.search(&oriented, &seq, edit_budget(error_rate, other.len()))
.into_iter()
.min_by_key(|m| (m.cost, m.text_start))?;
let short = match end {
End::Five => hit.text_end < seq.len(),
End::Three => hit.text_start > 0,
};
short.then_some((other, *support, *weight, hit))
})
.max_by(|a, b| {
a.0.len()
.cmp(&b.0.len())
.then(a.2.cmp(&b.2))
.then(b.0.cmp(a.0))
})
.map(|(other, support, _, hit)| (other, support, hit))?;
let outward: Vec<u8> = match end {
End::Five => seq[..oriented_hit.text_start]
.iter()
.rev()
.map(|&b| crate::adapter::reverse_complement(&[b])[0])
.collect(),
End::Three => seq[oriented_hit.text_end..]
.iter()
.map(|&b| crate::adapter::reverse_complement(&[b])[0])
.collect(),
};
let mut best: Vec<Option<(i32, usize, usize)>> = vec![None; other_windows.len()];
for hit in searcher.search_texts(other, other_windows, edit_budget(error_rate, other.len())) {
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));
}
}
let mut extension = Vec::new();
for (step, &expected) in outward.iter().enumerate() {
let (mut carried, mut held) = (0, 0);
for (window, hit) in other_windows.iter().zip(&best) {
let Some((_, start, stop)) = *hit else {
continue;
};
let base = match end {
End::Five => window.get(stop + step),
End::Three => start.checked_sub(step + 1).and_then(|i| window.get(i)),
};
if let Some(&base) = base {
held += 1;
carried += usize::from(base.to_ascii_uppercase() == expected);
}
}
if carried < MIN_SUPPORT_WINDOWS || carried * 2 <= held {
break;
}
extension.push(expected);
}
let form = match end {
End::Five => [other.as_slice(), &extension].concat(),
End::Three => extension.iter().rev().chain(other).copied().collect(),
};
Some((form, support))
}
const FORM_TRIM_SLACK: usize = 3;
pub(super) fn untrimmed_other_end(
seq: &[u8],
end: End,
candidates: &[(Vec<u8>, f64, u64, End)],
other_windows: &[&[u8]],
base: &AdapterConfig,
) -> Option<(Vec<u8>, f64, End)> {
let family = AdapterConfig {
adapters: vec![Adapter {
name: "family".into(),
seq: seq.to_vec(),
role: Role::Adapter,
}],
error_rate: base.error_rate,
end_size: base.end_size,
split: false,
min_piece: 1,
candidate_index: std::sync::OnceLock::new(),
amplicon: false,
};
let mut searcher = crate::adapter::search::new_searcher_fwd();
candidates
.iter()
.filter(|(other, _, _, other_end)| {
*other_end != end && other.len() >= KMER_K && same_family(seq, other, base.error_rate)
})
.filter(|(other, _, _, other_end)| {
let mut best: Vec<Option<(i32, usize, usize)>> = vec![None; other_windows.len()];
for hit in searcher.search_texts(
other,
other_windows,
edit_budget(base.error_rate, other.len()),
) {
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));
}
}
let (mut held, mut untrimmed) = (0, 0);
for (window, hit) in other_windows.iter().zip(&best) {
let Some((_, start, stop)) = *hit else {
continue;
};
held += 1;
let kept = crate::adapter::adapter_segments(window, &family);
untrimmed += usize::from(match other_end {
End::Five => kept
.first()
.is_some_and(|&(first, _)| first + FORM_TRIM_SLACK < stop),
End::Three => kept
.last()
.is_some_and(|&(_, last)| last > start + FORM_TRIM_SLACK),
});
}
held >= MIN_SUPPORT_WINDOWS && untrimmed * 2 >= held
})
.max_by(|a, b| {
a.0.len()
.cmp(&b.0.len())
.then(a.2.cmp(&b.2))
.then(b.0.cmp(&a.0))
})
.map(|(other, support, _, other_end)| (other.clone(), *support, *other_end))
}
pub(super) fn fragment_of(a: &[u8], b: &[u8], error_rate: f64) -> bool {
let short = a.len().min(b.len());
same_adapter(a, b, error_rate) || {
let shared = shared_substring(a, b);
shared * 100 >= short * FAMILY_OVERLAP_PERCENT && short - shared < MIN_PATTERN_LEN
}
}
pub(super) fn shared_substring(a: &[u8], b: &[u8]) -> usize {
longest_common_substring(a, b).max(longest_common_substring(
&crate::adapter::reverse_complement(a),
b,
))
}
pub(super) fn longest_common_substring(a: &[u8], b: &[u8]) -> usize {
let mut longest = 0;
let mut previous = vec![0usize; b.len() + 1];
for &x in a {
let mut current = vec![0usize; b.len() + 1];
for (j, &y) in b.iter().enumerate() {
if x == y {
current[j + 1] = previous[j] + 1;
longest = longest.max(current[j + 1]);
}
}
previous = current;
}
longest
}