rsomics-composition 0.1.0

Compositional-data geometry, transforms, and differential abundance
Documentation
use std::collections::{HashSet, VecDeque};

use rsomics_phylo_tree::Tree;

use crate::{CompositionError, Result};

#[derive(Clone, Debug, PartialEq)]
pub struct Basis {
    components: Vec<String>,
    balances: Vec<String>,
    values: Vec<f64>,
}

impl Basis {
    pub fn new(components: Vec<String>, balances: Vec<String>, values: Vec<f64>) -> Result<Self> {
        validate_names("component", &components)?;
        validate_names("balance", &balances)?;
        let width = components.len();
        if width < 2 {
            return Err(CompositionError::TooFewComponents {
                found: width,
                required: 2,
            });
        }
        if balances.len() != width - 1 || values.len() != balances.len() * width {
            return Err(CompositionError::BasisShape {
                rows: balances.len(),
                columns: values.len().checked_div(balances.len()).unwrap_or(0),
                expected_rows: width - 1,
                expected_columns: width,
            });
        }
        validate_orthonormal(&values, balances.len(), width)?;
        Ok(Self {
            components,
            balances,
            values,
        })
    }

    pub fn default_for(components: Vec<String>) -> Result<Self> {
        let width = components.len();
        if width < 2 {
            return Err(CompositionError::TooFewComponents {
                found: width,
                required: 2,
            });
        }
        let mut values = vec![0.0; (width - 1) * width];
        for row in 0..width - 1 {
            let count = row + 1;
            let scale = (count as f64 / (count + 1) as f64).sqrt();
            for column in 0..count {
                values[row * width + column] = scale / count as f64;
            }
            values[row * width + count] = -scale;
        }
        Self::new(
            components,
            (0..width - 1)
                .map(|index| format!("balance{index}"))
                .collect(),
            values,
        )
    }

    pub fn from_sbp(
        components: Vec<String>,
        balances: Vec<String>,
        partitions: &[Vec<i8>],
    ) -> Result<Self> {
        validate_names("component", &components)?;
        validate_names("balance", &balances)?;
        let width = components.len();
        if partitions.len() != width.saturating_sub(1) || balances.len() != partitions.len() {
            return Err(CompositionError::BasisShape {
                rows: partitions.len(),
                columns: partitions.first().map_or(0, Vec::len),
                expected_rows: width.saturating_sub(1),
                expected_columns: width,
            });
        }
        let mut values = vec![0.0; partitions.len() * width];
        for (row_index, row) in partitions.iter().enumerate() {
            if row.len() != width {
                return Err(CompositionError::BasisShape {
                    rows: partitions.len(),
                    columns: row.len(),
                    expected_rows: width - 1,
                    expected_columns: width,
                });
            }
            if let Some(&value) = row.iter().find(|&&value| !matches!(value, -1..=1)) {
                return Err(CompositionError::InvalidPartitionValue {
                    row: row_index,
                    value,
                });
            }
            let positive = row.iter().filter(|&&value| value == 1).count();
            let negative = row.iter().filter(|&&value| value == -1).count();
            if positive == 0 || negative == 0 {
                return Err(CompositionError::EmptyPartitionSide(row_index));
            }
            let positive_value =
                (negative as f64 / (positive as f64 * (positive + negative) as f64)).sqrt();
            let negative_value =
                -(positive as f64 / (negative as f64 * (positive + negative) as f64)).sqrt();
            for (column, &partition) in row.iter().enumerate() {
                values[row_index * width + column] = match partition {
                    1 => positive_value,
                    -1 => negative_value,
                    _ => 0.0,
                };
            }
        }
        Self::new(components, balances, values)
    }

