use crate::alphabet::Alphabet;
use crate::cluster::{Linkage, hclust};
use crate::compare::{CompareOptions, NullModel, align, compare_matrix};
use crate::convert::convert_type;
use crate::create::{CreateOptions, from_typed_matrix};
use crate::error::{Result, arg_err};
use crate::matrix::Matrix;
use crate::motif::{Motif, MotifType, Strand};
use crate::similarity::{CwmCompareOptions, CwmMetric, align_cwm_pair, cwm_similarity_matrix};
#[derive(Debug, Clone, PartialEq)]
pub struct MergeOptions {
pub min_overlap: usize,
pub rc: bool,
pub name: Option<String>,
pub weighted: bool,
pub nthreads: usize,
}
impl Default for MergeOptions {
fn default() -> Self {
MergeOptions {
min_overlap: 5,
rc: true,
name: None,
weighted: false,
nthreads: 1,
}
}
}
fn shared_alphabet(motifs: &[Motif]) -> Result<Alphabet> {
let Some(first) = motifs.first() else {
return arg_err("no motifs given");
};
if motifs.iter().any(|m| m.alphabet != first.alphabet) {
return arg_err("all motifs must share the same alphabet");
}
Ok(first.alphabet.clone())
}
pub fn merge_motifs(motifs: &[Motif], opts: &MergeOptions) -> Result<Motif> {
merge_motifs_detailed(motifs, opts).map(|m| m.motif)
}
#[derive(Debug, Clone, PartialEq)]
#[non_exhaustive]
pub struct MergedMotif {
pub motif: Motif,
pub used: Vec<usize>,
}
pub fn merge_motifs_detailed(motifs: &[Motif], opts: &MergeOptions) -> Result<MergedMotif> {
let alphabet = shared_alphabet(motifs)?;
if motifs.iter().all(|m| m.motif_type == MotifType::Cwm) {
return merge_cwms(motifs, alphabet, opts);
}
let nl = alphabet.len();
if motifs.len() == 1 {
let mut p = convert_type(&motifs[0], MotifType::Ppm, None, false)?.into_parts();
if let Some(n) = &opts.name {
p.name = n.clone();
}
return Ok(MergedMotif {
motif: Motif::from_parts(p)?,
used: vec![0],
});
}
let ppms: Vec<Motif> = motifs
.iter()
.map(|m| convert_type(m, MotifType::Ppm, None, false))
.collect::<Result<_>>()?;
let nsites: Vec<f64> = ppms
.iter()
.map(|m| m.nsites.filter(|n| *n > 0.0).unwrap_or(1.0))
.collect();
let ic: Vec<f64> = ppms.iter().map(|m| m.icscore).collect();
let mut anchor = 0;
for (i, &v) in ic.iter().enumerate().skip(1) {
if v > ic[anchor] + 1e-9 * ic[anchor].abs().max(1.0) {
anchor = i;
}
}
let pairs: Vec<(usize, usize)> = (0..ppms.len()).map(|i| (anchor, i)).collect();
let copts = CompareOptions {
min_overlap: opts.min_overlap,
rc: opts.rc,
nthreads: opts.nthreads,
..Default::default()
};
let al = align(&ppms, &pairs, &copts)?;
let w_anchor = ppms[anchor].width() as i64;
let mut used: Vec<(usize, Matrix, i64)> = Vec::new();
for (i, m) in ppms.iter().enumerate() {
if i == anchor {
used.push((i, m.matrix.clone(), 0));
continue;
}
let a = &al[i];
let len = a.overlap as i64;
if a.overlap < opts.min_overlap.min(m.width()).min(ppms[anchor].width()) {
continue;
}
let t_start = (-a.offset).max(0);
let w = m.width() as i64;
if a.strand == Strand::Minus {
let q_start = w_anchor - a.query_start as i64 - len;
let t_start_oriented = w - t_start - len;
used.push((i, m.matrix.reversed(), q_start - t_start_oriented));
} else {
used.push((i, m.matrix.clone(), a.query_start as i64 - t_start));
}
}
let lo = used.iter().map(|u| u.2).min().unwrap();
let hi = used.iter().map(|u| u.2 + u.1.ncol() as i64).max().unwrap();
let width = (hi - lo) as usize;
let weights: Vec<f64> = used
.iter()
.map(|u| if opts.weighted { nsites[u.0] } else { 1.0 })
.collect();
let mut cols = Vec::with_capacity(width);
for p in 0..width as i64 {
let frame = lo + p;
let mut sum = vec![0.0; nl];
let mut wsum = 0.0;
for (u, &w) in used.iter().zip(&weights) {
let local = frame - u.2;
if local < 0 || local >= u.1.ncol() as i64 {
continue;
}
for (s, v) in sum.iter_mut().zip(u.1.col(local as usize)) {
*s += w * v;
}
wsum += w;
}
cols.push(if wsum == 0.0 {
vec![1.0 / nl as f64; nl]
} else {
sum.iter().map(|s| s / wsum).collect()
});
}
let total_nsites: f64 = used.iter().map(|u| nsites[u.0]).sum();
let mut bkg = vec![0.0; nl];
for u in &used {
for (b, v) in bkg.iter_mut().zip(&ppms[u.0].bkg) {
*b += v;
}
}
let bkg: Vec<f64> = bkg.iter().map(|b| b / used.len() as f64).collect();
let name = opts.name.clone().unwrap_or_else(|| {
let names: Vec<&str> = used.iter().map(|u| ppms[u.0].name.as_str()).collect();
format!("merged_{}", names.join("+"))
});
let copts = CreateOptions {
motif_type: MotifType::Ppm,
name,
nsites: Some(total_nsites),
bkg: Some(bkg),
pseudocount: ppms[anchor].pseudocount,
..Default::default()
};
let merged = from_typed_matrix(
Matrix::from_columns(&cols)?,
None,
Some(alphabet),
MotifType::Ppm,
&copts,
)?;
let mut used_idx: Vec<usize> = used.iter().map(|u| u.0).collect();
used_idx.sort_unstable();
Ok(MergedMotif {
motif: merged,
used: used_idx,
})
}
fn merge_cwms(motifs: &[Motif], alphabet: Alphabet, opts: &MergeOptions) -> Result<MergedMotif> {
let nl = alphabet.len();
let nsites: Vec<f64> = motifs
.iter()
.map(|m| m.nsites.filter(|n| *n > 0.0).unwrap_or(1.0))
.collect();
let mass: Vec<f64> = motifs
.iter()
.map(|m| m.matrix.as_slice().iter().map(|v| v.abs()).sum())
.collect();
let mut anchor = 0;
for (i, &v) in mass.iter().enumerate().skip(1) {
if v > mass[anchor] + 1e-9 * mass[anchor].abs().max(1.0) {
anchor = i;
}
}
let copts = CwmCompareOptions {
min_overlap: opts.min_overlap,
rc: opts.rc,
nthreads: opts.nthreads,
..Default::default()
};
let mut used: Vec<(usize, Matrix, i64)> = Vec::new();
for (i, m) in motifs.iter().enumerate() {
if i == anchor {
used.push((i, m.matrix.clone(), 0));
continue;
}
let a = align_cwm_pair(m, &motifs[anchor], &copts)?;
if a.overlap < opts.min_overlap.min(m.width()).min(motifs[anchor].width()) {
continue;
}
let matrix = if a.strand == Strand::Minus {
m.matrix.reversed()
} else {
m.matrix.clone()
};
used.push((i, matrix, -a.offset));
}
let lo = used.iter().map(|u| u.2).min().unwrap();
let hi = used.iter().map(|u| u.2 + u.1.ncol() as i64).max().unwrap();
let mut cols = Vec::with_capacity((hi - lo) as usize);
for frame in lo..hi {
let mut sum = vec![0.0; nl];
let mut wsum = 0.0;
for u in &used {
let local = frame - u.2;
if local < 0 || local >= u.1.ncol() as i64 {
continue;
}
let w = if opts.weighted { nsites[u.0] } else { 1.0 };
for (s, v) in sum.iter_mut().zip(u.1.col(local as usize)) {
*s += w * v;
}
wsum += w;
}
cols.push(if wsum == 0.0 {
sum
} else {
sum.iter().map(|s| s / wsum).collect()
});
}
let mut bkg = vec![0.0; nl];
for u in &used {
for (b, v) in bkg.iter_mut().zip(&motifs[u.0].bkg) {
*b += v / used.len() as f64;
}
}
let name = opts.name.clone().unwrap_or_else(|| {
let names: Vec<&str> = used.iter().map(|u| motifs[u.0].name.as_str()).collect();
format!("merged_{}", names.join("+"))
});
let copts = CreateOptions {
motif_type: MotifType::Cwm,
name,
nsites: Some(used.iter().map(|u| nsites[u.0]).sum()),
bkg: Some(bkg),
..Default::default()
};
let merged = from_typed_matrix(
Matrix::from_columns(&cols)?,
None,
Some(alphabet),
MotifType::Cwm,
&copts,
)?;
let mut used_idx: Vec<usize> = used.iter().map(|u| u.0).collect();
used_idx.sort_unstable();
Ok(MergedMotif {
motif: merged,
used: used_idx,
})
}
#[derive(Debug, Clone, PartialEq)]
#[non_exhaustive]
pub struct MergedClusters {
pub clusters: Vec<usize>,
pub motifs: Vec<Motif>,
pub warnings: Vec<String>,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
#[non_exhaustive]
pub enum MergeLinkage {
#[default]
Single,
Complete,
}
impl MergeLinkage {
pub fn as_str(&self) -> &'static str {
match self {
MergeLinkage::Single => "single",
MergeLinkage::Complete => "complete",
}
}
}
impl std::str::FromStr for MergeLinkage {
type Err = crate::error::Error;
fn from_str(s: &str) -> Result<Self> {
match s {
"single" => Ok(MergeLinkage::Single),
"complete" => Ok(MergeLinkage::Complete),
_ => arg_err(format!("linkage must be 'single' or 'complete', not '{s}'")),
}
}
}
#[derive(Debug, Clone, PartialEq)]
pub struct MergeSimilarOptions {
pub qvalue: f64,
pub null: NullModel,
pub min_overlap: usize,
pub rc: bool,
pub bkg: [f64; 4],
pub weighted: bool,
pub cwm_metric: CwmMetric,
pub ignore_sign: bool,
pub min_score: Option<f64>,
pub linkage: MergeLinkage,
pub nthreads: usize,
}
impl Default for MergeSimilarOptions {
fn default() -> Self {
MergeSimilarOptions {
qvalue: 0.01,
null: NullModel::Empirical,
min_overlap: 5,
rc: true,
bkg: [0.25; 4],
weighted: false,
cwm_metric: CwmMetric::Cosine,
ignore_sign: false,
min_score: None,
linkage: MergeLinkage::Single,
nthreads: 1,
}
}
}
#[allow(clippy::needless_range_loop)]
pub fn merge_similar(motifs: &[Motif], opts: &MergeSimilarOptions) -> Result<MergedClusters> {
if motifs.is_empty() {
return Ok(MergedClusters {
clusters: Vec::new(),
motifs: Vec::new(),
warnings: Vec::new(),
});
}
shared_alphabet(motifs)?;
let cwms = motifs.iter().all(|m| m.motif_type == MotifType::Cwm);
if !cwms && !(opts.qvalue > 0.0 && opts.qvalue <= 1.0) {
return arg_err("qvalue must be in (0, 1]");
}
let n = motifs.len();
if n == 1 {
return Ok(MergedClusters {
clusters: vec![0],
motifs: motifs.to_vec(),
warnings: Vec::new(),
});
}
let clusters = if cwms {
cwm_clusters(motifs, opts)?
} else {
qvalue_clusters(motifs, opts)?
};
let n_clusters = clusters.iter().max().map_or(0, |&c| c + 1);
let mut sizes = vec![0usize; n_clusters];
for &c in &clusters {
sizes[c] += 1;
}
let mut warnings = Vec::new();
if let Some((big, &size)) = sizes
.iter()
.enumerate()
.max_by_key(|&(c, &s)| (s, std::cmp::Reverse(c)))
&& size > 2
&& size * 4 > n
{
let advice = match (cwms, opts.linkage) {
(false, MergeLinkage::Single) => "a smaller qvalue or complete linkage",
(false, MergeLinkage::Complete) => "a smaller qvalue",
(true, MergeLinkage::Single) => "a higher min_score or complete linkage",
(true, MergeLinkage::Complete) => "a higher min_score",
};
warnings.push(format!(
"cluster {big} holds {size} of the {n} motifs, which suggests that unlike motifs \
were joined; try {advice} to split it"
));
}
let mopts = MergeOptions {
min_overlap: opts.min_overlap,
rc: opts.rc,
weighted: opts.weighted,
nthreads: opts.nthreads,
name: None,
};
let merged = (0..n_clusters)
.map(|c| {
let members: Vec<Motif> = (0..n)
.filter(|&i| clusters[i] == c)
.map(|i| motifs[i].clone())
.collect();
if members.len() == 1 {
Ok(members.into_iter().next().unwrap())
} else {
merge_motifs(&members, &mopts)
}
})
.collect::<Result<_>>()?;
Ok(MergedClusters {
clusters,
motifs: merged,
warnings,
})
}
fn qvalue_clusters(motifs: &[Motif], opts: &MergeSimilarOptions) -> Result<Vec<usize>> {
let n = motifs.len();
let copts = CompareOptions {
min_overlap: opts.min_overlap,
rc: opts.rc,
null: opts.null,
bkg: opts.bkg,
nthreads: opts.nthreads,
..Default::default()
};
let q = compare_matrix(motifs, &copts, true)?.qvalues;
let link = |i: usize, j: usize| {
let qij = q[i][j].min(q[j][i]);
if qij.is_nan() { f64::INFINITY } else { qij }
};
Ok(match opts.linkage {
MergeLinkage::Single => connected_groups(n, |i, j| link(i, j) <= opts.qvalue),
MergeLinkage::Complete => {
let dist: Vec<Vec<f64>> = (0..n)
.map(|i| {
(0..n)
.map(|j| if i == j { 0.0 } else { link(i, j).min(2.0) })
.collect()
})
.collect();
hclust(&dist, Linkage::Complete)?.cutree_height(opts.qvalue)?
}
})
}
fn cwm_clusters(motifs: &[Motif], opts: &MergeSimilarOptions) -> Result<Vec<usize>> {
let n = motifs.len();
let min_score = opts
.min_score
.unwrap_or_else(|| opts.cwm_metric.default_min_score());
if !min_score.is_finite() {
return arg_err("min_score must be a number");
}
let s = cwm_similarity_matrix(
motifs,
&CwmCompareOptions {
metric: opts.cwm_metric,
ignore_sign: opts.ignore_sign,
min_overlap: opts.min_overlap,
rc: opts.rc,
nthreads: opts.nthreads,
},
)?;
let link = |i: usize, j: usize| {
let v = s[i][j].max(s[j][i]);
if v.is_nan() { f64::NEG_INFINITY } else { v }
};
Ok(match opts.linkage {
MergeLinkage::Single => connected_groups(n, |i, j| link(i, j) >= min_score),
MergeLinkage::Complete => {
let dist: Vec<Vec<f64>> = (0..n)
.map(|i| {
(0..n)
.map(|j| {
if i == j {
0.0
} else {
(1.0 - link(i, j)).clamp(0.0, 3.0)
}
})
.collect()
})
.collect();
hclust(&dist, Linkage::Complete)?.cutree_height(1.0 - min_score)?
}
})
}
fn connected_groups(n: usize, linked: impl Fn(usize, usize) -> bool) -> Vec<usize> {
let mut parent: Vec<usize> = (0..n).collect();
fn find(parent: &mut [usize], mut x: usize) -> usize {
let mut root = x;
while parent[root] != root {
root = parent[root];
}
while parent[x] != root {
let next = parent[x];
parent[x] = root;
x = next;
}
root
}
for i in 0..n {
for j in i + 1..n {
if linked(i, j) {
let (ra, rb) = (find(&mut parent, i), find(&mut parent, j));
if ra != rb {
parent[rb] = ra;
}
}
}
}
let mut seen: Vec<usize> = Vec::new();
(0..n)
.map(|i| {
let r = find(&mut parent, i);
match seen.iter().position(|&s| s == r) {
Some(p) => p,
None => {
seen.push(r);
seen.len() - 1
}
}
})
.collect()
}