use super::*;
pub(super) fn encode_kmer(bytes: &[u8]) -> Option<u64> {
if bytes.len() > 32 {
return None;
}
let mut code = 0u64;
for &b in bytes {
let two = match b {
b'A' => 0,
b'C' => 1,
b'G' => 2,
b'T' => 3,
_ => return None,
};
code = (code << 2) | two;
}
Some(code)
}
pub(super) fn decode_kmer(mut code: u64, k: usize) -> Vec<u8> {
let mut out = vec![0u8; k];
for i in (0..k).rev() {
out[i] = match code & 0b11 {
0 => b'A',
1 => b'C',
2 => b'G',
_ => b'T',
};
code >>= 2;
}
out
}
#[cfg(test)]
pub(super) fn end_windows<'a>(sample: &[&'a [u8]], w: usize) -> (Vec<&'a [u8]>, Vec<&'a [u8]>) {
let (five, three) = layer_windows(sample, &Boundaries::new(sample), w);
(
five.into_iter().map(|(_, window)| window).collect(),
three.into_iter().map(|(_, window)| window).collect(),
)
}
#[derive(Default, Clone, Copy)]
pub(super) struct KmerHasher(u64);
impl std::hash::Hasher for KmerHasher {
fn finish(&self) -> u64 {
self.0
}
fn write(&mut self, bytes: &[u8]) {
for &byte in bytes {
self.0 = (self.0 ^ u64::from(byte)).wrapping_mul(0x0100_0000_01b3);
}
}
fn write_u64(&mut self, code: u64) {
let mixed = code.wrapping_mul(0x9e37_79b9_7f4a_7c15);
self.0 = mixed ^ (mixed >> 32);
}
}
pub(super) type KmerMap<V> =
std::collections::HashMap<u64, V, std::hash::BuildHasherDefault<KmerHasher>>;
pub(super) fn is_low_complexity(kmer: &[u8]) -> bool {
(1..=8.min(kmer.len() / 2))
.any(|period| kmer.iter().enumerate().all(|(i, &b)| b == kmer[i % period]))
}
pub(super) fn is_repetitive(seq: &[u8]) -> bool {
(1..=8.min(seq.len() / 2).min(seq.len().saturating_sub(10))).any(|period| {
let matches = seq
.iter()
.zip(&seq[period..])
.filter(|(a, b)| a == b)
.count();
matches * 100 >= (seq.len() - period) * 65
})
}
pub(super) fn top_kmers(windows: &[&[u8]], k: usize, top: usize) -> Vec<(u64, u32)> {
let mut counts: KmerMap<(u32, usize)> =
KmerMap::with_capacity_and_hasher(windows.len() * 8, Default::default());
assert!((1..=32).contains(&k));
let mask = u64::MAX >> (64 - 2 * k);
for (window_index, &wnd) in windows.iter().enumerate() {
let (mut code, mut valid) = (0, 0);
for &base in wnd {
if let Some(bits) = encode_kmer(&[base]) {
code = ((code << 2) | bits) & mask;
valid += 1;
if valid >= k {
let entry = counts.entry(code).or_insert((0, usize::MAX));
if entry.1 != window_index {
entry.0 += 1;
entry.1 = window_index;
}
}
} else {
code = 0;
valid = 0;
}
}
}
let mut ranked: Vec<(u64, u32)> = counts
.into_iter()
.map(|(code, (count, _))| (code, count))
.filter(|&(code, _)| {
if k >= 4 {
!(1..=8.min(k / 2))
.any(|period| code & (mask >> (2 * period)) == code >> (2 * period))
} else {
!is_low_complexity(&decode_kmer(code, k))
}
})
.collect();
let order = |a: &(u64, u32), b: &(u64, u32)| b.1.cmp(&a.1).then(a.0.cmp(&b.0));
if ranked.len() > top {
ranked.select_nth_unstable_by(top, order);
ranked.truncate(top);
}
ranked.sort_unstable_by(order);
ranked
}
pub(super) fn bounded_heaviest_path(
nodes: &[(u64, u32)],
k: usize,
lmax: usize,
) -> Option<(Vec<u8>, Vec<u32>, u64)> {
use std::collections::HashMap;
if nodes.is_empty() {
return None;
}
let n = nodes.len();
let suffix_mask: u64 = if k >= 1 {
(1u64 << (2 * (k - 1))) - 1
} else {
0
};
let mut by_prefix: HashMap<u64, Vec<usize>> = HashMap::new();
let mut by_suffix: HashMap<u64, Vec<usize>> = HashMap::new();
for (i, &(code, _)) in nodes.iter().enumerate() {
by_prefix.entry(code >> 2).or_default().push(i);
by_suffix.entry(code & suffix_mask).or_default().push(i);
}
let weight_desc_code_asc = |&a: &usize, &b: &usize| {
nodes[a]
.1
.cmp(&nodes[b].1)
.then(nodes[b].0.cmp(&nodes[a].0))
};
let pick = |cands: Option<&Vec<usize>>, visited: &[bool]| -> Option<usize> {
cands?
.iter()
.copied()
.filter(|&i| !visited[i])
.max_by(weight_desc_code_asc)
};
let seed = (0..n).max_by(weight_desc_code_asc).unwrap();
let mut visited = vec![false; n];
visited[seed] = true;
let mut forward: Vec<usize> = Vec::new();
let mut cur = seed;
while k + forward.len() < lmax {
match pick(by_prefix.get(&(nodes[cur].0 & suffix_mask)), &visited) {
Some(v) => {
visited[v] = true;
forward.push(v);
cur = v;
},
None => break,
}
}
let mut backward: Vec<usize> = Vec::new();
cur = seed;
while k + forward.len() + backward.len() < lmax {
match pick(by_suffix.get(&(nodes[cur].0 >> 2)), &visited) {
Some(u) => {
visited[u] = true;
backward.push(u);
cur = u;
},
None => break,
}
}
let mut chain: Vec<usize> = backward.iter().rev().copied().collect();
chain.push(seed);
chain.extend(forward.iter().copied());
let mut cons = decode_kmer(nodes[chain[0]].0, k);
let mut profile: Vec<u32> = vec![nodes[chain[0]].1; k];
let mut weight: u64 = nodes[chain[0]].1 as u64;
for &idx in &chain[1..] {
cons.push(*decode_kmer(nodes[idx].0, k).last().unwrap());
profile.push(nodes[idx].1);
weight += nodes[idx].1 as u64;
}
Some((cons, profile, weight))
}
pub(super) fn peel_paths(
mut nodes: Vec<(u64, u32)>,
k: usize,
end: End,
) -> Vec<(Vec<u8>, Vec<u32>)> {
let mut out = Vec::new();
while out.len() < MAX_ADAPTERS_PER_END {
let Some((cons, _, _)) = bounded_heaviest_path(&nodes, k, LMAX) else {
break;
};
let current: KmerMap<u32> = nodes.iter().copied().collect();
let weights: Vec<u32> = cons
.windows(k)
.map(|w| {
encode_kmer(w)
.and_then(|code| current.get(&code).copied())
.unwrap_or(0)
})
.collect();
let (lo, hi, _) = supported_span(&weights, end);
let mut used: std::collections::HashSet<u64> = cons[lo..hi.min(cons.len())]
.windows(k)
.filter_map(encode_kmer)
.collect();
if used.is_empty() {
used = cons.windows(k).filter_map(encode_kmer).collect();
}
nodes.retain(|(code, _)| !used.contains(code));
out.push((cons, weights));
if nodes.is_empty() {
break;
}
}
out
}