use crate::adapter::search::{AmbiguousSearcher, hits, is_plain_acgt, new_ambiguous_searcher};
use crate::adapter::{Adapter, AdapterConfig, MIN_PATTERN_LEN, Role, edit_budget};
mod assemble;
mod boundary;
mod consensus;
mod degenerate;
mod kmer;
mod layers;
mod linkage;
mod support;
use assemble::*;
use boundary::*;
use consensus::*;
use degenerate::*;
use kmer::*;
use layers::*;
use linkage::*;
use support::*;
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum End {
Five,
Three,
}
const KMER_K: usize = 16;
const TOP_KMERS: usize = 500;
const WINDOW_LEN: usize = 100;
const KEEP_SUPPORT: f64 = 0.01;
const MIN_SUPPORT_WINDOWS: usize = 20;
const RECOUNT_WINDOWS: usize = 4000;
const BOUNDARY_SUPPORT: f64 = 0.45;
const START_K: usize = 11;
const LMAX: usize = 100;
const MAX_BOUNDARY_ANCHORS: usize = 8;
const VARIABLE_MEMBER_SUPPORT: f64 = 0.001;
const MAX_ADAPTERS_PER_END: usize = 128;
const MAX_LAYERS: usize = 8;
const MIRROR_WINDOW: usize = 300;
const MIRROR_SEGMENT: usize = KMER_K;
const SYMMETRY_TOLERANCE: usize = 35;
const MIRROR_ERROR_RATE: f64 = 0.5;
const MIRROR_STEP: usize = 4;
const MIRROR_SUPPORT_DIVISOR: usize = 8;
const ANCHORED_PERCENT: usize = 60;
const ANCHOR_SLACK: usize = 50;
const ADAPTER_FLUSH: usize = 20;
const SHARED_END_MIN: usize = 12;
const FAMILY_OVERLAP_PERCENT: usize = 60;
const VARIANT_OVERLAP_PERCENT: usize = 80;
const NAME_IDENTITY_MIN: f32 = 85.0;
#[derive(Debug, Clone)]
pub struct InferredAdapter {
pub adapter: Adapter,
pub assembled_seq: Vec<u8>,
pub support: f64,
pub name_hits: Vec<(String, f32)>,
pub layer: usize,
}
impl InferredAdapter {
pub fn uncertain_bases(&self) -> usize {
self.assembled_seq
.len()
.saturating_sub(self.adapter.seq.len())
}
}
type Ranked = (Vec<u8>, f64, Vec<bool>, usize, bool, End, u64);
pub fn discover(sample: &[&[u8]], base: &AdapterConfig) -> Vec<InferredAdapter> {
let mut bounds = Boundaries::new(sample);
let known: Vec<Vec<u8>> = base
.adapters
.iter()
.filter(|a| !crate::adapter::is_construct(a))
.map(|a| a.seq.to_ascii_uppercase())
.collect();
if !known.is_empty() {
let mut active = vec![true; sample.len()];
for _ in 0..MAX_LAYERS {
active = advance_boundaries(
sample,
&mut bounds,
&known,
base.error_rate,
&active,
true,
true,
);
if active.is_empty() {
break;
}
}
}
let physical = Boundaries::new(sample);
let (five_p, three_p) = layer_windows(sample, &physical, MIRROR_WINDOW);
let five_phys: Vec<&[u8]> = stride_sample(
&five_p.iter().map(|(_, w)| *w).collect::<Vec<_>>(),
RECOUNT_WINDOWS,
);
let three_phys: Vec<&[u8]> = stride_sample(
&three_p.iter().map(|(_, w)| *w).collect::<Vec<_>>(),
RECOUNT_WINDOWS,
);
let mut searcher = crate::adapter::search::new_searcher_fwd();
let mut strand_searcher = crate::adapter::search::new_searcher_fwd();
let mut distinct: Vec<(Vec<u8>, f64, usize, bool, bool)> = Vec::new();
let mut open = [true, true];
let mut strand_words: Vec<Vec<u8>> = Vec::new();
let mut insert_bounds: [Vec<Vec<u8>>; 2] = [
crate::adapter::catalog::MARKER_PRIMERS
.iter()
.map(|p| p.to_vec())
.collect(),
crate::adapter::catalog::MARKER_PRIMERS
.iter()
.map(|p| crate::adapter::reverse_complement(p))
.collect(),
];
for layer in 0..MAX_LAYERS {
let (mut five_w, mut three_w) = layer_windows(sample, &bounds, 2 * WINDOW_LEN);
if !open[0] {
five_w.clear();
}
if !open[1] {
three_w.clear();
}
if layer == 0 && !known.is_empty() {
for (index, (end, windows)) in [(End::Five, &mut five_w), (End::Three, &mut three_w)]
.into_iter()
.enumerate()
{
let moved = |i: usize| match end {
End::Five => bounds.five[i] > 0,
End::Three => bounds.three[i] < sample[i].len(),
};
let texts: Vec<&[u8]> = windows
.iter()
.filter(|(i, _)| moved(*i))
.map(|(_, w)| *w)
.collect();
let texts = stride_sample(&texts, RECOUNT_WINDOWS);
if template_at_boundary(&texts, end) {
tracing::debug!(layer = layer + 1, ?end, "Template begins at the boundary");
windows.clear();
open[index] = false;
}
}
}
let five_texts: Vec<&[u8]> = five_w.iter().map(|(_, w)| *w).collect();
let three_texts: Vec<&[u8]> = three_w.iter().map(|(_, w)| *w).collect();
let five_sample = stride_sample(&five_texts, RECOUNT_WINDOWS);
let three_sample = stride_sample(&three_texts, RECOUNT_WINDOWS);
let mut five = assemble(&five_texts, &three_phys, base, End::Five, layer == 0);
let mut three = assemble(&three_texts, &five_phys, base, End::Three, layer == 0);
let mut layer_bounds = insert_bounds.clone();
for (own, other, index) in [(&five, &three, 0), (&three, &five, 1)] {
layer_bounds[index].extend(
own.iter()
.filter(|c| c.2)
.map(|c| c.0.clone())
.chain(
other
.iter()
.filter(|c| c.2)
.map(|c| crate::adapter::reverse_complement(&c.0)),
)
.collect::<Vec<_>>(),
);
}
end_at_insert_boundaries(&mut five, &layer_bounds[0], End::Five);
end_at_insert_boundaries(&mut three, &layer_bounds[1], End::Three);
strip_shared_ends(&mut five, base.error_rate);
strip_shared_ends(&mut three, base.error_rate);
let (five, five_variable) = with_variable_layer(
&mut searcher,
five,
&five_texts,
&five_sample,
End::Five,
base.error_rate,
);
let (three, three_variable) = with_variable_layer(
&mut searcher,
three,
&three_texts,
&three_sample,
End::Three,
base.error_rate,
);
let variable: Vec<Vec<u8>> = five_variable.into_iter().chain(three_variable).collect();
let background = background_windows(sample, &bounds, WINDOW_LEN);
let background = stride_sample(&background, RECOUNT_WINDOWS);
let mut inserts: Vec<Vec<u8>> = Vec::new();
let mut next_words: Vec<Vec<u8>> = Vec::new();
let cut: Vec<(Vec<u8>, f64, bool, u64, End)> = five
.into_iter()
.map(|c| (c, End::Five))
.chain(three.into_iter().map(|c| (c, End::Three)))
.filter(|((seq, support, _, _, _, _), _)| {
seq.len() >= MIN_PATTERN_LEN && (*support >= KEEP_SUPPORT || variable.contains(seq))
})
.filter_map(
|((seq, support, boundary, weight, unbounded, divided), end)| {
let strand = strand_words.iter().any(|word| {
!hits(
&mut strand_searcher,
word,
&seq,
edit_budget(base.error_rate, word.len()),
)
.is_empty()
});
if !divided.is_empty() || strand {
next_words.extend(divided);
return Some((seq, support, boundary, weight, end));
}
let (own, opposite) = match end {
End::Five => (&five_phys, &three_phys),
End::Three => (&three_phys, &five_phys),
};
let (cut, insert) = symmetry_cut(&seq, end, own, opposite, base.error_rate);
if insert.len() >= MIN_PATTERN_LEN {
inserts.push(crate::adapter::reverse_complement(&insert));
inserts.push(insert);
}
let cut = cut?;
if unbounded && cut.len() == seq.len() {
return None;
}
Some((cut, support, boundary, weight, end))
},
)
.collect();
strand_words.extend(next_words);
let mut candidates: Vec<(Vec<u8>, f64, u32, bool, u64, End)> = cut
.into_iter()
.filter(|(seq, _, _, _, _)| {
!inserts
.iter()
.any(|insert| same_family(seq, insert, base.error_rate))
})
.filter_map(|(seq, support, boundary, weight, end)| {
let count = windows_containing(
&mut searcher,
&seq,
&background,
edit_budget(base.error_rate, seq.len()),
);
if !background.is_empty() && count as f64 * 4.0 >= support * background.len() as f64
{
return None;
}
let exact = windows_containing(&mut searcher, &seq, &five_sample, 0)
+ windows_containing(&mut searcher, &seq, &three_sample, 0);
tracing::debug!(sequence = %String::from_utf8_lossy(&seq), exact, "Layer candidate");
Some((seq, support, exact, boundary, weight, end))
})
.collect();
candidates.sort_by(|a, b| {
b.3.cmp(&a.3)
.then_with(|| {
if a.3 && b.3 {
b.2.cmp(&a.2)
} else {
std::cmp::Ordering::Equal
}
})
.then(b.4.cmp(&a.4))
.then(b.2.cmp(&a.2))
.then(b.1.total_cmp(&a.1))
.then(b.0.len().cmp(&a.0.len()))
.then(a.0.cmp(&b.0))
});
let layer_candidates: Vec<(Vec<u8>, f64, u64, End)> = candidates
.iter()
.map(|(seq, support, _, _, weight, end)| (seq.clone(), *support, *weight, *end))
.collect();
let mut merged: Vec<(Vec<u8>, f64, u64, bool, End)> = Vec::new();
for (seq, support, _, boundary, weight, end) in candidates {
let matched = weight;
if distinct.iter().any(|(other, _, _, _, _)| {
other.len() <= seq.len() + edit_budget(base.error_rate, seq.len())
&& same_adapter(&seq, other, base.error_rate)
}) {
continue;
} else if let Some((other, previous, best, _, _)) =
merged.iter_mut().find(|(other, previous, _, _, _)| {
support < *previous * f64::from(RUN_JUMP)
&& *previous < support * f64::from(RUN_JUMP)
&& fragment_of(&seq, other, base.error_rate)
})
{
if matched > *best {
*other = seq;
*best = matched;
*previous = support;
}
} else {
merged.push((seq, support, matched, boundary, end));
}
}
let layer_texts: Vec<&[u8]> = five_sample.iter().chain(&three_sample).copied().collect();
let mut ranked: Vec<Ranked> = merged
.into_iter()
.map(|(seq, support, matched, boundary, end)| {
let k = edit_budget(base.error_rate, seq.len());
let mut windows = windows_covered(&mut searcher, &seq, &layer_texts, k);
let mirror = crate::adapter::reverse_complement(&seq);
for (window, hit) in
windows
.iter_mut()
.zip(windows_covered(&mut searcher, &mirror, &layer_texts, k))
{
*window |= hit;
}
let own = windows.iter().filter(|&&w| w).count();
(seq, support, windows, own, boundary, end, matched)
})
.collect();
ranked.sort_by(|a, b| {
b.6.cmp(&a.6)
.then(b.3.cmp(&a.3))
.then(b.0.len().cmp(&a.0.len()))
.then(a.0.cmp(&b.0))
});
let mut accepted: Vec<Vec<u8>> = Vec::new();
let mut accepted_windows: Vec<Vec<bool>> = Vec::new();
let mut accepted_ends: Vec<End> = Vec::new();
let mut own_forms: Vec<(Vec<u8>, f64, End)> = Vec::new();
for (seq, support, windows, own, boundary, end, matched) in ranked {
let member = variable
.iter()
.any(|v| same_adapter(&seq, v, base.error_rate));
let shared = accepted_windows
.iter()
.map(|other| {
windows
.iter()
.zip(other)
.filter(|(a, b)| **a && **b)
.count()
})
.max()
.unwrap_or(0);
let variant = !member && shared * 100 >= own * VARIANT_OVERLAP_PERCENT;
tracing::debug!(sequence = %String::from_utf8_lossy(&seq), matched, own, shared, variant, "Ranked candidate");
if variant {
continue;
}
let flush = layer == 0
&& known.is_empty()
&& [(End::Five, &five_phys), (End::Three, &three_phys)]
.iter()
.any(|(end, phys)| {
outer_depth(&mut searcher, &seq, phys, *end, base.error_rate)
<= ADAPTER_FLUSH
});
if boundary {
let index = usize::from(end == End::Three);
open[index] = false;
insert_bounds[index].push(seq.clone());
insert_bounds[1 - index].push(crate::adapter::reverse_complement(&seq));
}
accepted_ends.push(end);
accepted.push(seq.clone());
if !member {
accepted_windows.push(windows);
let other_windows = match end {
End::Five => &three_sample,
End::Three => &five_sample,
};
if let Some(form) =
other_end_form(&seq, end, &layer_candidates, other_windows, base.error_rate)
&& !distinct.iter().any(|(other, _, _, _, _)| *other == form.0)
{
tracing::debug!(sequence = %String::from_utf8_lossy(&form.0), "Other end form");
distinct.push((form.0, form.1, layer, flush, false));
}
if let Some(own) =
untrimmed_other_end(&seq, end, &layer_candidates, other_windows, base)
{
own_forms.push(own);
}
}
distinct.push((seq, support, layer, flush, member));
}
for (seq, support, end) in own_forms {
if accepted.contains(&seq) || distinct.iter().any(|(other, _, _, _, _)| *other == seq) {
continue;
}
tracing::debug!(sequence = %String::from_utf8_lossy(&seq), "Other end layer");
let flush = layer == 0
&& known.is_empty()
&& [(End::Five, &five_phys), (End::Three, &three_phys)]
.iter()
.any(|(end, phys)| {
outer_depth(&mut searcher, &seq, phys, *end, base.error_rate)
<= ADAPTER_FLUSH
});
accepted_ends.push(end);
accepted.push(seq.clone());
distinct.push((seq, support, layer, flush, false));
}
tracing::debug!(
layer = layer + 1,
accepted = accepted.len(),
"Discovery layer"
);
for (index, end) in [End::Five, End::Three].into_iter().enumerate() {
if !accepted_ends.contains(&end) {
open[index] = false;
}
}
if accepted.is_empty()
|| advance_boundaries(
sample,
&mut bounds,
&accepted,
base.error_rate,
&vec![true; sample.len()],
false,
layer == 0,
)
.is_empty()
{
break;
}
}
let oriented: Vec<Vec<u8>> = five_phys
.iter()
.map(|w| w.to_ascii_uppercase())
.chain(
three_phys
.iter()
.map(|w| crate::adapter::reverse_complement(&w.to_ascii_uppercase())),
)
.collect();
let oriented: Vec<&[u8]> = oriented.iter().map(Vec::as_slice).collect();
let composition = base_composition(&oriented);
let known_layers = base
.adapters
.iter()
.filter(|a| a.role != Role::Barcode && !crate::adapter::is_construct(a))
.map(|a| (a.seq.to_ascii_uppercase(), 0));
let discovered_layers = distinct
.iter()
.filter(|(_, _, _, _, member)| !member)
.map(|(seq, _, layer, _, _)| (seq.clone(), *layer + 1));
let preceding: Vec<(Vec<u8>, usize)> = known_layers.chain(discovered_layers).collect();
let mut tags: Vec<(Vec<u8>, f64, usize, bool, bool)> = Vec::new();
for (seq, layer) in preceding {
for pattern in [seq.clone(), crate::adapter::reverse_complement(&seq)] {
if let Some((tag, present)) = degenerate_layer(
&mut searcher,
&pattern,
&oriented,
composition,
base.error_rate,
) && !tags.iter().any(|(other, _, _, _, _)| {
*other == tag || *other == crate::adapter::reverse_complement(&tag)
}) && !known
.iter()
.filter(|k| !is_plain_acgt(k))
.any(|k| same_adapter(&tag, k, base.error_rate))
{
tracing::debug!(sequence = %String::from_utf8_lossy(&tag), "Degenerate layer");
tags.push((
tag,
present as f64 / oriented.len() as f64,
layer,
false,
false,
));
}
}
}
let tag_seqs: Vec<Vec<u8>> = tags.iter().map(|t| t.0.clone()).collect();
distinct.extend(tags);
let refs = crate::adapter::preset::preset(crate::adapter::preset::Kit::ALL);
let name_refs: Vec<Adapter> = refs
.into_iter()
.chain(base.adapters.iter().cloned())
.collect();
let degenerate_refs: Vec<Adapter> = name_refs
.iter()
.filter(|r| !is_plain_acgt(&r.seq))
.cloned()
.collect();
distinct.sort_by(|a, b| a.2.cmp(&b.2).then(b.1.total_cmp(&a.1)).then(a.0.cmp(&b.0)));
distinct
.into_iter()
.enumerate()
.map(|(i, (seq, support, layer, flush, member))| {
let tag = tag_seqs.contains(&seq);
let refs = if tag { °enerate_refs } else { &name_refs };
let name_hits = name_against(&seq, refs, base.error_rate);
let role = if flush && !crate::adapter::matches_marker_primer(&seq, base.error_rate) {
Role::Adapter
} else if member {
Role::Barcode
} else {
Role::Primer
};
InferredAdapter {
adapter: Adapter {
name: format!("inferred_{}", i + 1),
seq: if tag {
seq.clone()
} else {
crate::adapter::with_marker_codes(&seq, base.error_rate)
},
role,
},
assembled_seq: seq,
support,
name_hits,
layer,
}
})
.collect()
}
#[cfg(test)]
mod tests;