use super::*;
pub(super) const MAX_SEED_EXPANSIONS: usize = 256;
#[derive(Debug, Clone)]
pub(crate) struct CandidateIndex {
pub(super) seeds: Option<SeedTable>,
pub(super) budgets: Vec<Budget>,
pub(super) plain: Vec<bool>,
pub(super) unfiltered: Vec<bool>,
pub(super) terminal_batches: Vec<TerminalBatch>,
pub(super) singletons: Vec<bool>,
pub(super) end_seeds: Option<SeedTable>,
pub(super) end_reach: usize,
pub(super) panel_gates: Vec<bool>,
pub(super) split_classes: Vec<usize>,
pub(super) paired: Vec<bool>,
pub(super) opens: Vec<bool>,
pub(super) whole_primers: Vec<Option<WholePrimer>>,
}
pub(super) const CONSTRUCT_BARCODE_LEN: usize = 16;
pub(super) fn bounds_barcode(adapter: &Adapter) -> bool {
let seq = adapter.seq.to_ascii_uppercase();
is_construct(adapter)
|| super::catalog::INSERT_SIDE_FLANKS
.iter()
.any(|flank| seq == *flank || seq == reverse_complement(flank))
}
pub(crate) fn matches_marker_primer(seq: &[u8], error_rate: f64) -> bool {
marker_primer_opens(seq, error_rate).is_some()
}
pub(crate) fn marker_primer_opens(seq: &[u8], error_rate: f64) -> Option<bool> {
marker_primer_of(seq, error_rate).map(|(_, opens)| opens)
}
pub(crate) fn marker_primer_of(seq: &[u8], error_rate: f64) -> Option<(&'static [u8], bool)> {
let seq = seq.to_ascii_uppercase();
let mut searcher = new_ambiguous_searcher();
super::catalog::MARKER_PRIMERS
.iter()
.filter_map(|&primer| {
let best = if seq.len() >= primer.len() {
if seq.len() >= primer.len() + MIN_OVERLAP {
return None;
}
search::hits(
&mut searcher,
primer,
&seq,
edit_budget(error_rate, primer.len()),
)
.into_iter()
.min_by_key(|hit| hit.cost)
} else {
if seq.len() + MIN_OVERLAP <= primer.len() {
return None;
}
search::hits(
&mut searcher,
&seq,
primer,
edit_budget(error_rate, seq.len()),
)
.into_iter()
.filter(|hit| hit.start == 0 || hit.end == primer.len())
.min_by_key(|hit| hit.cost)
};
best.map(|hit| (primer, hit))
})
.min_by_key(|(_, hit)| hit.cost)
.map(|(primer, hit)| (primer, !hit.rc))
}
#[derive(Debug, Clone)]
pub(super) struct WholePrimer {
pub(super) seq: Vec<u8>,
pub(super) k_mid: [usize; INTERIOR_CLASSES],
}
pub(crate) fn with_marker_codes(seq: &[u8], error_rate: f64) -> Vec<u8> {
let mut out = seq.to_ascii_uppercase();
if !matches_marker_primer(&out, error_rate) {
return out;
}
let mut searcher = search::new_searcher_fwd();
let mut best: Option<(sassy::Match, Vec<u8>)> = None;
for primer in super::catalog::MARKER_PRIMERS
.iter()
.flat_map(|&primer| [primer.to_vec(), reverse_complement(primer)])
{
let (pattern, text) = if out.len() <= primer.len() {
(&out, &primer)
} else {
(&primer, &out)
};
for m in searcher.search(pattern, text, edit_budget(error_rate, pattern.len())) {
if best.as_ref().is_none_or(|(b, _)| m.cost < b.cost) {
best = Some((m, primer.clone()));
}
}
}
let Some((m, primer)) = best else {
return out;
};
let seq_is_pattern = out.len() <= primer.len();
let (mut p, mut t) = (m.pattern_start, m.text_start);
for e in &m.cigar.ops {
let op = e.op.to_char();
for _ in 0..e.cnt {
match op {
'=' | 'X' => {
let (i, j) = if seq_is_pattern { (p, t) } else { (t, p) };
if op == '=' && !b"ACGT".contains(&primer[j]) {
out[i] = primer[j];
}
p += 1;
t += 1;
},
'I' => p += 1,
_ => t += 1,
}
}
}
out
}
pub(super) fn is_umi(adapter: &Adapter) -> bool {
let seq = adapter.seq.to_ascii_uppercase();
super::catalog::UMIS
.iter()
.any(|umi| seq == *umi || seq == reverse_complement(umi))
}
fn is_panel_barcode(adapter: &Adapter, adapters: &[Adapter]) -> bool {
let member = |a: &Adapter| a.role == Role::Barcode && !bounds_barcode(a);
member(adapter)
&& adapters
.iter()
.filter(|other| member(other) && other.seq.len() == adapter.seq.len())
.nth(1)
.is_some()
}
pub(super) fn is_construct(adapter: &Adapter) -> bool {
adapter.role == Role::Barcode
&& adapter
.seq
.split(|&b| !b.eq_ignore_ascii_case(&b'N'))
.any(|run| run.len() >= CONSTRUCT_BARCODE_LEN)
}
#[derive(Debug, Clone)]
pub(super) struct TerminalBatch {
pub(super) adapter_indices: Vec<usize>,
pub(super) encoded: EncodedAdapterBatch,
pub(super) len: usize,
pub(super) k_end: usize,
}
impl CandidateIndex {
pub(super) fn new(
adapters: &[Adapter],
error_rate: f64,
end_size: usize,
include_interior: bool,
) -> Self {
let searchable: Vec<bool> = adapters
.iter()
.map(|adapter| adapter.seq.len() >= MIN_PATTERN_LEN)
.collect();
let mut budgets: Vec<Budget> = adapters
.iter()
.map(|adapter| Budget::new(&adapter.seq, error_rate, end_size))
.collect();
let caps: Vec<usize> = budgets.iter().map(|b| b.k_end).collect();
let near = family_budgets(
adapters,
&searchable,
&caps,
4.0 * (FLANK_SLACK + 1) as f64,
TERMINAL_CHANCE_HITS_PER_READ,
);
let far = family_budgets(
adapters,
&searchable,
&near,
4.0 * (end_size + 1) as f64,
TERMINAL_CHANCE_HITS_PER_READ,
);
for ((budget, k_end), k_far) in budgets.iter_mut().zip(near).zip(far) {
budget.k_end = k_end;
budget.k_far = k_far;
}
let flanked = adapters.iter().any(bounds_barcode);
let split_classes: Vec<usize> = adapters
.iter()
.zip(&searchable)
.map(|(adapter, &searchable)| {
if !searchable
|| (flanked && is_panel_barcode(adapter, adapters))
|| is_umi(adapter)
{
0
} else if adapter.role == Role::Adapter {
INTERIOR_CLASSES
} else {
let exact = chance_cumulative(&adapter.seq, 0)[0];
(0..INTERIOR_CLASSES)
.take_while(|&class| {
exact * interior_positions(class) <= INTERIOR_CHANCE_HITS_PER_READ
})
.count()
}
})
.collect();
let splitting: Vec<bool> = split_classes.iter().map(|&c| c > 0).collect();
for class in 0..INTERIOR_CLASSES {
let caps: Vec<usize> = budgets.iter().map(|b| b.k_mid[class]).collect();
let splitting_here: Vec<bool> = split_classes.iter().map(|&c| c > class).collect();
let edits = family_budgets(
adapters,
&splitting_here,
&caps,
interior_positions(class),
INTERIOR_CHANCE_HITS_PER_READ,
);
for (budget, k) in budgets.iter_mut().zip(edits) {
let previous = class.checked_sub(1).map_or(usize::MAX, |c| budget.k_mid[c]);
budget.k_mid[class] = k.min(previous);
}
}
let senses: Vec<Option<bool>> = adapters
.iter()
.zip(&searchable)
.map(|(adapter, &searchable)| {
if searchable && adapter.role == Role::Primer {
marker_primer_opens(&adapter.seq, error_rate)
} else {
None
}
})
.collect();
let paired: Vec<bool> = senses.iter().map(Option::is_some).collect();
let caps: Vec<usize> = budgets.iter().map(|b| b.k_end).collect();
for class in 0..INTERIOR_CLASSES {
let edits = pair_budgets(
adapters,
&paired,
&caps,
interior_positions(class),
INTERIOR_CHANCE_HITS_PER_READ,
);
for ((budget, k), &paired) in budgets.iter_mut().zip(edits).zip(&paired) {
let previous = class
.checked_sub(1)
.map_or(usize::MAX, |c| budget.k_pair[c]);
budget.k_pair[class] = if paired { k.min(previous) } else { 0 };
}
}
let plain: Vec<bool> = adapters
.iter()
.map(|adapter| is_plain_acgt(&adapter.seq))
.collect();
let mut unfiltered = vec![false; adapters.len()];
let seeds = if include_interior {
let mut seeds: BTreeMap<Vec<u8>, Vec<usize>> = BTreeMap::new();
for (adapter_idx, adapter) in adapters.iter().enumerate() {
let k_mid = budgets[adapter_idx].interior_max();
if !splitting[adapter_idx] {
continue;
}
let pattern = adapter.seq.to_ascii_uppercase();
let forward = partition_seeds(&pattern, k_mid);
let reverse = partition_seeds(&reverse_complement(&pattern), k_mid);
match (forward, reverse) {
(Some(forward), Some(reverse))
if window_coverage(&forward, &reverse, &budgets[adapter_idx])
<= MAX_WINDOW_COVERAGE =>
{
for seed in forward.into_iter().chain(reverse) {
let owners = seeds.entry(seed).or_default();
if owners.last() != Some(&adapter_idx) {
owners.push(adapter_idx);
}
}
},
_ => unfiltered[adapter_idx] = true,
}
}
SeedTable::new(seeds)
} else {
None
};
let mut by_len: BTreeMap<usize, Vec<usize>> = BTreeMap::new();
for (adapter_idx, adapter) in adapters.iter().enumerate() {
let len = adapter.seq.len();
if searchable[adapter_idx]
&& len <= MAX_TILED_PATTERN_LEN
&& adapter.role == Role::Barcode
{
by_len.entry(len).or_default().push(adapter_idx);
}
}
let mut terminal_batches = Vec::new();
let mut singletons = searchable.clone();
for (len, adapter_indices) in by_len {
if adapter_indices.len() >= 2 {
let patterns: Vec<Vec<u8>> = adapter_indices
.iter()
.map(|&idx| adapters[idx].seq.clone())
.collect();
for &adapter_idx in &adapter_indices {
singletons[adapter_idx] = false;
}
terminal_batches.push(TerminalBatch {
k_end: adapter_indices
.iter()
.map(|&idx| budgets[idx].k_end)
.max()
.unwrap_or(0),
adapter_indices,
encoded: encode_patterns(&patterns),
len,
});
}
}
let mut end_seeds: BTreeMap<Vec<u8>, Vec<usize>> = BTreeMap::new();
let mut end_reach = 0;
for (adapter_idx, adapter) in adapters.iter().enumerate() {
let Budget { len, k_end, .. } = budgets[adapter_idx];
if !searchable[adapter_idx] || is_construct(adapter) {
continue;
}
end_reach = end_reach.max(len + k_end);
let pattern = adapter.seq.to_ascii_uppercase();
for strand in [pattern.clone(), reverse_complement(&pattern)] {
for kmer in strand.windows(END_SEED_LEN) {
let Some(expansions) = expand_iupac(kmer) else {
continue;
};
for seed in expansions {
let owners = end_seeds.entry(seed).or_default();
if owners.last() != Some(&adapter_idx) {
owners.push(adapter_idx);
}
}
}
}
}
let end_seeds = SeedTable::new(end_seeds);
Self {
seeds,
budgets,
plain,
unfiltered,
terminal_batches,
singletons,
end_seeds,
end_reach,
panel_gates: adapters.iter().map(bounds_barcode).collect(),
split_classes,
opens: senses.iter().map(|sense| sense == &Some(true)).collect(),
whole_primers: vec![None; adapters.len()],
paired,
}
}
pub(super) fn for_config(cfg: &AdapterConfig) -> Self {
let mut index = Self::new(&cfg.adapters, cfg.error_rate, cfg.end_size, cfg.split);
if cfg.amplicon {
for (adapter_idx, adapter) in cfg.adapters.iter().enumerate() {
if !index.paired[adapter_idx] {
continue;
}
index.whole_primers[adapter_idx] = marker_primer_of(&adapter.seq, cfg.error_rate)
.map(|(primer, opens)| {
let seq = if opens {
primer.to_vec()
} else {
reverse_complement(primer)
};
let k_mid = Budget::new(&seq, cfg.error_rate, cfg.end_size).k_mid;
WholePrimer { seq, k_mid }
});
}
}
index
}
pub(super) fn end_candidates(
&self,
window: &[u8],
ws: usize,
we: usize,
end_size: usize,
head: &mut Vec<bool>,
tail: &mut Vec<bool>,
) {
let adapters = self.budgets.len();
head.clear();
head.resize(adapters, false);
tail.clear();
tail.resize(adapters, false);
let Some(table) = &self.end_seeds else {
return;
};
let n = we - ws;
let reach = (end_size + self.end_reach).min(n);
table.scan(&window[ws..ws + reach], |adapter_idx, _| {
head[adapter_idx] = true
});
table.scan(&window[we - reach..we], |adapter_idx, _| {
tail[adapter_idx] = true
});
}
pub(super) fn candidate_windows(&self, text: &[u8], windows: &mut Vec<(usize, usize, usize)>) {
windows.clear();
for (adapter_idx, &whole) in self.unfiltered.iter().enumerate() {
if whole {
windows.push((adapter_idx, 0, text.len()));
}
}
if let Some(table) = &self.seeds {
table.scan(text, |adapter_idx, (start, end)| {
let Budget { len, k_end, .. } = self.budgets[adapter_idx];
let radius = len + k_end;
windows.push((
adapter_idx,
start.saturating_sub(radius),
end.saturating_add(radius).min(text.len()),
));
});
}
windows.sort_unstable();
let mut merged = 0;
for i in 0..windows.len() {
let (adapter_idx, start, end) = windows[i];
if merged > 0 && windows[merged - 1].0 == adapter_idx && start <= windows[merged - 1].2
{
windows[merged - 1].2 = windows[merged - 1].2.max(end);
} else {
windows[merged] = (adapter_idx, start, end);
merged += 1;
}
}
windows.truncate(merged);
}
}
pub(super) const MAX_WINDOW_COVERAGE: f64 = 0.25;
fn window_coverage(forward: &[Vec<u8>], reverse: &[Vec<u8>], budget: &Budget) -> f64 {
let rate: f64 = forward
.iter()
.chain(reverse)
.map(|seed| 0.25f64.powi(seed.len() as i32))
.sum();
rate * (2 * (budget.len + budget.k_end)) as f64
}
pub(super) const MAX_SEED_PREFIX_LEN: usize = 10;
#[derive(Debug, Clone)]
pub(super) struct SeedTable {
pub(super) prefix: usize,
pub(super) slots: Vec<u16>,
pub(super) lists: Vec<Vec<(usize, Vec<u8>)>>,
}
impl SeedTable {
pub(super) fn new(seeds: BTreeMap<Vec<u8>, Vec<usize>>) -> Option<Self> {
let code_of = |seed: &[u8], prefix: usize| {
seed[..prefix].iter().fold(0usize, |code, &b| {
(code << 2) | usize::from(BASE_CODE[usize::from(b)])
})
};
const SLOT_PREFIX_FLOOR: usize = 7;
let longest = seeds.keys().map(Vec::len).min()?.min(MAX_SEED_PREFIX_LEN);
let prefix = (SLOT_PREFIX_FLOOR.min(longest)..=longest)
.rev()
.find(|&prefix| {
let mut seen = vec![false; 1 << (2 * prefix)];
let distinct = seeds
.keys()
.filter(|seed| !std::mem::replace(&mut seen[code_of(seed, prefix)], true))
.count();
distinct <= usize::from(u16::MAX)
})
.unwrap_or(longest.min(SLOT_PREFIX_FLOOR));
let mut slots = vec![0u16; 1 << (2 * prefix)];
let mut lists: Vec<Vec<(usize, Vec<u8>)>> = Vec::new();
for (seed, owners) in seeds {
let code = code_of(&seed, prefix);
if slots[code] == 0 {
lists.push(Vec::new());
slots[code] = u16::try_from(lists.len()).expect("The prefix bounds the slot count");
}
let list = &mut lists[usize::from(slots[code]) - 1];
list.extend(owners.into_iter().map(|adapter| (adapter, seed.clone())));
}
Some(SeedTable {
prefix,
slots,
lists,
})
}
pub(super) fn scan(&self, text: &[u8], mut hit: impl FnMut(usize, (usize, usize))) {
let prefix = self.prefix;
if text.len() < prefix {
return;
}
let mask = (1usize << (2 * prefix)) - 1;
let slots = &self.slots[..=mask];
let mut code = text[..prefix - 1].iter().fold(0usize, |code, &b| {
(code << 2) | usize::from(BASE_CODE[usize::from(b)])
});
for (i, &b) in text[prefix - 1..].iter().enumerate() {
code = ((code << 2) | usize::from(BASE_CODE[usize::from(b)])) & mask;
let slot = slots[code];
if slot != 0 {
for (adapter, seed) in &self.lists[usize::from(slot) - 1] {
if text[i..].starts_with(seed) {
hit(*adapter, (i, i + seed.len()));
}
}
}
}
}
}
pub(super) const BASE_CODE: [u8; 256] = {
let mut t = [0u8; 256];
t[b'C' as usize] = 1;
t[b'G' as usize] = 2;
t[b'T' as usize] = 3;
t
};
pub(super) fn partition_seeds(pattern: &[u8], max_edits: usize) -> Option<Vec<Vec<u8>>> {
let parts = (max_edits + 1).min(pattern.len());
let mut seeds = Vec::new();
for i in 0..parts {
let start = i * pattern.len() / parts;
let end = (i + 1) * pattern.len() / parts;
seeds.extend(expand_iupac(&pattern[start..end])?);
}
Some(seeds)
}
pub(super) fn expand_iupac(piece: &[u8]) -> Option<Vec<Vec<u8>>> {
let mut expansions: Vec<Vec<u8>> = vec![Vec::with_capacity(piece.len())];
for &code in piece {
let bases = iupac_bases(code)?;
if expansions.len() * bases.len() > MAX_SEED_EXPANSIONS {
return None;
}
let mut next = Vec::with_capacity(expansions.len() * bases.len());
for prefix in &expansions {
for &base in bases {
let mut expansion = prefix.clone();
expansion.push(base);
next.push(expansion);
}
}
expansions = next;
}
Some(expansions)
}
pub(super) const END_SEED_LEN: usize = 9;