use std::collections::HashMap;
use rayon::prelude::*;
use crate::alphabet::Alphabet;
use crate::create::{CreateOptions, from_matrix};
use crate::error::{Result, arg_err};
use crate::matrix::Matrix;
use crate::motif::{Motif, MotifType, Strand};
use crate::pvalue::with_threads;
use crate::shuffle::{ShuffleMethod, ShuffleOptions, shuffled_background};
const HAMMING_MISMATCH: u64 = 1;
const REFINE_PASSES: usize = 2;
const TOP_K_SEEDS: usize = 4;
const MAX_MOTIF_WIDTH: usize = 30;
const MIN_REFINE_HITS: u64 = 20;
const MIN_IC_BITS: f64 = 0.5;
const AMBIGUITY_SCORE: i32 = -10_000_000;
const MAX_CDF_SIZE: u64 = 2_097_152;
const MAX_SPACED_PAIRS: usize = 65_536;
const COMP4: [usize; 4] = [3, 2, 1, 0];
const fn char_table() -> [u8; 256] {
let mut t = [4u8; 256];
t[b'A' as usize] = 0;
t[b'a' as usize] = 0;
t[b'C' as usize] = 1;
t[b'c' as usize] = 1;
t[b'G' as usize] = 2;
t[b'g' as usize] = 2;
t[b'T' as usize] = 3;
t[b't' as usize] = 3;
t[b'U' as usize] = 3;
t[b'u' as usize] = 3;
t
}
const CHAR2IDX: [u8; 256] = char_table();
#[derive(Clone, Default)]
struct FMotif {
pwm: Vec<i32>,
pwm_rc: Vec<i32>,
probs: Vec<[f64; 4]>,
threshold: i32,
mn: i32,
mx: i32,
max_score: i32,
min_score: i32,
cdf_max: i32,
cdf_offset: i32,
cdf_size: u64,
size: usize,
nsites: u64,
}
impl FMotif {
fn init(&mut self, w: usize) {
*self = FMotif {
pwm: vec![0; w * 5],
pwm_rc: vec![0; w * 5],
probs: vec![[0.0; 4]; w],
size: w,
..Default::default()
};
for i in 0..w {
self.pwm[i * 5 + 4] = AMBIGUITY_SCORE;
self.pwm_rc[i * 5 + 4] = AMBIGUITY_SCORE;
}
}
fn score(&self, idx: usize, pos: usize) -> i32 {
self.pwm[idx + pos * 5]
}
}
fn calc_score_ns(prob: f64, bkg: f64, ns: u64, pc: u32) -> i32 {
let mut x = prob * ns as f64;
x += pc as f64 / 4.0;
x /= (ns + pc as u64) as f64;
if x <= 0.0 {
x = 1e-12;
}
((x / bkg).log2() * 1000.0) as i32
}
thread_local! {
static CDF_BUFFERS: std::cell::RefCell<(Vec<f64>, Vec<f64>)> =
const { std::cell::RefCell::new((Vec::new(), Vec::new())) };
}
fn fill_cdf(m: &FMotif, bkg: &[f64; 4], cdf: &mut Vec<f64>, tmp: &mut Vec<f64>) -> bool {
if m.cdf_size == 0 || m.cdf_size > MAX_CDF_SIZE {
return false;
}
let size = m.cdf_size as usize;
let cmax = m.cdf_max as usize;
cdf.clear();
cdf.resize(size, 1.0);
tmp.clear();
tmp.resize(size, 0.0);
for i in 0..m.size {
let max_step = i * cmax;
tmp.copy_from_slice(cdf);
let end = (max_step + cmax + 1).min(size);
cdf[..end].fill(0.0);
for (j, b) in bkg.iter().enumerate() {
let s = (m.score(j, i) - m.mn) as usize;
for (c, t) in cdf[s..=s + max_step].iter_mut().zip(tmp.iter()) {
*c += t * b;
}
}
}
let sum: f64 = cdf.iter().fold(0.0, |a, &b| a + b);
if (sum - 1.0).abs() > 0.0001 {
cdf.iter_mut().for_each(|v| *v /= sum);
}
for i in (0..size - 1).rev() {
cdf[i] += cdf[i + 1];
}
true
}
fn set_threshold_pval(m: &mut FMotif, cdf: &[f64], pval: f64) {
let threshold_i = cdf
.iter()
.position(|&c| c < pval)
.unwrap_or(m.cdf_size as usize) as i32;
m.threshold = threshold_i + m.mn * m.size as i32;
m.max_score = 0;
m.min_score = 0;
for i in 0..m.size {
let col: Vec<i32> = (0..4).map(|j| m.score(j, i)).collect();
m.max_score += *col.iter().max().unwrap();
m.min_score += *col.iter().min().unwrap();
}
let min_pval = cdf[(m.max_score - m.cdf_offset) as usize];
if min_pval / pval > 1.0001 {
m.threshold = i32::MAX;
}
}
fn convert_ppm_to_motif(
m: &mut FMotif,
ppm: &[[u64; 4]],
nsites: u64,
bkg: &[f64; 4],
pc: u32,
hit_pval: f64,
) {
let w = ppm.len();
m.init(w);
m.nsites = nsites;
for (j, col) in ppm.iter().enumerate() {
let mut total = col.iter().sum::<u64>() as f64;
if total <= 0.0 {
total = 1.0;
}
for i in 0..4 {
let raw = col[i] as f64 / total;
m.probs[j][i] = (raw * nsites as f64 + pc as f64 / 4.0) / (nsites + pc as u64) as f64;
m.pwm[i + j * 5] = calc_score_ns(raw, bkg[i], nsites, pc);
}
}
m.mn = (0..w)
.flat_map(|p| (0..4).map(move |l| (p, l)))
.fold(0, |a, (p, l)| a.min(m.score(l, p)));
m.mx = (0..w)
.flat_map(|p| (0..4).map(move |l| (p, l)))
.fold(0, |a, (p, l)| a.max(m.score(l, p)));
m.cdf_offset = m.mn * w as i32;
for pos in 0..w {
for (idx, &comp) in COMP4.iter().enumerate() {
m.pwm_rc[idx + (w - 1 - pos) * 5] = m.score(comp, pos);
}
}
m.cdf_max = m.mx - m.mn;
m.cdf_size = w as u64 * m.cdf_max as u64 + 1;
CDF_BUFFERS.with(|b| {
let (cdf, tmp) = &mut *b.borrow_mut();
if m.cdf_max == 0 || m.cdf_size > MAX_CDF_SIZE || !fill_cdf(m, bkg, cdf, tmp) {
m.threshold = i32::MAX;
return;
}
set_threshold_pval(m, cdf, hit_pval);
if m.threshold == i32::MAX {
set_threshold_pval(m, cdf, 0.01);
}
});
}
fn kmer_encode(seq: &[u8], w: usize, off: usize) -> Option<u64> {
let mut k = 0u64;
for &c in &seq[off..off + w] {
let i = CHAR2IDX[c as usize];
if i >= 4 {
return None;
}
k = k * 4 + i as u64;
}
Some(k)
}
fn rc_kmer(mut kmer: u64, w: usize) -> u64 {
let mut rc = 0;
for _ in 0..w {
rc = rc * 4 + COMP4[(kmer & 3) as usize] as u64;
kmer >>= 2;
}
rc
}
fn hamming(mut a: u64, mut b: u64, w: usize) -> u64 {
let mut mm = 0;
for _ in 0..w {
if a & 3 != b & 3 {
mm += 1;
}
a >>= 2;
b >>= 2;
}
mm
}
struct LogFact(Vec<f64>);
impl LogFact {
fn new(n: usize) -> LogFact {
LogFact((0..=n).map(|i| libm::lgamma(i as f64 + 1.0)).collect())
}
fn choose(&self, n: u64, k: u64) -> f64 {
self.0[n as usize] - self.0[k as usize] - self.0[(n - k) as usize]
}
}
fn fisher_greater(lf: &LogFact, a: u64, b: u64, c: u64, d: u64) -> f64 {
ln_fisher_greater(lf, a, b, c, d).exp()
}
fn ln_fisher_greater(lf: &LogFact, a: u64, b: u64, c: u64, d: u64) -> f64 {
let (r1, r2) = (a + b, c + d);
let c1 = a + c;
let n = a + b + c + d;
let denom = lf.choose(n, c1);
let x_max = r1.min(c1);
let mut log_sum = lf.choose(r1, a) + lf.choose(r2, c1 - a) - denom;
for x in a + 1..=x_max {
let term = lf.choose(r1, x) + lf.choose(r2, c1 - x) - denom;
if term > log_sum {
log_sum = term + (log_sum - term).exp().ln_1p();
} else {
log_sum += (term - log_sum).exp().ln_1p();
}
}
log_sum.min(0.0)
}
fn score_at(m: &FMotif, seq: &[u8], off: usize) -> (i32, i32) {
let (mut s, mut src) = (0, 0);
for i in 0..m.size {
let idx = CHAR2IDX[seq[off + i] as usize] as usize;
s += m.pwm[idx + i * 5];
src += m.pwm_rc[idx + i * 5];
}
(s, src)
}
fn kmer_presence(seqs: &[Vec<u8>], w: usize, rc: bool) -> (Vec<u64>, Vec<u32>) {
let mask = if w == 32 {
u64::MAX
} else {
(1u64 << (2 * w)) - 1
};
let total: usize = seqs.iter().map(|s| (s.len() + 1).saturating_sub(w)).sum();
let mut all: Vec<u64> = Vec::with_capacity(total);
let longest = seqs.iter().map(|s| s.len()).max().unwrap_or(0);
let mut seen: Vec<u64> = Vec::with_capacity(longest);
for s in seqs {
seen.clear();
let (mut fwd, mut rev, mut run) = (0u64, 0u64, 0usize);
for &b in s {
let idx = CHAR2IDX[b as usize];
if idx >= 4 {
run = 0;
continue;
}
fwd = ((fwd << 2) | idx as u64) & mask;
rev = (rev >> 2) | ((COMP4[idx as usize] as u64) << (2 * (w - 1)));
run += 1;
if run >= w {
seen.push(if rc { fwd.min(rev) } else { fwd });
}
}
seen.sort_unstable();
seen.dedup();
all.extend_from_slice(&seen);
}
all.sort_unstable();
let mut counts: Vec<u32> = Vec::with_capacity(all.len());
let mut n = 0;
for i in 0..all.len() {
if n > 0 && all[n - 1] == all[i] {
counts[n - 1] += 1;
} else {
all[n] = all[i];
counts.push(1);
n += 1;
}
}
all.truncate(n);
(all, counts)
}
fn enumerate_seeds(
pos: &[Vec<u8>],
neg: &[Vec<u8>],
w: usize,
rc: bool,
lf: &LogFact,
) -> (Vec<(u64, f64)>, u64) {
let ((pk, pn), (nk, nn_)) = (kmer_presence(pos, w, rc), kmer_presence(neg, w, rc));
let (np, nn) = (pos.len() as u64, neg.len() as u64);
let mut memo: HashMap<(u64, u64), f64> = HashMap::new();
let mut best: Vec<(u64, f64)> = Vec::with_capacity(TOP_K_SEEDS + 1);
let mut j = 0;
for (&k, &pc) in pk.iter().zip(&pn) {
let pc = pc as u64;
while j < nk.len() && nk[j] < k {
j += 1;
}
let nc = if j < nk.len() && nk[j] == k {
nn_[j] as u64
} else {
0
};
let p = *memo.entry((pc, nc)).or_insert_with(|| {
fisher_greater(lf, pc, nc, np.saturating_sub(pc), nn.saturating_sub(nc))
});
if best.len() < TOP_K_SEEDS || p < best[best.len() - 1].1 {
let at = best.partition_point(|&(_, q)| q <= p);
best.insert(at, (k, p));
best.truncate(TOP_K_SEEDS);
}
}
(best, pk.len() as u64)
}
fn add_site(ppm: &mut [[u64; 4]], seq: &[u8], off: usize, w: usize, reverse: bool) {
for i in 0..w {
if reverse {
let idx = CHAR2IDX[seq[off + w - 1 - i] as usize] as usize;
if idx < 4 {
ppm[i][COMP4[idx]] += 1;
}
} else {
let idx = CHAR2IDX[seq[off + i] as usize] as usize;
if idx < 4 {
ppm[i][idx] += 1;
}
}
}
}
fn build_ppm_from_seed(pos: &[Vec<u8>], seed: u64, w: usize, rc: bool) -> (Vec<[u64; 4]>, u64) {
let rc_seed = rc.then(|| rc_kmer(seed, w));
let mut ppm = vec![[0u64; 4]; w];
let mut nsites = 0;
for s in pos {
if s.len() < w {
continue;
}
for off in 0..=s.len() - w {
let Some(k) = kmer_encode(s, w, off) else {
continue;
};
if hamming(k, seed, w) <= HAMMING_MISMATCH {
add_site(&mut ppm, s, off, w, false);
nsites += 1;
} else if rc_seed.is_some_and(|r| hamming(k, r, w) <= HAMMING_MISMATCH) {
add_site(&mut ppm, s, off, w, true);
nsites += 1;
}
}
}
(ppm, nsites)
}
fn refine(
pos: &[Vec<u8>],
m: &mut FMotif,
w: usize,
rc: bool,
bkg: &[f64; 4],
pc: u32,
hit_pval: f64,
) -> bool {
if m.threshold == i32::MAX {
return false;
}
let thr = m.threshold - 1;
let mut ppm = vec![[0u64; 4]; w];
let mut nsites = 0;
for s in pos {
if s.len() < w {
continue;
}
for off in 0..=s.len() - w {
let (sc, src) = score_at(m, s, off);
if sc > thr {
add_site(&mut ppm, s, off, w, false);
nsites += 1;
}
if rc && src > thr {
add_site(&mut ppm, s, off, w, true);
nsites += 1;
}
}
}
if nsites < MIN_REFINE_HITS {
return false;
}
convert_ppm_to_motif(m, &ppm, nsites, bkg, pc, hit_pval);
true
}
struct Evaluation {
ln_pvalue: f64,
sites_pos: u64,
sites_neg: u64,
seqs_pos: u64,
seqs_neg: u64,
covered: Coverage,
}
struct Coverage {
starts: Vec<usize>,
bits: Vec<u64>,
}
impl Coverage {
fn new(seqs: &[Vec<u8>]) -> Coverage {
let mut starts = Vec::with_capacity(seqs.len());
let mut total = 0;
for s in seqs {
starts.push(total);
total += s.len();
}
Coverage {
starts,
bits: vec![0; total.div_ceil(64)],
}
}
fn fill(&mut self, seq: usize, from: usize, len: usize) {
for p in self.starts[seq] + from..self.starts[seq] + from + len {
self.bits[p / 64] |= 1 << (p % 64);
}
}
fn contains(&self, seq: usize, pos: usize) -> bool {
let p = self.starts[seq] + pos;
self.bits[p / 64] & (1 << (p % 64)) != 0
}
fn count(&self) -> u64 {
self.bits.iter().map(|w| w.count_ones() as u64).sum()
}
fn shared(&self, other: &Coverage) -> u64 {
self.bits
.iter()
.zip(&other.bits)
.map(|(a, b)| (a & b).count_ones() as u64)
.sum()
}
}
fn evaluate(pos: &[Vec<u8>], neg: &[Vec<u8>], m: &FMotif, rc: bool, lf: &LogFact) -> Evaluation {
let thr = m.threshold - 1;
let w = m.size;
let mut covered = Coverage::new(pos);
let (mut sites_pos, mut seqs_pos, mut sites_neg, mut seqs_neg) = (0, 0, 0, 0);
for (si, s) in pos.iter().enumerate() {
if s.len() < w {
continue;
}
let mut hit = false;
for off in 0..=s.len() - w {
let (sc, src) = score_at(m, s, off);
for found in [sc > thr, rc && src > thr] {
if found {
hit = true;
sites_pos += 1;
covered.fill(si, off, w);
}
}
}
seqs_pos += hit as u64;
}
for s in neg {
if s.len() < w {
continue;
}
let mut hit = false;
for off in 0..=s.len() - w {
let (sc, src) = score_at(m, s, off);
for found in [sc > thr, rc && src > thr] {
if found {
hit = true;
sites_neg += 1;
}
}
}
seqs_neg += hit as u64;
}
let (np, nn) = (pos.len() as u64, neg.len() as u64);
Evaluation {
ln_pvalue: ln_fisher_greater(
lf,
seqs_pos,
seqs_neg,
np.saturating_sub(seqs_pos),
nn.saturating_sub(seqs_neg),
),
sites_pos,
sites_neg,
seqs_pos,
seqs_neg,
covered,
}
}
struct Found {
motif: FMotif,
eval: Evaluation,
width: usize,
order: usize,
candidates: u64,
}
#[allow(clippy::too_many_arguments)]
fn discover_for_width(
pos: &[Vec<u8>],
neg: &[Vec<u8>],
w: usize,
nmotifs: usize,
rc: bool,
bkg: &[f64; 4],
pc: u32,
hit_pval: f64,
stop_pval: f64,
lf: &LogFact,
) -> (Vec<Found>, u64) {
let mut work = pos.to_vec();
let mut out = Vec::new();
let mut tested = 0;
for _ in 0..nmotifs {
let (seeds, candidates) = enumerate_seeds(&work, neg, w, rc, lf);
tested += candidates;
if seeds.is_empty() {
break;
}
let mut accepted = false;
for &(seed, _) in &seeds {
let (ppm, nsites) = build_ppm_from_seed(&work, seed, w, rc);
if nsites < MIN_REFINE_HITS {
continue;
}
let mut m = FMotif::default();
convert_ppm_to_motif(&mut m, &ppm, nsites, bkg, pc, hit_pval);
if m.threshold == i32::MAX {
continue;
}
for _ in 0..REFINE_PASSES {
if !refine(&work, &mut m, w, rc, bkg, pc, hit_pval) {
break;
}
}
if m.threshold == i32::MAX {
continue;
}
let eval = evaluate(&work, neg, &m, rc, lf);
if eval.ln_pvalue > stop_pval.ln() {
continue;
}
for (si, s) in work.iter_mut().enumerate() {
for (p, b) in s.iter_mut().enumerate() {
if eval.covered.contains(si, p) {
*b = b'N';
}
}
}
let order = out.len();
out.push(Found {
motif: m,
eval,
width: w,
order,
candidates,
});
accepted = true;
break;
}
if !accepted {
break;
}
}
(out, tested)
}
fn column_ic(p: &[f64; 4]) -> f64 {
let ic = p
.iter()
.filter(|&&x| x > 0.0)
.fold(2.0, |acc, &x| acc + x * x.log2());
ic.max(0.0)
}
#[derive(Debug, Clone, PartialEq)]
pub struct FinderOptions {
pub min_width: usize,
pub max_width: usize,
pub nmotifs: usize,
pub hit_pvalue: f64,
pub stop_pvalue: f64,
pub qvalue: f64,
pub dedup_overlap: f64,
pub rc: bool,
pub shuffle_k: usize,
pub seed: u64,
pub pseudocount: u32,
pub nthreads: usize,
}
impl Default for FinderOptions {
fn default() -> Self {
FinderOptions {
min_width: 6,
max_width: 15,
nmotifs: 10,
hit_pvalue: 1e-4,
stop_pvalue: 1e-3,
qvalue: 0.05,
dedup_overlap: 0.5,
rc: true,
shuffle_k: 2,
seed: 1,
pseudocount: 1,
nthreads: 1,
}
}
}
#[derive(Debug, Clone, PartialEq)]
#[non_exhaustive]
pub struct FoundMotif {
pub motif: Motif,
pub rank: usize,
pub seqs_pos: u64,
pub seqs_neg: u64,
pub sites_pos: u64,
pub sites_neg: u64,
pub n_pos: usize,
pub n_neg: usize,
pub candidates: u64,
pub pvalue: f64,
pub log10_pvalue: f64,
pub qvalue: f64,
pub log10_qvalue: f64,
}
pub(crate) fn finder_background<S: AsRef<str>>(pos: &[S], neg: &[S]) -> [f64; 4] {
let mut counts = [0f64; 4];
for s in pos.iter().chain(neg) {
for b in s.as_ref().bytes() {
if CHAR2IDX[b as usize] < 4 {
counts[CHAR2IDX[b as usize] as usize] += 1.0;
}
}
}
let total: f64 = counts.iter().sum();
let mut bkg = counts.map(|c| if total > 0.0 { c / total } else { 0.25 });
for b in bkg.iter_mut() {
if *b < 1e-3 {
*b = 1e-3;
}
}
let s: f64 = bkg.iter().sum();
bkg.map(|b| b / s)
}
pub fn motif_finder<S: AsRef<str> + Sync>(
sequences: &[S],
negatives: Option<&[S]>,
opts: &FinderOptions,
) -> Result<Vec<FoundMotif>> {
if sequences.is_empty() {
return arg_err("no sequences given");
}
if opts.min_width < 3 || opts.max_width > MAX_MOTIF_WIDTH || opts.min_width > opts.max_width {
return arg_err("widths must satisfy 3 <= min_width <= max_width <= 30");
}
if opts.nmotifs < 1 {
return arg_err("nmotifs must be at least 1");
}
if !(opts.hit_pvalue > 0.0 && opts.hit_pvalue < 1.0)
|| !(opts.stop_pvalue > 0.0 && opts.stop_pvalue <= 1.0)
|| !(opts.qvalue > 0.0 && opts.qvalue <= 1.0)
|| !(0.0..=1.0).contains(&opts.dedup_overlap)
{
return arg_err(
"hit_pvalue must be in (0, 1); stop_pvalue and qvalue in (0, 1]; dedup_overlap in [0, 1]",
);
}
let rna = sequences.iter().any(|s| s.as_ref().contains(['U', 'u']));
let alphabet = if rna { Alphabet::Rna } else { Alphabet::Dna };
let shuffled: Vec<String>;
let neg_strs: Vec<&str> = match negatives {
Some(n) => n.iter().map(|s| s.as_ref()).collect(),
None => {
shuffled = shuffled_background(
sequences,
&ShuffleOptions {
k: opts.shuffle_k,
method: ShuffleMethod::Euler,
seed: opts.seed,
window: None,
nthreads: opts.nthreads,
},
)?;
shuffled.iter().map(|s| s.as_str()).collect()
}
};
if neg_strs.is_empty() {
return arg_err("no negative sequences");
}
let pos_strs: Vec<&str> = sequences.iter().map(|s| s.as_ref()).collect();
let bkg = finder_background(&pos_strs, &neg_strs);
let pos: Vec<Vec<u8>> = pos_strs.iter().map(|s| s.as_bytes().to_vec()).collect();
let neg: Vec<Vec<u8>> = neg_strs.iter().map(|s| s.as_bytes().to_vec()).collect();
let lf = LogFact::new(pos.len() + neg.len());
let widths: Vec<usize> = (opts.min_width..=opts.max_width).collect();
let per_width: Vec<(Vec<Found>, u64)> = with_threads(opts.nthreads, || {
widths
.par_iter()
.map(|&w| {
discover_for_width(
&pos,
&neg,
w,
opts.nmotifs,
opts.rc,
&bkg,
opts.pseudocount,
opts.hit_pvalue,
opts.stop_pvalue,
&lf,
)
})
.collect()
})?;
let total_tests: u64 = per_width.iter().map(|(_, t)| t).sum();
let mut found: Vec<Found> = per_width.into_iter().flat_map(|(f, _)| f).collect();
found.sort_by_key(|f| (f.width, f.order));
if found.is_empty() {
return Ok(Vec::new());
}
for f in found.iter_mut() {
f.eval = evaluate(&pos, &neg, &f.motif, opts.rc, &lf);
}
let corrected = |f: &Found| (f.eval.ln_pvalue + (f.candidates as f64).ln()).min(0.0);
found.sort_by(|a, b| a.eval.ln_pvalue.total_cmp(&b.eval.ln_pvalue));
let mut dropped = vec![false; found.len()];
let counts: Vec<u64> = found.iter().map(|f| f.eval.covered.count()).collect();
for i in 0..found.len() {
if dropped[i] {
continue;
}
for j in i + 1..found.len() {
if dropped[j] {
continue;
}
let inter = found[i].eval.covered.shared(&found[j].eval.covered);
let smin = counts[i].min(counts[j]);
if smin > 0 && inter as f64 / smin as f64 > opts.dedup_overlap {
dropped[j] = true;
}
}
}
let mut survivors: Vec<Found> = found
.into_iter()
.zip(dropped)
.filter(|(_, d)| !d)
.map(|(f, _)| f)
.collect();
survivors.sort_by(|a, b| corrected(a).total_cmp(&corrected(b)));
let ln_q = crate::stats::ln_p_adjust_bh(
&survivors
.iter()
.map(|f| f.eval.ln_pvalue)
.collect::<Vec<_>>(),
total_tests.max(survivors.len() as u64) as f64,
);
let mut out = Vec::new();
for (f, ln_qv) in survivors.iter().zip(ln_q) {
let qv = ln_qv.exp();
let ln_pv = corrected(f);
let probs = &f.motif.probs;
let mut left = 0;
while left < probs.len() && column_ic(&probs[left]) < MIN_IC_BITS {
left += 1;
}
let mut right = probs.len();
while right > left && column_ic(&probs[right - 1]) < MIN_IC_BITS {
right -= 1;
}
let kept = if right - left < 3 {
probs.as_slice()
} else {
&probs[left..right]
};
let cols: Vec<Vec<f64>> = kept.iter().map(|c| c.to_vec()).collect();
if qv > opts.qvalue {
continue;
}
let copts = CreateOptions {
motif_type: MotifType::Ppm,
name: format!("motif_{}", out.len() + 1),
nsites: Some(f.motif.nsites as f64),
pseudocount: opts.pseudocount as f64,
bkg: Some(bkg.to_vec()),
pval: Some(ln_pv.exp()),
eval: Some(qv),
strand: if opts.rc { Strand::Both } else { Strand::Plus },
..Default::default()
};
let motif = from_matrix(
Matrix::from_columns(&cols)?,
None,
Some(alphabet.clone()),
&copts,
)?;
out.push(FoundMotif {
motif,
rank: out.len() + 1,
seqs_pos: f.eval.seqs_pos,
seqs_neg: f.eval.seqs_neg,
sites_pos: f.eval.sites_pos,
sites_neg: f.eval.sites_neg,
n_pos: pos.len(),
n_neg: neg.len(),
candidates: f.candidates,
pvalue: ln_pv.exp(),
log10_pvalue: ln_pv / std::f64::consts::LN_10,
qvalue: qv,
log10_qvalue: ln_qv / std::f64::consts::LN_10,
});
}
Ok(out)
}
#[derive(Debug, Clone, PartialEq)]
#[non_exhaustive]
pub struct SpacedPair {
pub left: u64,
pub right: u64,
pub gap: usize,
pub width: usize,
pub positives: u32,
pub negatives: u32,
pub ln_pvalue: f64,
}
type Slots<'a> = dyn Fn(usize, usize, &mut dyn FnMut(usize)) + Sync + 'a;
#[allow(clippy::too_many_arguments)]
pub fn spaced_pairs<S: AsRef<str> + Sync>(
positives: &[S],
negatives: &[S],
k: usize,
min_gap: usize,
max_gap: usize,
rc: bool,
min_count: u32,
mismatch: bool,
nthreads: usize,
) -> Result<Vec<SpacedPair>> {
if !(2..=6).contains(&k) {
return arg_err("k must be from 2 to 6");
}
if min_gap > max_gap || max_gap > 100 {
return arg_err("gaps must satisfy min_gap <= max_gap <= 100");
}
let min_count = min_count.max(1);
let n_gaps = max_gap - min_gap + 1;
let mut windows: Vec<(usize, usize)> = Vec::new();
for w in [1usize, 2, 4, 8, 16] {
if w > n_gaps {
break;
}
let step = if w <= 2 { 1 } else { w / 2 };
let mut st = 0;
loop {
windows.push((st, w));
if st + w >= n_gaps {
break;
}
st = (st + step).min(n_gaps - w);
}
}
let n_windows = windows.len();
let of_gap: Vec<Vec<u32>> = (0..n_gaps)
.map(|g| {
windows
.iter()
.enumerate()
.filter(|(_, (st, w))| *st <= g && g < st + w)
.map(|(i, _)| i as u32)
.collect()
})
.collect();
let n_kmers = 1usize << (2 * k);
let n_pairs = n_kmers * n_kmers;
let threads = nthreads.max(1);
let each_pair = |seq: &S, codes: &mut Vec<Option<u64>>, f: &mut dyn FnMut(usize, usize)| {
let bytes = seq.as_ref().as_bytes();
if bytes.len() < 2 * k + min_gap {
return;
}
codes.clear();
codes.extend((0..=bytes.len() - k).map(|i| kmer_encode(bytes, k, i)));
for i in 0..codes.len() {
let Some(a) = codes[i] else { continue };
for g in min_gap..=max_gap {
let j = i + k + g;
if j >= codes.len() {
break;
}
let Some(b) = codes[j] else { continue };
let pair = (a << (2 * k)) | b;
let rev = rc_kmer(pair, 2 * k);
let canon = |p: u64, r: u64| (if rc { p.min(r) } else { p }) as usize;
f(canon(pair, rev), g - min_gap);
if mismatch {
for i in 0..2 * k {
let (sh, rsh) = (2 * i, 2 * (2 * k - 1 - i));
for x in 1..4u64 {
f(canon(pair ^ (x << sh), rev ^ (x << rsh)), g - min_gap);
}
}
}
}
}
};
let count = |seqs: &[S], len: usize, slots: &Slots| {
let chunk = seqs.len().div_ceil(threads).max(1);
let parts: Vec<Vec<u32>> = with_threads(threads, || {
seqs.par_chunks(chunk)
.map(|part| {
let mut counts = vec![0u32; len];
let mut seen = vec![0u64; len.div_ceil(64)];
let mut touched: Vec<usize> = Vec::new();
let mut codes: Vec<Option<u64>> = Vec::new();
for seq in part {
each_pair(seq, &mut codes, &mut |pair, gi| {
slots(pair, gi, &mut |p| {
let (word, bit) = (p / 64, 1u64 << (p % 64));
if seen[word] & bit == 0 {
seen[word] |= bit;
touched.push(p);
counts[p] += 1;
}
})
});
for &p in &touched {
seen[p / 64] = 0;
}
touched.clear();
}
counts
})
.collect()
})?;
let mut total = vec![0u32; len];
for part in parts {
for (t, v) in total.iter_mut().zip(part) {
*t += v;
}
}
Ok::<_, crate::error::Error>(total)
};
let (n_pos, n_neg) = (positives.len() as u64, negatives.len() as u64);
let lf = LogFact::new((n_pos + n_neg) as usize);
let mut index = count(positives, n_pairs, &|pair, _, f| f(pair))?;
let n_kept = index.iter().filter(|&&c| c >= min_count).count();
let mut kept: Vec<usize> = Vec::with_capacity(n_kept);
kept.extend((0..n_pairs).filter(|&p| index[p] >= min_count));
if kept.len() > MAX_SPACED_PAIRS {
let any_neg = count(negatives, n_pairs, &|pair, _, f| f(pair))?;
let mut scored: Vec<(f64, usize)> = Vec::with_capacity(kept.len());
scored.extend(kept.iter().map(|&p| {
let (c, d) = (index[p] as u64, any_neg[p] as u64);
(ln_fisher_greater(&lf, c, n_pos - c, d, n_neg - d), p)
}));
drop(any_neg);
scored.select_nth_unstable_by(MAX_SPACED_PAIRS - 1, |a, b| a.0.total_cmp(&b.0));
kept.clear();
kept.extend(scored[..MAX_SPACED_PAIRS].iter().map(|&(_, p)| p));
kept.sort_unstable();
}
index.fill(u32::MAX);
let mut is_kept = vec![0u64; n_pairs.div_ceil(64)];
for (i, &p) in kept.iter().enumerate() {
index[p] = i as u32;
is_kept[p / 64] |= 1 << (p % 64);
}
let by_window = |pair: usize, gi: usize, f: &mut dyn FnMut(usize)| {
if is_kept[pair / 64] & (1 << (pair % 64)) == 0 {
return;
}
let i = index[pair];
if i != u32::MAX {
let base = i as usize * n_windows;
for &win in &of_gap[gi] {
f(base + win as usize);
}
}
};
let len = kept.len() * n_windows;
let pos = count(positives, len, &by_window)?;
let neg = count(negatives, len, &by_window)?;
let mut out: Vec<SpacedPair> =
Vec::with_capacity(pos.iter().filter(|&&c| c >= min_count).count());
out.extend(
pos.iter()
.enumerate()
.filter(|&(_, &c)| c >= min_count)
.map(|(p, &c)| {
let (st, w) = windows[p % n_windows];
let pair = kept[p / n_windows];
let d = neg[p] as u64;
SpacedPair {
left: (pair / n_kmers) as u64,
right: (pair % n_kmers) as u64,
gap: min_gap + st,
width: w,
positives: c,
negatives: d as u32,
ln_pvalue: ln_fisher_greater(&lf, c as u64, n_pos - c as u64, d, n_neg - d),
}
}),
);
out.sort_by(|a, b| a.ln_pvalue.total_cmp(&b.ln_pvalue));
Ok(out)
}