use std::collections::{HashMap, HashSet};
use crate::alphabet::Alphabet;
use crate::convert::convert_type;
use crate::create::{CreateOptions, from_strings, from_typed_matrix};
use crate::error::{Result, arg_err};
use crate::finder::spaced_pairs;
use crate::mask::{DustOptions, mask_complexity};
use crate::matrix::Matrix;
use crate::motif::{Motif, MotifType};
use crate::ops::{add_gap, normalize};
use crate::packed::EncodedSequences;
use crate::scan::{HitTable, NoOverlaps, ScanOptions, scan_encoded};
use crate::shuffle::{ShuffleMethod, ShuffleOptions, shuffled_background};
use crate::stats::ln_fisher_greater;
#[derive(Debug, Clone, PartialEq)]
pub struct GappedFinderOptions {
pub k: Vec<usize>,
pub min_gap: usize,
pub max_gap: usize,
pub nmotifs: usize,
pub hit_pvalue: f64,
pub stop_pvalue: f64,
pub flank: usize,
pub min_ic: f64,
pub n_seed_pairs: usize,
pub min_fraction: f64,
pub holdout: f64,
pub mismatch: bool,
pub mask: bool,
pub rc: bool,
pub shuffle_k: usize,
pub seed: u64,
pub nthreads: usize,
}
impl Default for GappedFinderOptions {
fn default() -> Self {
GappedFinderOptions {
k: vec![4, 5, 6],
min_gap: 0,
max_gap: 20,
nmotifs: 3,
hit_pvalue: 1e-4,
stop_pvalue: 1e-3,
flank: 3,
min_ic: 0.5,
n_seed_pairs: 6,
min_fraction: 0.02,
holdout: 0.3,
mismatch: false,
mask: true,
rc: true,
shuffle_k: 2,
seed: 1,
nthreads: 1,
}
}
}
#[derive(Debug, Clone, PartialEq)]
#[non_exhaustive]
pub struct GappedMotif {
pub motif: Motif,
pub k: usize,
pub seed_pair: String,
pub seqs_pos: u64,
pub seqs_neg: u64,
pub n_pos: usize,
pub n_neg: usize,
pub candidates: u64,
pub seed_pairs: usize,
pub pvalue: f64,
pub log10_pvalue: f64,
pub spacing_pvalue: f64,
pub log10_spacing_pvalue: f64,
}
struct Candidate {
motif: Motif,
hits: Vec<(usize, usize, usize)>,
held_out_hits: Vec<(usize, usize, usize)>,
seqs_pos: u64,
seqs_neg: u64,
ln_spacing: f64,
ln_p: f64,
k: usize,
seed: String,
n_tested: usize,
tried: usize,
}
struct SeqSet {
text: Vec<String>,
encoded: EncodedSequences,
}
impl SeqSet {
fn new(text: Vec<String>, nthreads: usize) -> Result<SeqSet> {
let encoded = EncodedSequences::new(&text, &Alphabet::Dna, nthreads)?;
Ok(SeqSet { text, encoded })
}
}
struct Profile {
hits: HitTable,
spacers: Vec<usize>,
observed: Vec<f64>,
expected: Vec<f64>,
}
fn split(seqs: Vec<String>, fraction: f64, seed: u64) -> (Vec<String>, Vec<String>) {
let (mut kept, mut held) = (Vec::new(), Vec::new());
for (i, s) in seqs.into_iter().enumerate() {
let mut z = seed.wrapping_add((i as u64 + 1).wrapping_mul(0x9e37_79b9_7f4a_7c15));
z = (z ^ (z >> 30)).wrapping_mul(0xbf58_476d_1ce4_e5b9);
z = (z ^ (z >> 27)).wrapping_mul(0x94d0_49bb_1331_11eb);
z ^= z >> 31;
if ((z >> 11) as f64 / (1u64 << 53) as f64) < fraction {
held.push(s);
} else {
kept.push(s);
}
}
(kept, held)
}
fn masked(set: &mut SeqSet, hits: &[(usize, usize, usize)], nthreads: usize) -> Result<SeqSet> {
let mut text = std::mem::take(&mut set.text);
for &(i, s, e) in hits {
text[i].replace_range(s..e, &"N".repeat(e - s));
}
SeqSet::new(text, nthreads)
}
struct Search<'a> {
opts: &'a GappedFinderOptions,
work: SeqSet,
neg: &'a SeqSet,
held_out: Option<(SeqSet, SeqSet)>,
}
pub fn gapped_motif_finder<S: AsRef<str> + Sync>(
sequences: &[S],
negatives: Option<&[S]>,
opts: &GappedFinderOptions,
) -> Result<Vec<GappedMotif>> {
if sequences.is_empty() {
return arg_err("no sequences given");
}
if opts.k.is_empty() || opts.k.iter().any(|k| !(2..=6).contains(k)) {
return arg_err("each k must be from 2 to 6");
}
if opts.min_gap > opts.max_gap || opts.max_gap > 100 {
return arg_err("gaps must satisfy min_gap <= max_gap <= 100");
}
if !(opts.hit_pvalue > 0.0 && opts.hit_pvalue < 1.0)
|| !(opts.stop_pvalue > 0.0 && opts.stop_pvalue <= 1.0)
{
return arg_err("hit_pvalue must be in (0, 1) and stop_pvalue in (0, 1]");
}
if !(0.0..=1.0).contains(&opts.min_fraction) {
return arg_err("min_fraction must be in [0, 1]");
}
if !(0.0..0.9).contains(&opts.holdout) {
return arg_err("holdout must be in [0, 0.9)");
}
let pos: Vec<String> = sequences.iter().map(|s| dna_text(s.as_ref())).collect();
let neg: Vec<String> = match negatives {
Some(n) => n.iter().map(|s| dna_text(s.as_ref())).collect(),
None => shuffled_background(
&pos,
&ShuffleOptions {
k: opts.shuffle_k,
method: ShuffleMethod::Euler,
seed: opts.seed,
window: None,
nthreads: opts.nthreads,
},
)?,
};
if neg.is_empty() {
return arg_err("no negative sequences");
}
let (pos, neg) = if opts.mask {
let dust = DustOptions {
letter: 'N',
nthreads: opts.nthreads,
..Default::default()
};
(mask_complexity(&pos, &dust)?, mask_complexity(&neg, &dust)?)
} else {
(pos, neg)
};
let (n_pos, n_neg) = (pos.len(), neg.len());
let (pos, neg, held_out) = if opts.holdout > 0.0 {
let (pos, test_pos) = split(pos, opts.holdout, opts.seed);
let (neg, test_neg) = split(neg, opts.holdout, opts.seed ^ 0x9e37_79b9_7f4a_7c15);
if test_pos.is_empty() || test_neg.is_empty() || pos.len() < 2 || neg.is_empty() {
return arg_err("too few sequences to hold some out; set holdout to 0");
}
let test = (
SeqSet::new(test_pos, opts.nthreads)?,
SeqSet::new(test_neg, opts.nthreads)?,
);
(pos, neg, Some(test))
} else {
(pos, neg, None)
};
let min_count = 5.max((opts.min_fraction * pos.len() as f64) as u32);
let mut ks = opts.k.clone();
ks.sort_unstable();
ks.dedup();
let neg = SeqSet::new(neg, opts.nthreads)?;
let mut search = Search {
opts,
work: SeqSet::new(pos, opts.nthreads)?,
neg: &neg,
held_out,
};
let ln_stop = opts.stop_pvalue.ln();
let mut out = Vec::new();
for found in 0..opts.nmotifs {
let name = format!("gapped_{}", found + 1);
let mut candidates = Vec::new();
for &k in &ks {
candidates.extend(search.seed_candidates(k, min_count, &name)?);
}
if candidates.is_empty() {
break;
}
let n_candidates = candidates.len() as f64;
let ln_enriched = if search.held_out.is_some() {
0.05f64.ln()
} else {
ln_stop
};
for c in &mut candidates {
if search.held_out.is_some() {
search.test(c)?;
c.ln_spacing += n_candidates.ln();
} else {
c.ln_spacing +=
(c.n_tested as f64).ln() + (c.tried as f64).ln() + (ks.len() as f64).ln();
}
}
let mut best: Option<Candidate> = None;
for c in candidates {
if c.ln_spacing > ln_stop || c.ln_p > ln_enriched {
continue;
}
let better = match &best {
None => true,
Some(b) => {
(!c.motif.gap.isgapped, c.ln_spacing) < (!b.motif.gap.isgapped, b.ln_spacing)
}
};
if better {
best = Some(c);
}
}
let Some(best) = best else { break };
search.work = masked(&mut search.work, &best.hits, opts.nthreads)?;
if let Some((test_pos, _)) = &mut search.held_out {
*test_pos = masked(test_pos, &best.held_out_hits, opts.nthreads)?;
}
out.push(GappedMotif {
motif: best.motif,
k: best.k,
seed_pair: best.seed,
seqs_pos: best.seqs_pos,
seqs_neg: best.seqs_neg,
n_pos,
n_neg,
candidates: best.n_tested as u64,
seed_pairs: best.tried,
pvalue: best.ln_p.min(0.0).exp(),
log10_pvalue: best.ln_p.min(0.0) / std::f64::consts::LN_10,
spacing_pvalue: best.ln_spacing.min(0.0).exp(),
log10_spacing_pvalue: best.ln_spacing.min(0.0) / std::f64::consts::LN_10,
});
}
Ok(out)
}
impl Search<'_> {
fn seed_candidates(&self, k: usize, min_count: u32, name: &str) -> Result<Vec<Candidate>> {
let o = self.opts;
let mismatch = o.mismatch && k == 6;
let pairs = spaced_pairs(
&self.work.text,
&self.neg.text,
k,
o.min_gap,
o.max_gap,
o.rc,
min_count,
mismatch,
o.nthreads,
)?;
let mut candidates: Vec<Candidate> = Vec::new();
let mut covered: HashMap<usize, Vec<(usize, usize)>> = HashMap::new();
let mut seen = HashSet::new();
let mut tried = 0;
for p in &pairs {
if tried == o.n_seed_pairs {
break;
}
if !seen.insert((p.left, p.right)) {
continue;
}
let (lo, hi) = (p.gap, p.gap + p.width - 1);
let (left, right) = (kmer_string(p.left, k), kmer_string(p.right, k));
let occ = occurrences(&self.work.text, &left, &right, lo, hi, o.rc, mismatch);
let inside = occ
.iter()
.filter(|&&(i, start, _, _)| {
covered
.get(&i)
.is_some_and(|v| v.iter().any(|&(s, e)| s <= start && start < e))
})
.count();
if !occ.is_empty() && inside * 2 > occ.len() {
continue;
}
tried += 1;
let Some(mut cand) = self.build(&occ, k, name)? else {
continue;
};
cand.seed = format!("{left}[{lo}-{hi}]{right}");
for &(i, s, e) in &cand.hits {
covered.entry(i).or_default().push((s, e));
}
candidates.push(cand);
}
for c in &mut candidates {
c.n_tested = pairs.len();
c.tried = tried;
}
Ok(candidates)
}
fn scan(&self, motif: &Motif, negatives: bool) -> Result<HitTable> {
self.scan_in(motif, if negatives { self.neg } else { &self.work })
}
fn scan_in(&self, motif: &Motif, seqs: &SeqSet) -> Result<HitTable> {
let seqs = &seqs.encoded;
let opts = ScanOptions {
pvalue: self.opts.hit_pvalue,
rc: self.opts.rc,
no_overlaps: Some(NoOverlaps::default()),
nthreads: self.opts.nthreads,
..Default::default()
};
scan_encoded(&[normalize(motif)?], seqs, &opts)
}
fn hit_sites(&self, hits: &HitTable, keep: impl Fn(usize) -> bool) -> Vec<String> {
let mut sites = Vec::with_capacity(hits.len());
for i in 0..hits.len() {
if !keep(i) {
continue;
}
let seq = &self.work.text[hits.sequence[i] as usize];
let site = &seq[hits.start[i] as usize..hits.end[i] as usize];
sites.push(if hits.minus[i] {
rc_string(site)
} else {
site.to_string()
});
}
clean(sites)
}
fn build(&self, occ: &[Occurrence], k: usize, name: &str) -> Result<Option<Candidate>> {
let o = self.opts;
let Some(lo) = occ.iter().map(|x| x.2).min() else {
return Ok(None);
};
let inner = o.flank.min(lo / 2);
let (mut wl, mut wr) = (o.flank + k + inner, inner + k + o.flank);
let mut sites = clean(
occ.iter()
.filter_map(|&(i, start, g, rev)| {
site(&self.work.text[i], start, k + g + k, rev, o.flank, o.flank)
})
.collect(),
);
if sites.len() < 5 {
return Ok(None);
}
let mut motif = with_pieces(&sites, wl, wr, name)?;
for _ in 0..2 {
let hits = self.scan(&motif, false)?;
if hits.len() < 5 {
break;
}
sites = self.hit_sites(&hits, |_| true);
motif = with_pieces(&sites, wl, wr, name)?;
}
let ic = column_ic(&ppm(&motif)?);
let (a0, a1) = strong_span(&ic[..wl], o.min_ic);
let (b0, b1) = strong_span(&ic[wl..], o.min_ic);
if a1 <= a0 || b1 <= b0 {
return Ok(None);
}
sites = clean(
sites
.iter()
.map(|x| x[a0..x.len() - (wr - b1)].to_string())
.collect(),
);
(wl, wr) = (a1 - a0, b1 - b0);
if sites.len() < 5 {
return Ok(None);
}
motif = with_pieces(&sites, wl, wr, name)?;
let Some((fit, mut ln_spacing)) = self.fit_gap(&motif, wl, wr)? else {
return Ok(None);
};
if ln_spacing > o.stop_pvalue.ln() {
return Ok(None);
}
motif = self.grow(fit)?;
if !motif.gap.isgapped {
if let Some((rep, ln)) = self.repeat(&motif)? {
(motif, ln_spacing) = (rep, ln);
}
}
let best = self.judge(normalize(&motif)?)?;
let (m, hp, sp, sn, ln_p) = best;
if !m.gap.isgapped {
return Ok(None);
}
let hits = (0..hp.len())
.map(|i| {
(
hp.sequence[i] as usize,
hp.start[i] as usize,
hp.end[i] as usize,
)
})
.collect();
Ok(Some(Candidate {
motif: m,
hits,
seqs_pos: sp,
seqs_neg: sn,
ln_spacing,
ln_p,
held_out_hits: Vec::new(),
k,
seed: String::new(),
n_tested: 0,
tried: 0,
}))
}
fn judge(&self, m: Motif) -> Result<(Motif, HitTable, u64, u64, f64)> {
let hp = self.scan(&m, false)?;
let hn = self.scan(&m, true)?;
let (sp, sn) = (n_unique(&hp.sequence), n_unique(&hn.sequence));
let (n1, n2) = (self.work.text.len() as u64, self.neg.text.len() as u64);
let ln_p = ln_fisher_greater(sp, n1 - sp, sn, n2 - sn);
Ok((m, hp, sp, sn, ln_p))
}
fn fit_gap(&self, motif: &Motif, wl: usize, wr: usize) -> Result<Option<(Motif, f64)>> {
let lo = self.opts.min_gap;
let Some(prof) = self.profile(motif, wl, wr, &self.work, self.neg)? else {
return Ok(None);
};
let (hp, sp, cp, expect) = (prof.hits, prof.spacers, prof.observed, prof.expected);
let n_in = cp.len();
let mut best = 0;
for j in 1..n_in {
if cp[j] - expect[j] > cp[best] - expect[best] {
best = j;
}
}
if cp[best] - expect[best] <= 0.0 {
return Ok(None);
}
let supported = |j: usize| cp[j] > expect[j] + 2.0 * (expect[j] + 1.0).sqrt();
let (mut a, mut b) = (best, best);
while a > 0 && supported(a - 1) {
a -= 1;
}
while b + 1 < n_in && supported(b + 1) {
b += 1;
}
let ln_spacing = ln_poisson_upper(
cp[a..=b].iter().sum::<f64>() as u64,
expect[a..=b].iter().sum(),
);
let sites = self.hit_sites(&hp, |i| (lo + a..=lo + b).contains(&sp[i]));
if sites.len() < 5 {
return Ok(None);
}
Ok(Some((
with_pieces(&sites, wl, wr, &motif.name)?,
ln_spacing,
)))
}
fn profile(
&self,
motif: &Motif,
wl: usize,
wr: usize,
pos: &SeqSet,
neg: &SeqSet,
) -> Result<Option<Profile>> {
let (lo, hi) = (self.opts.min_gap, self.opts.max_gap);
let ext = hi + 20.max(hi - lo + 1);
let wide = normalize(&add_gap(motif, Some(&[wl]), &[lo], &[ext])?)?;
let hp = self.scan_in(&wide, pos)?;
let hn = self.scan_in(&wide, neg)?;
if hp.len() < 5 {
return Ok(None);
}
let spacer = |h: &HitTable, i: usize| h.gap_sizes(i).map_or(0, |g| g[0]);
let sp: Vec<usize> = (0..hp.len()).map(|i| spacer(&hp, i)).collect();
let n_sizes = ext - lo + 1;
let mut cp = vec![0.0; n_sizes];
let mut cn = vec![0.0; n_sizes];
for &g in &sp {
cp[g - lo] += 1.0;
}
for i in 0..hn.len() {
cn[spacer(&hn, i) - lo] += 1.0;
}
let scale = pos.text.len() as f64 / neg.text.len().max(1) as f64;
let n_in = hi - lo + 1;
let flat = |seqs: &[String], counts: &[f64]| -> Option<Vec<f64>> {
let room: Vec<f64> = (lo..=ext)
.map(|g| {
seqs.iter()
.map(|s| (s.len() + 1).saturating_sub(wl + wr + g) as f64)
.sum()
})
.collect();
let tail_hits: f64 = counts[n_in..].iter().sum();
let tail_room: f64 = room[n_in..].iter().sum();
(tail_room > 0.0).then(|| {
room.iter()
.map(|r| r * (tail_hits + 1.0) / tail_room)
.collect()
})
};
let Some(flat_pos) = flat(&pos.text, &cp) else {
return Ok(None);
};
let flat_neg = flat(&neg.text, &cn).unwrap_or_else(|| cn.clone());
let expected: Vec<f64> = (0..n_in)
.map(|j| {
let excess = ((cn[j] + 5.0) / (flat_neg[j] + 5.0)).max(1.0);
(cn[j] * scale).max(flat_pos[j] * excess)
})
.collect();
cp.truncate(n_in);
Ok(Some(Profile {
hits: hp,
spacers: sp,
observed: cp,
expected,
}))
}
fn test(&self, c: &mut Candidate) -> Result<()> {
let (test_pos, test_neg) = self.held_out.as_ref().unwrap();
let m = &c.motif;
let wl = m.gap.gaploc[0];
let (lo, hi) = (self.opts.min_gap, self.opts.max_gap);
let range = m.gap.mingap[0].clamp(lo, hi) - lo..=m.gap.maxgap[0].clamp(lo, hi) - lo;
c.ln_spacing = match self.profile(m, wl, m.width() - wl, test_pos, test_neg)? {
Some(p) => ln_poisson_upper(
p.observed[range.clone()].iter().sum::<f64>() as u64,
p.expected[range].iter().sum(),
),
None => 0.0,
};
let hp = self.scan_in(m, test_pos)?;
let hn = self.scan_in(m, test_neg)?;
let (sp, sn) = (n_unique(&hp.sequence), n_unique(&hn.sequence));
let (n1, n2) = (test_pos.text.len() as u64, test_neg.text.len() as u64);
c.ln_p = ln_fisher_greater(sp, n1 - sp, sn, n2 - sn);
c.seqs_pos += sp;
c.seqs_neg += sn;
c.held_out_hits = (0..hp.len())
.map(|i| {
(
hp.sequence[i] as usize,
hp.start[i] as usize,
hp.end[i] as usize,
)
})
.collect();
Ok(())
}
fn grow(&self, mut motif: Motif) -> Result<Motif> {
let min_ic = self.opts.min_ic;
for _ in 0..8 {
if !motif.gap.isgapped {
return Ok(motif);
}
let wl = motif.gap.gaploc[0];
let wr = motif.width() - wl;
let hits = self.scan(&motif, false)?;
if hits.len() < 5 {
return Ok(motif);
}
let mut windows = Vec::with_capacity(hits.len());
for i in 0..hits.len() {
let seq = &self.work.text[hits.sequence[i] as usize];
let (s, e) = (hits.start[i] as usize, hits.end[i] as usize);
if s == 0 || e + 1 > seq.len() {
continue;
}
let w = &seq[s - 1..e + 1];
windows.push(if hits.minus[i] {
rc_string(w)
} else {
w.to_string()
});
}
let windows = clean(windows);
if windows.len() < 5 {
return Ok(motif);
}
let spacer = windows.iter().map(|w| w.len() - 2 - wl - wr).min().unwrap();
let ic_at =
|f: &dyn Fn(&[u8]) -> u8| letters_ic(windows.iter().map(|w| f(w.as_bytes())));
let left_out = ic_at(&|w| w[0]);
let right_out = ic_at(&|w| w[w.len() - 1]);
let (left_in, right_in) = if spacer >= 1 {
(ic_at(&|w| w[1 + wl]), ic_at(&|w| w[w.len() - 2 - wr]))
} else {
(0.0, 0.0)
};
let (lo_t, ro_t) = (left_out >= min_ic, right_out >= min_ic);
let (mut li_t, mut ri_t) = (left_in >= min_ic, right_in >= min_ic);
if li_t && ri_t && spacer < 2 {
if right_in < left_in {
ri_t = false;
} else {
li_t = false;
}
}
if !(lo_t || ro_t || li_t || ri_t) {
return Ok(motif);
}
let (a, b) = (usize::from(!lo_t), usize::from(!ro_t));
let sites: Vec<String> = windows
.iter()
.map(|w| w[a..w.len() - b].to_string())
.collect();
let nl = wl + usize::from(lo_t) + usize::from(li_t);
let nr = wr + usize::from(ro_t) + usize::from(ri_t);
motif = with_pieces(&sites, nl, nr, &motif.name)?;
}
Ok(motif)
}
fn repeat(&self, motif: &Motif) -> Result<Option<(Motif, f64)>> {
let m = ppm(motif)?;
let w = m.ncol();
let mut best: Option<(Motif, f64)> = None;
for other in [m.clone(), m.reversed()] {
let mut data = m.as_slice().to_vec();
data.extend_from_slice(other.as_slice());
let opts = CreateOptions {
name: motif.name.clone(),
..Default::default()
};
let two = from_typed_matrix(
Matrix::from_vec(4, 2 * w, data)?,
None,
Some(Alphabet::Dna),
MotifType::Ppm,
&opts,
)?;
if let Some((fit, ln)) = self.fit_gap(&two, w, w)?
&& ln <= self.opts.stop_pvalue.ln()
&& best.as_ref().is_none_or(|b| ln < b.1)
{
best = Some((fit, ln));
}
}
Ok(best)
}
}
type Occurrence = (usize, usize, usize, bool);
fn occurrences(
seqs: &[String],
left: &str,
right: &str,
lo: usize,
hi: usize,
rc: bool,
mismatch: bool,
) -> Vec<Occurrence> {
let k = left.len();
let mut forms = vec![(left.to_string(), right.to_string(), false)];
if rc {
forms.push((rc_string(right), rc_string(left), true));
}
let allowed = usize::from(mismatch);
let mut out = Vec::new();
for (i, s) in seqs.iter().enumerate() {
let s = s.as_bytes();
for (a, b, rev) in &forms {
let (a, b) = (a.as_bytes(), b.as_bytes());
for start in 0..s.len().saturating_sub(k - 1) {
let Some(ma) = distance(&s[start..start + k], a, allowed) else {
continue;
};
for g in lo..=hi {
let j = start + k + g;
if j + k > s.len() {
break;
}
if distance(&s[j..j + k], b, allowed - ma).is_some() {
out.push((i, start, g, *rev));
}
}
}
}
}
if mismatch {
out.sort_unstable();
out.dedup();
}
out
}
fn distance(seq: &[u8], pattern: &[u8], allowed: usize) -> Option<usize> {
let mut d = 0;
for (&x, &p) in seq.iter().zip(pattern) {
if x != p {
if !matches!(x, b'A' | b'C' | b'G' | b'T') {
return None;
}
d += 1;
if d > allowed {
return None;
}
}
}
Some(d)
}
fn site(
seq: &str,
start: usize,
width: usize,
rev: bool,
flank_l: usize,
flank_r: usize,
) -> Option<String> {
let (fa, fb) = if rev {
(flank_r, flank_l)
} else {
(flank_l, flank_r)
};
let a = start.checked_sub(fa)?;
let b = start + width + fb;
if b > seq.len() {
return None;
}
let s = &seq[a..b];
Some(if rev { rc_string(s) } else { s.to_string() })
}
fn with_pieces(sites: &[String], left: usize, right: usize, name: &str) -> Result<Motif> {
if let Some(short) = sites.iter().find(|x| x.len() < left + right) {
return arg_err(format!(
"the site {short} is shorter than its two parts, {left} and {right} letters"
));
}
let parts: Vec<String> = sites
.iter()
.map(|x| format!("{}{}", &x[..left], &x[x.len() - right..]))
.collect();
let strs: Vec<&str> = parts.iter().map(String::as_str).collect();
let opts = CreateOptions {
name: name.to_string(),
..Default::default()
};
let motif = from_strings(&strs, Some(Alphabet::Dna), &opts)?;
let spacers = sites.iter().map(|x| x.len() - left - right);
let (lo, hi) = (
spacers.clone().min().unwrap_or(0),
spacers.max().unwrap_or(0),
);
if hi == 0 {
return Ok(motif);
}
add_gap(&motif, Some(&[left]), &[lo], &[hi])
}
fn ppm(motif: &Motif) -> Result<Matrix> {
Ok(
convert_type(&normalize(motif)?, MotifType::Ppm, None, false)?
.matrix
.clone(),
)
}
fn column_ic(ppm: &Matrix) -> Vec<f64> {
ppm.columns()
.map(|c| {
2.0 + c
.iter()
.map(|&p| p * p.clamp(1e-12, 1.0).log2())
.sum::<f64>()
})
.collect()
}
fn letters_ic(letters: impl Iterator<Item = u8>) -> f64 {
let mut counts = [0.25; 4];
for l in letters {
if let Some(i) = b"ACGT".iter().position(|&x| x == l) {
counts[i] += 1.0;
}
}
let total: f64 = counts.iter().sum();
2.0 + counts
.iter()
.map(|c| {
let p = c / total;
p * p.log2()
})
.sum::<f64>()
}
fn strong_span(ic: &[f64], min_ic: f64) -> (usize, usize) {
let first = ic.iter().position(|&x| x >= min_ic);
let last = ic.iter().rposition(|&x| x >= min_ic);
match (first, last) {
(Some(a), Some(b)) => (a, b + 1),
_ => (0, 0),
}
}
fn ln_poisson_upper(x: u64, mu: f64) -> f64 {
if x == 0 || x as f64 <= mu {
return 0.0;
}
let mu = mu.max(1e-12);
let n = 200 + (4.0 * (x as f64 + mu).sqrt()) as u64;
let terms: Vec<f64> = (x..x + n)
.map(|i| i as f64 * mu.ln() - mu - libm::lgamma(i as f64 + 1.0))
.collect();
let top = terms.iter().cloned().fold(f64::NEG_INFINITY, f64::max);
(top + terms.iter().map(|t| (t - top).exp()).sum::<f64>().ln()).min(0.0)
}
fn dna_text(s: &str) -> String {
s.chars()
.map(|c| {
if c.is_ascii() {
c.to_ascii_uppercase()
} else {
'N'
}
})
.collect()
}
fn n_unique(seqs: &[u32]) -> u64 {
seqs.iter().collect::<HashSet<_>>().len() as u64
}
fn clean(sites: Vec<String>) -> Vec<String> {
sites
.into_iter()
.filter(|x| x.bytes().all(|b| matches!(b, b'A' | b'C' | b'G' | b'T')))
.collect()
}
fn kmer_string(code: u64, k: usize) -> String {
(0..k)
.map(|i| b"ACGT"[((code >> (2 * (k - 1 - i))) & 3) as usize] as char)
.collect()
}
fn rc_string(s: &str) -> String {
s.bytes()
.rev()
.map(|b| match b {
b'A' => 'T',
b'C' => 'G',
b'G' => 'C',
b'T' => 'A',
b'a' => 't',
b'c' => 'g',
b'g' => 'c',
b't' => 'a',
other => other as char,
})
.collect()
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn occurrences_allow_one_mismatch() {
let seqs = vec![
"TTAGGTCAGGAGGTCATT".to_string(),
"AGGACAGGAGGTCA".to_string(),
];
let exact = occurrences(&seqs, "AGGTCA", "AGGTCA", 1, 5, false, false);
assert_eq!(exact, vec![(0, 2, 2, false)]);
let one = occurrences(&seqs, "AGGTCA", "AGGTCA", 1, 5, false, true);
assert_eq!(one, vec![(0, 2, 2, false), (1, 0, 2, false)]);
}
#[test]
fn sites_and_pieces() {
assert_eq!(site("AACGTTT", 2, 3, false, 1, 1).as_deref(), Some("ACGTT"));
assert_eq!(site("AACGTTT", 2, 3, true, 1, 1).as_deref(), Some("AACGT"));
assert_eq!(site("AACGTTT", 0, 3, false, 1, 1), None);
let sites = ["TGACAAGTCA", "TGACAGTCA"].map(String::from);
let m = with_pieces(&sites, 4, 4, "m").unwrap();
assert_eq!(
(m.gap.gaploc[0], m.gap.mingap[0], m.gap.maxgap[0]),
(4, 1, 2)
);
}
#[test]
fn poisson_tail() {
assert!((ln_poisson_upper(2, 1.0) - (1.0 - 2.0 * (-1.0f64).exp()).ln()).abs() < 1e-9);
assert_eq!(ln_poisson_upper(0, 3.0), 0.0);
assert_eq!(ln_poisson_upper(50, 500.0), 0.0);
assert_eq!(ln_poisson_upper(10, 1000.0), 0.0);
}
}