    pub fn from_tree(tree: &Tree, components: Vec<String>) -> Result<Self> {
        validate_names("component", &components)?;
        if components.len() < 2 {
            return Err(CompositionError::TooFewComponents {
                found: components.len(),
                required: 2,
            });
        }
        let tip_index = tree
            .tip_index()
            .map_err(|error| CompositionError::TreeTipMismatch(error.to_string()))?;
        let component_set: HashSet<&str> = components.iter().map(String::as_str).collect();
        if tip_index.len() != components.len()
            || tip_index.keys().any(|tip| !component_set.contains(tip))
        {
            return Err(CompositionError::TreeTipMismatch(format!(
                "tree has {:?}; components have {:?}",
                sorted(tip_index.keys().copied()),
                sorted(components.iter().map(String::as_str))
            )));
        }

        let mut descendants = vec![Vec::<usize>::new(); tree.node_count()];
        for id in tree.postorder() {
            let node = tree.node(id).unwrap();
            if node.is_tip() {
                let name = node.name().unwrap();
                descendants[id.index()].push(
                    components
                        .iter()
                        .position(|component| component == name)
                        .unwrap(),
                );
            } else {
                if node.children().len() != 2 {
                    return Err(CompositionError::NonBifurcatingTree {
                        node: id.index(),
                        children: node.children().len(),
                    });
                }
                for child in node.children() {
                    let tips = descendants[child.index()].clone();
                    descendants[id.index()].extend(tips);
                }
            }
        }

        let mut internal = Vec::with_capacity(components.len() - 1);
        let mut queue = VecDeque::from([tree.root()]);
        while let Some(id) = queue.pop_front() {
            let node = tree.node(id).unwrap();
            if node.is_tip() {
                continue;
            }
            internal.push(id);
            queue.extend(node.children().iter().copied());
        }
        if internal.len() != components.len() - 1 {
            return Err(CompositionError::BasisShape {
                rows: internal.len(),
                columns: components.len(),
                expected_rows: components.len() - 1,
                expected_columns: components.len(),
            });
        }

        let width = components.len();
        let mut values = vec![0.0; internal.len() * width];
        let mut balances = Vec::with_capacity(internal.len());
        for (row, id) in internal.into_iter().enumerate() {
            let node = tree.node(id).unwrap();
            let negative = &descendants[node.children()[0].index()];
            let positive = &descendants[node.children()[1].index()];
            let positive_value = (negative.len() as f64
                / (positive.len() * (positive.len() + negative.len())) as f64)
                .sqrt();
            let negative_value = -(positive.len() as f64
                / (negative.len() * (positive.len() + negative.len())) as f64)
                .sqrt();
            for &column in positive {
                values[row * width + column] = positive_value;
            }
            for &column in negative {
                values[row * width + column] = negative_value;
            }
            balances.push(
                node.name()
                    .map(str::to_owned)
                    .unwrap_or_else(|| format!("balance{row}")),
            );
        }
        Self::new(components, balances, values)
    }

    #[must_use]
    pub fn components(&self) -> &[String] {
        &self.components
    }

    #[must_use]
    pub fn balances(&self) -> &[String] {
        &self.balances
    }

    #[must_use]
    pub fn values(&self) -> &[f64] {
        &self.values
    }

    #[must_use]
    pub fn row(&self, index: usize) -> Option<&[f64]> {
        let width = self.components.len();
        self.values.get(index * width..(index + 1) * width)
    }

    pub(crate) fn component_order(&self, components: &[String]) -> Result<Vec<usize>> {
        align(&self.components, components, "basis is missing component")
    }

    pub(crate) fn balance_order(&self, balances: &[String]) -> Result<Vec<usize>> {
        align(&self.balances, balances, "coordinates are missing balance")
    }
}

fn align(target: &[String], source: &[String], prefix: &str) -> Result<Vec<usize>> {
    if target.len() != source.len() {
        return Err(CompositionError::ComponentMismatch {
            details: format!("expected {} identities, got {}", target.len(), source.len()),
        });
    }
    target
        .iter()
        .map(|identity| {
            source
                .iter()
                .position(|candidate| candidate == identity)
                .ok_or_else(|| CompositionError::ComponentMismatch {
                    details: format!("{prefix} {identity:?}"),
                })
        })
        .collect()
}

