1use rayon::prelude::*;
2use statrs::distribution::{ContinuousCDF, FisherSnedecor};
3
4use crate::adjustment::{PAdjustMethod, adjust_pvalues};
5use crate::{CompositionError, Grouping, LabeledMatrix, Result};
6
7#[derive(Clone, Debug)]
8pub struct AncomOptions {
9 pub alpha: f64,
10 pub tau: f64,
11 pub theta: f64,
12 pub adjustment: PAdjustMethod,
13 pub percentiles: Vec<f64>,
14 pub max_dense_cells: usize,
15}
16
17impl Default for AncomOptions {
18 fn default() -> Self {
19 Self {
20 alpha: 0.05,
21 tau: 0.02,
22 theta: 0.1,
23 adjustment: PAdjustMethod::Holm,
24 percentiles: vec![0.0, 25.0, 50.0, 75.0, 100.0],
25 max_dense_cells: crate::DEFAULT_MAX_DENSE_CELLS,
26 }
27 }
28}
29
30#[derive(Clone, Debug, PartialEq, Eq)]
31pub struct AncomEntry {
32 pub component: String,
33 pub w: usize,
34 pub significant: bool,
35}
36
37#[derive(Clone, Debug, PartialEq)]
38pub struct PercentileEntry {
39 pub component: String,
40 pub group: String,
41 pub percentile: f64,
42 pub value: f64,
43}
44
45#[derive(Clone, Debug, PartialEq)]
46pub struct AncomResult {
47 entries: Vec<AncomEntry>,
48 percentiles: Vec<PercentileEntry>,
49 degenerate_pairs: usize,
50}
51
52impl AncomResult {
53 #[must_use]
54 pub fn entries(&self) -> &[AncomEntry] {
55 &self.entries
56 }
57
58 #[must_use]
59 pub fn percentiles(&self) -> &[PercentileEntry] {
60 &self.percentiles
61 }
62
63 #[must_use]
64 pub const fn degenerate_pairs(&self) -> usize {
65 self.degenerate_pairs
66 }
67}
68
69pub fn ancom(
70 matrix: &LabeledMatrix,
71 grouping: &Grouping,
72 options: &AncomOptions,
73) -> Result<AncomResult> {
74 validate_options(options)?;
75 validate_positive_matrix(matrix)?;
76 let labels = grouping.align(matrix)?;
77 let mut group_names = labels.clone();
78 group_names.sort_unstable();
79 group_names.dedup();
80 if group_names.len() < 2 || group_names.len() == matrix.sample_count() {
81 return Err(CompositionError::InvalidGrouping);
82 }
83 let mut groups = vec![Vec::new(); group_names.len()];
84 for (row, label) in labels.iter().enumerate() {
85 groups[group_names.binary_search(label).unwrap()].push(row);
86 }
87
88 let components = matrix.component_count();
89 let mut pvalue_matrix = crate::limits::dense_vec(
90 "ANCOM p-value matrix",
91 components,
92 components,
93 options.max_dense_cells,
94 Some(0.0),
95 )?;
96 let pairs: Vec<(usize, usize)> = (0..components)
97 .flat_map(|left| ((left + 1)..components).map(move |right| (left, right)))
98 .collect();
99 let pvalues: Vec<Option<f64>> = pairs
100 .par_iter()
101 .map(|&(left, right)| one_way_log_ratio(matrix, &groups, left, right))
102 .collect::<Result<Vec<_>>>()?;
103 let degenerate_pairs = pvalues.iter().filter(|value| value.is_none()).count();
104 for (&(left, right), value) in pairs.iter().zip(pvalues) {
105 pvalue_matrix[left * components + right] = value;
106 pvalue_matrix[right * components + left] = value;
107 }
108 let mut w = Vec::with_capacity(components);
109 for row in 0..components {
110 let mut adjusted = adjust_pvalues(
111 &pvalue_matrix[row * components..(row + 1) * components],
112 options.adjustment,
113 )?;
114 adjusted[row] = Some(1.0);
115 w.push(
116 adjusted
117 .iter()
118 .filter(|value| value.is_some_and(|value| value < options.alpha))
119 .count(),
120 );
121 }
122 let significant = detect(&w, components, options.tau, options.theta);
123 let entries = matrix
124 .components()
125 .iter()
126 .zip(w)
127 .zip(significant)
128 .map(|((component, w), significant)| AncomEntry {
129 component: component.clone(),
130 w,
131 significant,
132 })
133 .collect();
134 let percentiles = calculate_percentiles(matrix, &group_names, &groups, &options.percentiles);
135 Ok(AncomResult {
136 entries,
137 percentiles,
138 degenerate_pairs,
139 })
140}
141
142fn validate_options(options: &AncomOptions) -> Result<()> {
143 for (name, value) in [
144 ("alpha", options.alpha),
145 ("tau", options.tau),
146 ("theta", options.theta),
147 ] {
148 if !(value.is_finite() && 0.0 < value && value < 1.0) {
149 return Err(CompositionError::InvalidParameter {
150 name,
151 requirement: "strictly between zero and one",
152 value,
153 });
154 }
155 }
156 let mut percentiles = options.percentiles.clone();
157 percentiles.sort_by(f64::total_cmp);
158 for (index, &value) in percentiles.iter().enumerate() {
159 if !value.is_finite() || !(0.0..=100.0).contains(&value) {
160 return Err(CompositionError::InvalidParameter {
161 name: "percentile",
162 requirement: "between zero and one hundred",
163 value,
164 });
165 }
166 if index > 0 && value == percentiles[index - 1] {
167 return Err(CompositionError::InvalidParameter {
168 name: "percentile",
169 requirement: "unique",
170 value,
171 });
172 }
173 }
174 Ok(())
175}
176
177fn validate_positive_matrix(matrix: &LabeledMatrix) -> Result<()> {
178 for (row, values) in matrix.rows().enumerate() {
179 for (column, &value) in values.iter().enumerate() {
180 if !value.is_finite() {
181 return Err(CompositionError::NonFinite {
182 sample: matrix.samples()[row].clone(),
183 component: matrix.components()[column].clone(),
184 value,
185 });
186 }
187 if value <= 0.0 {
188 return Err(CompositionError::InvalidComponent {
189 sample: matrix.samples()[row].clone(),
190 component: matrix.components()[column].clone(),
191 value,
192 requirement: "strictly positive for ANCOM",
193 });
194 }
195 }
196 }
197 Ok(())
198}
199
200fn one_way_log_ratio(
201 matrix: &LabeledMatrix,
202 groups: &[Vec<usize>],
203 left: usize,
204 right: usize,
205) -> Result<Option<f64>> {
206 let width = matrix.component_count();
207 let total = groups.iter().map(Vec::len).sum::<usize>();
208 let mut grand_sum = 0.0;
209 let mut group_sums = Vec::with_capacity(groups.len());
210 for rows in groups {
211 let sum = rows
212 .iter()
213 .map(|&row| {
214 let values = matrix.row(row).unwrap();
215 values[left].ln() - values[right].ln()
216 })
217 .sum::<f64>();
218 grand_sum += sum;
219 group_sums.push(sum);
220 }
221 let grand_mean = grand_sum / total as f64;
222 let mut between = 0.0;
223 let mut within = 0.0;
224 for (rows, sum) in groups.iter().zip(group_sums) {
225 let mean = sum / rows.len() as f64;
226 between += rows.len() as f64 * (mean - grand_mean).powi(2);
227 within += rows
228 .iter()
229 .map(|&row| {
230 let values = &matrix.values()[row * width..(row + 1) * width];
231 let ratio = values[left].ln() - values[right].ln();
232 (ratio - mean).powi(2)
233 })
234 .sum::<f64>();
235 }
236 let tolerance =
237 64.0 * f64::EPSILON * (grand_mean.powi(2) * total as f64 + between + within).max(1.0);
238 if within <= tolerance {
239 return Ok(if between <= tolerance {
240 None
241 } else {
242 Some(0.0)
243 });
244 }
245 let between_df = (groups.len() - 1) as f64;
246 let within_df = (total - groups.len()) as f64;
247 let statistic = (between / between_df) / (within / within_df);
248 let distribution = FisherSnedecor::new(between_df, within_df)
249 .map_err(|error| CompositionError::Statistics(error.to_string()))?;
250 Ok(Some(distribution.sf(statistic).clamp(0.0, 1.0)))
251}
252
253fn detect(w: &[usize], components: usize, tau: f64, theta: f64) -> Vec<bool> {
254 let maximum = w.iter().copied().max().unwrap_or(0) as f64;
255 let start = maximum / components as f64;
256 if start < theta {
257 return vec![false; w.len()];
258 }
259 let cutoffs: [f64; 5] = std::array::from_fn(|index| start - (0.05 + 0.05 * index as f64));
260 let proportions: [f64; 5] = std::array::from_fn(|index| {
261 let threshold = components as f64 * cutoffs[index];
262 w.iter().filter(|&&value| value as f64 > threshold).count() as f64 / w.len() as f64
263 });
264 let differences: [f64; 4] =
265 std::array::from_fn(|index| (proportions[index] - proportions[index + 1]).abs());
266 let cutoff = if differences[0] < tau && differences[1] < tau && differences[2] < tau {
267 cutoffs[1]
268 } else if differences[0] >= tau && differences[1] < tau && differences[2] < tau {
269 cutoffs[2]
270 } else if differences[1] >= tau && differences[2] < tau && differences[3] < tau {
271 cutoffs[3]
272 } else {
273 cutoffs[4]
274 };
275 let threshold = cutoff * components as f64;
276 w.iter().map(|&value| value as f64 >= threshold).collect()
277}
278
279fn calculate_percentiles(
280 matrix: &LabeledMatrix,
281 group_names: &[String],
282 groups: &[Vec<usize>],
283 requested: &[f64],
284) -> Vec<PercentileEntry> {
285 let mut percentiles = requested.to_vec();
286 percentiles.sort_by(f64::total_cmp);
287 let mut output =
288 Vec::with_capacity(matrix.component_count() * group_names.len() * percentiles.len());
289 for component in 0..matrix.component_count() {
290 for (group, rows) in group_names.iter().zip(groups) {
291 let mut values: Vec<f64> = rows
292 .iter()
293 .map(|&row| matrix.values()[row * matrix.component_count() + component])
294 .collect();
295 values.sort_by(f64::total_cmp);
296 for &percentile in &percentiles {
297 output.push(PercentileEntry {
298 component: matrix.components()[component].clone(),
299 group: group.clone(),
300 percentile,
301 value: percentile_linear(&values, percentile),
302 });
303 }
304 }
305 }
306 output
307}
308
309fn percentile_linear(values: &[f64], percentile: f64) -> f64 {
310 let position = percentile / 100.0 * (values.len() - 1) as f64;
311 let lower = position.floor() as usize;
312 let upper = position.ceil() as usize;
313 if lower == upper {
314 values[lower]
315 } else {
316 values[lower] + (values[upper] - values[lower]) * (position - lower as f64)
317 }
318}
319
320#[cfg(test)]
321mod tests {
322 use super::*;
323
324 fn doc_example() -> (LabeledMatrix, Grouping) {
325 let matrix = LabeledMatrix::new(
326 ["s1", "s2", "s3", "s4", "s5", "s6"]
327 .map(str::to_owned)
328 .to_vec(),
329 ["b1", "b2", "b3", "b4", "b5", "b6", "b7"]
330 .map(str::to_owned)
331 .to_vec(),
332 vec![
333 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,
334 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,
335 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,
336 ],
337 )
338 .unwrap();
339 let grouping = Grouping::new(
340 [
341 ("s1", "treatment"),
342 ("s2", "treatment"),
343 ("s3", "treatment"),
344 ("s4", "placebo"),
345 ("s5", "placebo"),
346 ("s6", "placebo"),
347 ]
348 .map(|(sample, group)| (sample.to_owned(), group.to_owned())),
349 )
350 .unwrap();
351 (matrix, grouping)
352 }
353
354 #[test]
355 fn matches_skbio_ancom_doc_example() {
356 let (matrix, grouping) = doc_example();
357 let result = ancom(&matrix, &grouping, &AncomOptions::default()).unwrap();
358 assert_eq!(
359 result
360 .entries()
361 .iter()
362 .map(|entry| entry.w)
363 .collect::<Vec<_>>(),
364 [0, 4, 0, 1, 1, 0, 1]
365 );
366 assert_eq!(
367 result
368 .entries()
369 .iter()
370 .map(|entry| entry.significant)
371 .collect::<Vec<_>>(),
372 [false, true, false, false, false, false, false]
373 );
374 }
375
376 #[test]
377 fn percentiles_match_linear_interpolation() {
378 let (matrix, grouping) = doc_example();
379 let result = ancom(&matrix, &grouping, &AncomOptions::default()).unwrap();
380 let median = result
381 .percentiles()
382 .iter()
383 .find(|entry| {
384 entry.component == "b2" && entry.group == "placebo" && entry.percentile == 50.0
385 })
386 .unwrap();
387 let upper_quartile = result
388 .percentiles()
389 .iter()
390 .find(|entry| {
391 entry.component == "b2" && entry.group == "placebo" && entry.percentile == 75.0
392 })
393 .unwrap();
394 assert_eq!(median.value, 21.0);
395 assert_eq!(upper_quartile.value, 21.5);
396 }
397
398 #[test]
399 fn degenerate_pairs_are_explicitly_non_rejections() {
400 let matrix = LabeledMatrix::new(
401 ["s1", "s2", "s3", "s4"].map(str::to_owned).to_vec(),
402 ["a", "b", "c"].map(str::to_owned).to_vec(),
403 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],
404 )
405 .unwrap();
406 let grouping = Grouping::new([
407 ("s1".into(), "x".into()),
408 ("s2".into(), "x".into()),
409 ("s3".into(), "y".into()),
410 ("s4".into(), "y".into()),
411 ])
412 .unwrap();
413 let result = ancom(&matrix, &grouping, &AncomOptions::default()).unwrap();
414 assert_eq!(result.degenerate_pairs(), 3);
415 assert!(
416 result
417 .entries()
418 .iter()
419 .all(|entry| entry.w == 0 && !entry.significant)
420 );
421 }
422
423 #[test]
424 fn dense_limit_fails_before_pairwise_tests() {
425 let (matrix, grouping) = doc_example();
426 let options = AncomOptions {
427 max_dense_cells: 48,
428 ..AncomOptions::default()
429 };
430 assert!(matches!(
431 ancom(&matrix, &grouping, &options),
432 Err(CompositionError::DenseMatrixTooLarge { .. })
433 ));
434 }
435}