use super::*;
pub(crate) fn edit_budget(rate: f64, len: usize) -> usize {
(rate * len as f64 + 1e-9).floor() as usize
}
pub(super) const INTERIOR_CHANCE_HITS_PER_READ: f64 = 1e-4;
pub(super) const TERMINAL_CHANCE_HITS_PER_READ: f64 = 0.1;
pub(super) const INTERIOR_CLASS_BITS: u32 = 12;
pub(super) const INTERIOR_CLASSES: usize = 20;
pub(super) fn interior_class(read_len: usize) -> usize {
let bits = usize::BITS - read_len.leading_zeros();
(bits.saturating_sub(INTERIOR_CLASS_BITS) as usize).min(INTERIOR_CLASSES - 1)
}
pub(super) fn interior_positions(class: usize) -> f64 {
2.0 * 2f64.powi(INTERIOR_CLASS_BITS as i32 + class as i32)
}
pub(super) fn chance_cumulative(pattern: &[u8], max_edits: usize) -> Vec<f64> {
let mut previous = vec![1.0; max_edits + 1];
for &base in pattern {
let p = search::iupac_degeneracy(base).unwrap_or(4) as f64 / 4.0;
let mut current = vec![0.0; max_edits + 1];
current[0] = p * previous[0];
for k in 1..=max_edits {
current[k] = p * previous[k] + (2.0 - p) * previous[k - 1] + current[k - 1];
}
previous = current;
}
let mut cumulative = previous;
for k in 1..=max_edits {
cumulative[k] += cumulative[k - 1];
}
cumulative
}
pub(super) fn family_budgets(
adapters: &[Adapter],
included: &[bool],
caps: &[usize],
positions: f64,
bound: f64,
) -> Vec<usize> {
let members = distinct_groups(adapters, included);
let mut edits: Vec<usize> = members
.iter()
.map(|group| group.iter().map(|&i| caps[i]).min().unwrap_or(0))
.collect();
let chance: Vec<Vec<f64>> = members
.iter()
.zip(&edits)
.map(|(group, &k)| {
chance_cumulative(&adapters[group[0]].seq, k)
.into_iter()
.map(|probability| probability * positions)
.collect()
})
.collect();
let excess = |g: usize, k: usize| chance[g][k] - chance[g][0];
loop {
let total: f64 = (0..members.len()).map(|g| excess(g, edits[g])).sum();
if total <= bound {
break;
}
let top = (0..members.len())
.filter(|&g| edits[g] > 0)
.map(|g| chance[g][edits[g]])
.fold(0.0, f64::max);
for g in 0..members.len() {
if edits[g] > 0 && chance[g][edits[g]] >= top * (1.0 - 1e-9) {
edits[g] -= 1;
}
}
}
spread(&members, &edits, caps)
}
fn distinct_groups(adapters: &[Adapter], included: &[bool]) -> Vec<Vec<usize>> {
let mut groups: BTreeMap<Vec<u8>, Vec<usize>> = BTreeMap::new();
for (adapter_idx, adapter) in adapters.iter().enumerate() {
if included[adapter_idx] {
let forward = adapter.seq.to_ascii_uppercase();
let reverse = reverse_complement(&forward);
groups
.entry(forward.min(reverse))
.or_default()
.push(adapter_idx);
}
}
groups.into_values().collect()
}
fn spread(members: &[Vec<usize>], edits: &[usize], caps: &[usize]) -> Vec<usize> {
let mut out = caps.to_vec();
for (group, &k) in members.iter().zip(edits) {
for &adapter_idx in group {
out[adapter_idx] = k;
}
}
out
}
pub(super) const PAIR_OFFSETS: usize = 2 * FLANK_SLACK + 1;
pub(super) fn pair_budgets(
adapters: &[Adapter],
included: &[bool],
caps: &[usize],
positions: f64,
bound: f64,
) -> Vec<usize> {
let members = distinct_groups(adapters, included);
let mut edits: Vec<usize> = members
.iter()
.map(|group| group.iter().map(|&i| caps[i]).min().unwrap_or(0))
.collect();
let chance: Vec<Vec<f64>> = members
.iter()
.zip(&edits)
.map(|(group, &k)| chance_cumulative(&adapters[group[0]].seq, k))
.collect();
let scale = positions * PAIR_OFFSETS as f64;
loop {
let rate: f64 = (0..members.len()).map(|g| chance[g][edits[g]]).sum();
if rate * rate * scale <= bound {
break;
}
let top = (0..members.len())
.filter(|&g| edits[g] > 0)
.map(|g| chance[g][edits[g]])
.fold(0.0, f64::max);
if top == 0.0 {
break;
}
for g in 0..members.len() {
if edits[g] > 0 && chance[g][edits[g]] >= top * (1.0 - 1e-9) {
edits[g] -= 1;
}
}
}
spread(&members, &edits, caps)
}
#[derive(Debug, Clone, Copy)]
pub(super) struct Budget {
pub(super) len: usize,
pub(super) k_end: usize,
pub(super) k_far: usize,
pub(super) k_mid: [usize; INTERIOR_CLASSES],
pub(super) k_pair: [usize; INTERIOR_CLASSES],
}
impl Budget {
pub(super) fn new(pattern: &[u8], error_rate: f64, end_size: usize) -> Self {
let len = pattern.len();
let k_end = edit_budget(error_rate, len);
let cumulative = chance_cumulative(pattern, k_end);
let k_mid = std::array::from_fn(|class| {
let positions = interior_positions(class);
cumulative
.iter()
.take_while(|&&probability| {
probability * positions <= INTERIOR_CHANCE_HITS_PER_READ
})
.count()
.saturating_sub(1)
});
let positions = 4.0 * (end_size + 1) as f64;
let k_end = cumulative
.iter()
.take_while(|&&probability| probability * positions <= TERMINAL_CHANCE_HITS_PER_READ)
.count()
.saturating_sub(1)
.min(k_end);
Self {
len,
k_end,
k_far: k_end,
k_mid,
k_pair: [0; INTERIOR_CLASSES],
}
}
pub(super) fn interior(&self, read_len: usize) -> usize {
self.k_mid[interior_class(read_len)]
}
pub(super) fn interior_max(&self) -> usize {
self.k_mid[0]
}
pub(super) fn pair(&self, read_len: usize) -> usize {
self.k_pair[interior_class(read_len)]
}
}
pub(super) fn overhang_cost(alpha: f32, left: usize, right: usize) -> usize {
let side = |bases: usize| (bases as f32 * alpha).floor() as usize;
side(left) + side(right)
}
pub(super) fn partial_budget(rate: f64, overlap: usize) -> usize {
edit_budget(rate, overlap.saturating_sub(MIN_OVERLAP - 1))
}