fn validate_names(kind: &'static str, names: &[String]) -> Result<()> {
    let mut seen = HashSet::with_capacity(names.len());
    for name in names {
        if name.is_empty() {
            return Err(CompositionError::EmptyIdentity { kind });
        }
        if !seen.insert(name) {
            return Err(CompositionError::DuplicateIdentity {
                kind,
                identity: name.clone(),
            });
        }
    }
    Ok(())
}

fn validate_orthonormal(values: &[f64], rows: usize, columns: usize) -> Result<()> {
    for left in 0..rows {
        for right in left..rows {
            let dot: f64 = (0..columns)
                .map(|column| values[left * columns + column] * values[right * columns + column])
                .sum();
            let expected = f64::from(u8::from(left == right));
            if !dot.is_finite() || (dot - expected).abs() > 1e-10 {
                return Err(CompositionError::NonOrthonormalBasis {
                    left,
                    right,
                    value: dot,
                });
            }
        }
    }
    Ok(())
}

fn sorted<'a>(values: impl Iterator<Item = &'a str>) -> Vec<&'a str> {
    let mut values: Vec<_> = values.collect();
    values.sort_unstable();
    values
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn sbp_matches_skbio_example() {
        let partitions = vec![
            vec![1, 1, -1, -1, -1],
            vec![1, -1, 0, 0, 0],
            vec![0, 0, 1, -1, -1],
            vec![0, 0, 0, 1, -1],
        ];
        let basis = Basis::from_sbp(
            ["a", "b", "c", "d", "e"].map(str::to_owned).to_vec(),
            (0..4).map(|index| format!("b{index}")).collect(),
            &partitions,
        )
        .unwrap();
        assert!((basis.row(0).unwrap()[0] - 0.547_722_557_505_166_1).abs() < 1e-12);
        assert!((basis.row(0).unwrap()[2] + 0.365_148_371_670_111_4).abs() < 1e-12);
    }

    #[test]
    fn tree_basis_uses_tip_identity() {
        let tree = Tree::from_newick("((b,c)a,d)root;").unwrap();
        let basis = Basis::from_tree(&tree, ["d", "c", "b"].map(str::to_owned).to_vec()).unwrap();
        assert_eq!(basis.balances(), ["root", "a"]);
        assert!((basis.row(0).unwrap()[0] - 0.816_496_580_927_726).abs() < 1e-12);
        assert!((basis.row(1).unwrap()[1] - 0.707_106_781_186_547_5).abs() < 1e-12);
        assert!((basis.row(1).unwrap()[2] + 0.707_106_781_186_547_5).abs() < 1e-12);
    }

    #[test]
    fn tree_basis_rejects_tip_mismatch_and_polytomy() {
        let mismatch = Tree::from_newick("(a,b)root;").unwrap();
        assert!(Basis::from_tree(&mismatch, vec!["a".into(), "c".into()]).is_err());
        let polytomy = Tree::from_newick("(a,b,c)root;").unwrap();
        assert!(matches!(
            Basis::from_tree(&polytomy, ["a", "b", "c"].map(str::to_owned).to_vec()),
            Err(CompositionError::NonBifurcatingTree { .. })
        ));
    }

    #[test]
    fn nonorthogonal_sbp_is_rejected() {
        let partitions = vec![vec![1, -1, 0], vec![1, 0, -1]];
        assert!(matches!(
            Basis::from_sbp(
                ["a", "b", "c"].map(str::to_owned).to_vec(),
                vec!["x".into(), "y".into()],
                &partitions,
            ),
            Err(CompositionError::NonOrthonormalBasis { .. })
        ));
    }

    #[test]
    fn nonfinite_numeric_basis_is_rejected() {
        assert!(matches!(
            Basis::new(
                vec!["a".into(), "b".into()],
                vec!["balance".into()],
                vec![f64::NAN, 0.0],
            ),
            Err(CompositionError::NonOrthonormalBasis { .. })
        ));
    }
}