use rayon::prelude::*;
use statrs::distribution::{ContinuousCDF, FisherSnedecor};
use crate::adjustment::{PAdjustMethod, adjust_pvalues};
use crate::{CompositionError, Grouping, LabeledMatrix, Result};
#[derive(Clone, Debug)]
pub struct AncomOptions {
pub alpha: f64,
pub tau: f64,
pub theta: f64,
pub adjustment: PAdjustMethod,
pub percentiles: Vec<f64>,
pub max_dense_cells: usize,
}
impl Default for AncomOptions {
fn default() -> Self {
Self {
alpha: 0.05,
tau: 0.02,
theta: 0.1,
adjustment: PAdjustMethod::Holm,
percentiles: vec![0.0, 25.0, 50.0, 75.0, 100.0],
max_dense_cells: crate::DEFAULT_MAX_DENSE_CELLS,
}
}
}
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct AncomEntry {
pub component: String,
pub w: usize,
pub significant: bool,
}
#[derive(Clone, Debug, PartialEq)]
pub struct PercentileEntry {
pub component: String,
pub group: String,
pub percentile: f64,
pub value: f64,
}
#[derive(Clone, Debug, PartialEq)]
pub struct AncomResult {
entries: Vec<AncomEntry>,
percentiles: Vec<PercentileEntry>,
degenerate_pairs: usize,
}
impl AncomResult {
#[must_use]
pub fn entries(&self) -> &[AncomEntry] {
&self.entries
}
#[must_use]
pub fn percentiles(&self) -> &[PercentileEntry] {
&self.percentiles
}
#[must_use]
pub const fn degenerate_pairs(&self) -> usize {
self.degenerate_pairs
}
}
pub fn ancom(
matrix: &LabeledMatrix,
grouping: &Grouping,
options: &AncomOptions,
) -> Result<AncomResult> {
validate_options(options)?;
validate_positive_matrix(matrix)?;
let labels = grouping.align(matrix)?;
let mut group_names = labels.clone();
group_names.sort_unstable();
group_names.dedup();
if group_names.len() < 2 || group_names.len() == matrix.sample_count() {
return Err(CompositionError::InvalidGrouping);
}
let mut groups = vec![Vec::new(); group_names.len()];
for (row, label) in labels.iter().enumerate() {
groups[group_names.binary_search(label).unwrap()].push(row);
}
let components = matrix.component_count();
let mut pvalue_matrix = crate::limits::dense_vec(
"ANCOM p-value matrix",
components,
components,
options.max_dense_cells,
Some(0.0),
)?;
let pairs: Vec<(usize, usize)> = (0..components)
.flat_map(|left| ((left + 1)..components).map(move |right| (left, right)))
.collect();
let pvalues: Vec<Option<f64>> = pairs
.par_iter()
.map(|&(left, right)| one_way_log_ratio(matrix, &groups, left, right))
.collect::<Result<Vec<_>>>()?;
let degenerate_pairs = pvalues.iter().filter(|value| value.is_none()).count();
for (&(left, right), value) in pairs.iter().zip(pvalues) {
pvalue_matrix[left * components + right] = value;
pvalue_matrix[right * components + left] = value;
}
let mut w = Vec::with_capacity(components);
for row in 0..components {
let mut adjusted = adjust_pvalues(
&pvalue_matrix[row * components..(row + 1) * components],
options.adjustment,
)?;
adjusted[row] = Some(1.0);
w.push(
adjusted
.iter()
.filter(|value| value.is_some_and(|value| value < options.alpha))
.count(),
);
}
let significant = detect(&w, components, options.tau, options.theta);
let entries = matrix
.components()
.iter()
.zip(w)
.zip(significant)
.map(|((component, w), significant)| AncomEntry {
component: component.clone(),
w,
significant,
})
.collect();
let percentiles = calculate_percentiles(matrix, &group_names, &groups, &options.percentiles);
Ok(AncomResult {
entries,
percentiles,
degenerate_pairs,
})
}
fn validate_options(options: &AncomOptions) -> Result<()> {
for (name, value) in [
("alpha", options.alpha),
("tau", options.tau),
("theta", options.theta),
] {
if !(value.is_finite() && 0.0 < value && value < 1.0) {
return Err(CompositionError::InvalidParameter {
name,
requirement: "strictly between zero and one",
value,
});
}
}
let mut percentiles = options.percentiles.clone();
percentiles.sort_by(f64::total_cmp);
for (index, &value) in percentiles.iter().enumerate() {
if !value.is_finite() || !(0.0..=100.0).contains(&value) {
return Err(CompositionError::InvalidParameter {
name: "percentile",
requirement: "between zero and one hundred",
value,
});
}
if index > 0 && value == percentiles[index - 1] {
return Err(CompositionError::InvalidParameter {
name: "percentile",
requirement: "unique",
value,
});
}
}
Ok(())
}
fn validate_positive_matrix(matrix: &LabeledMatrix) -> Result<()> {
for (row, values) in matrix.rows().enumerate() {
for (column, &value) in values.iter().enumerate() {
if !value.is_finite() {
return Err(CompositionError::NonFinite {
sample: matrix.samples()[row].clone(),
component: matrix.components()[column].clone(),
value,
});
}
if value <= 0.0 {
return Err(CompositionError::InvalidComponent {
sample: matrix.samples()[row].clone(),
component: matrix.components()[column].clone(),
value,
requirement: "strictly positive for ANCOM",
});
}
}
}
Ok(())
}
fn one_way_log_ratio(
matrix: &LabeledMatrix,
groups: &[Vec<usize>],
left: usize,
right: usize,
) -> Result<Option<f64>> {
let width = matrix.component_count();
let total = groups.iter().map(Vec::len).sum::<usize>();
let mut grand_sum = 0.0;
let mut group_sums = Vec::with_capacity(groups.len());
for rows in groups {
let sum = rows
.iter()
.map(|&row| {
let values = matrix.row(row).unwrap();
values[left].ln() - values[right].ln()
})
.sum::<f64>();
grand_sum += sum;
group_sums.push(sum);
}
let grand_mean = grand_sum / total as f64;
let mut between = 0.0;
let mut within = 0.0;
for (rows, sum) in groups.iter().zip(group_sums) {
let mean = sum / rows.len() as f64;
between += rows.len() as f64 * (mean - grand_mean).powi(2);
within += rows
.iter()
.map(|&row| {
let values = &matrix.values()[row * width..(row + 1) * width];
let ratio = values[left].ln() - values[right].ln();
(ratio - mean).powi(2)
})
.sum::<f64>();
}
let tolerance =
64.0 * f64::EPSILON * (grand_mean.powi(2) * total as f64 + between + within).max(1.0);
if within <= tolerance {
return Ok(if between <= tolerance {
None
} else {
Some(0.0)
});
}
let between_df = (groups.len() - 1) as f64;
let within_df = (total - groups.len()) as f64;
let statistic = (between / between_df) / (within / within_df);
let distribution = FisherSnedecor::new(between_df, within_df)
.map_err(|error| CompositionError::Statistics(error.to_string()))?;
Ok(Some(distribution.sf(statistic).clamp(0.0, 1.0)))
}
fn detect(w: &[usize], components: usize, tau: f64, theta: f64) -> Vec<bool> {
let maximum = w.iter().copied().max().unwrap_or(0) as f64;
let start = maximum / components as f64;
if start < theta {
return vec![false; w.len()];
}
let cutoffs: [f64; 5] = std::array::from_fn(|index| start - (0.05 + 0.05 * index as f64));
let proportions: [f64; 5] = std::array::from_fn(|index| {
let threshold = components as f64 * cutoffs[index];
w.iter().filter(|&&value| value as f64 > threshold).count() as f64 / w.len() as f64
});
let differences: [f64; 4] =
std::array::from_fn(|index| (proportions[index] - proportions[index + 1]).abs());
let cutoff = if differences[0] < tau && differences[1] < tau && differences[2] < tau {
cutoffs[1]
} else if differences[0] >= tau && differences[1] < tau && differences[2] < tau {
cutoffs[2]
} else if differences[1] >= tau && differences[2] < tau && differences[3] < tau {
cutoffs[3]
} else {
cutoffs[4]
};
let threshold = cutoff * components as f64;
w.iter().map(|&value| value as f64 >= threshold).collect()
}
fn calculate_percentiles(
matrix: &LabeledMatrix,
group_names: &[String],
groups: &[Vec<usize>],
requested: &[f64],
) -> Vec<PercentileEntry> {
let mut percentiles = requested.to_vec();
percentiles.sort_by(f64::total_cmp);
let mut output =
Vec::with_capacity(matrix.component_count() * group_names.len() * percentiles.len());
for component in 0..matrix.component_count() {
for (group, rows) in group_names.iter().zip(groups) {
let mut values: Vec<f64> = rows
.iter()
.map(|&row| matrix.values()[row * matrix.component_count() + component])
.collect();
values.sort_by(f64::total_cmp);
for &percentile in &percentiles {
output.push(PercentileEntry {
component: matrix.components()[component].clone(),
group: group.clone(),
percentile,
value: percentile_linear(&values, percentile),
});
}
}
}
output
}
fn percentile_linear(values: &[f64], percentile: f64) -> f64 {
let position = percentile / 100.0 * (values.len() - 1) as f64;
let lower = position.floor() as usize;
let upper = position.ceil() as usize;
if lower == upper {
values[lower]
} else {
values[lower] + (values[upper] - values[lower]) * (position - lower as f64)
}
}
#[cfg(test)]
mod tests {
use super::*;
fn doc_example() -> (LabeledMatrix, Grouping) {
let matrix = LabeledMatrix::new(
["s1", "s2", "s3", "s4", "s5", "s6"]
.map(str::to_owned)
.to_vec(),
["b1", "b2", "b3", "b4", "b5", "b6", "b7"]
.map(str::to_owned)
.to_vec(),
vec![
12.0, 11.0, 10.0, 10.0, 10.0, 10.0, 10.0, 9.0, 11.0, 12.0, 10.0, 10.0, 10.0, 10.0,
1.0, 11.0, 10.0, 11.0, 10.0, 5.0, 9.0, 22.0, 21.0, 9.0, 10.0, 10.0, 10.0, 10.0,
20.0, 22.0, 10.0, 10.0, 13.0, 10.0, 10.0, 23.0, 21.0, 14.0, 10.0, 10.0, 10.0, 10.0,
],
)
.unwrap();
let grouping = Grouping::new(
[
("s1", "treatment"),
("s2", "treatment"),
("s3", "treatment"),
("s4", "placebo"),
("s5", "placebo"),
("s6", "placebo"),
]
.map(|(sample, group)| (sample.to_owned(), group.to_owned())),
)
.unwrap();
(matrix, grouping)
}
#[test]
fn matches_skbio_ancom_doc_example() {
let (matrix, grouping) = doc_example();
let result = ancom(&matrix, &grouping, &AncomOptions::default()).unwrap();
assert_eq!(
result
.entries()
.iter()
.map(|entry| entry.w)
.collect::<Vec<_>>(),
[0, 4, 0, 1, 1, 0, 1]
);
assert_eq!(
result
.entries()
.iter()
.map(|entry| entry.significant)
.collect::<Vec<_>>(),
[false, true, false, false, false, false, false]
);
}
#[test]
fn percentiles_match_linear_interpolation() {
let (matrix, grouping) = doc_example();
let result = ancom(&matrix, &grouping, &AncomOptions::default()).unwrap();
let median = result
.percentiles()
.iter()
.find(|entry| {
entry.component == "b2" && entry.group == "placebo" && entry.percentile == 50.0
})
.unwrap();
let upper_quartile = result
.percentiles()
.iter()
.find(|entry| {
entry.component == "b2" && entry.group == "placebo" && entry.percentile == 75.0
})
.unwrap();
assert_eq!(median.value, 21.0);
assert_eq!(upper_quartile.value, 21.5);
}
#[test]
fn degenerate_pairs_are_explicitly_non_rejections() {
let matrix = LabeledMatrix::new(
["s1", "s2", "s3", "s4"].map(str::to_owned).to_vec(),
["a", "b", "c"].map(str::to_owned).to_vec(),
vec![1.0, 2.0, 4.0, 2.0, 4.0, 8.0, 3.0, 6.0, 12.0, 4.0, 8.0, 16.0],
)
.unwrap();
let grouping = Grouping::new([
("s1".into(), "x".into()),
("s2".into(), "x".into()),
("s3".into(), "y".into()),
("s4".into(), "y".into()),
])
.unwrap();
let result = ancom(&matrix, &grouping, &AncomOptions::default()).unwrap();
assert_eq!(result.degenerate_pairs(), 3);
assert!(
result
.entries()
.iter()
.all(|entry| entry.w == 0 && !entry.significant)
);
}
#[test]
fn dense_limit_fails_before_pairwise_tests() {
let (matrix, grouping) = doc_example();
let options = AncomOptions {
max_dense_cells: 48,
..AncomOptions::default()
};
assert!(matches!(
ancom(&matrix, &grouping, &options),
Err(CompositionError::DenseMatrixTooLarge { .. })
));
}
}