Skip to main content

rsomics_composition/
basis.rs

1use std::collections::{HashSet, VecDeque};
2
3use rsomics_phylo_tree::Tree;
4
5use crate::{CompositionError, Result};
6
7#[derive(Clone, Debug, PartialEq)]
8pub struct Basis {
9    components: Vec<String>,
10    balances: Vec<String>,
11    values: Vec<f64>,
12}
13
14impl Basis {
15    pub fn new(components: Vec<String>, balances: Vec<String>, values: Vec<f64>) -> Result<Self> {
16        validate_names("component", &components)?;
17        validate_names("balance", &balances)?;
18        let width = components.len();
19        if width < 2 {
20            return Err(CompositionError::TooFewComponents {
21                found: width,
22                required: 2,
23            });
24        }
25        if balances.len() != width - 1 || values.len() != balances.len() * width {
26            return Err(CompositionError::BasisShape {
27                rows: balances.len(),
28                columns: values.len().checked_div(balances.len()).unwrap_or(0),
29                expected_rows: width - 1,
30                expected_columns: width,
31            });
32        }
33        validate_orthonormal(&values, balances.len(), width)?;
34        Ok(Self {
35            components,
36            balances,
37            values,
38        })
39    }
40
41    pub fn default_for(components: Vec<String>) -> Result<Self> {
42        let width = components.len();
43        if width < 2 {
44            return Err(CompositionError::TooFewComponents {
45                found: width,
46                required: 2,
47            });
48        }
49        let mut values = vec![0.0; (width - 1) * width];
50        for row in 0..width - 1 {
51            let count = row + 1;
52            let scale = (count as f64 / (count + 1) as f64).sqrt();
53            for column in 0..count {
54                values[row * width + column] = scale / count as f64;
55            }
56            values[row * width + count] = -scale;
57        }
58        Self::new(
59            components,
60            (0..width - 1)
61                .map(|index| format!("balance{index}"))
62                .collect(),
63            values,
64        )
65    }
66
67    pub fn from_sbp(
68        components: Vec<String>,
69        balances: Vec<String>,
70        partitions: &[Vec<i8>],
71    ) -> Result<Self> {
72        validate_names("component", &components)?;
73        validate_names("balance", &balances)?;
74        let width = components.len();
75        if partitions.len() != width.saturating_sub(1) || balances.len() != partitions.len() {
76            return Err(CompositionError::BasisShape {
77                rows: partitions.len(),
78                columns: partitions.first().map_or(0, Vec::len),
79                expected_rows: width.saturating_sub(1),
80                expected_columns: width,
81            });
82        }
83        let mut values = vec![0.0; partitions.len() * width];
84        for (row_index, row) in partitions.iter().enumerate() {
85            if row.len() != width {
86                return Err(CompositionError::BasisShape {
87                    rows: partitions.len(),
88                    columns: row.len(),
89                    expected_rows: width - 1,
90                    expected_columns: width,
91                });
92            }
93            if let Some(&value) = row.iter().find(|&&value| !matches!(value, -1..=1)) {
94                return Err(CompositionError::InvalidPartitionValue {
95                    row: row_index,
96                    value,
97                });
98            }
99            let positive = row.iter().filter(|&&value| value == 1).count();
100            let negative = row.iter().filter(|&&value| value == -1).count();
101            if positive == 0 || negative == 0 {
102                return Err(CompositionError::EmptyPartitionSide(row_index));
103            }
104            let positive_value =
105                (negative as f64 / (positive as f64 * (positive + negative) as f64)).sqrt();
106            let negative_value =
107                -(positive as f64 / (negative as f64 * (positive + negative) as f64)).sqrt();
108            for (column, &partition) in row.iter().enumerate() {
109                values[row_index * width + column] = match partition {
110                    1 => positive_value,
111                    -1 => negative_value,
112                    _ => 0.0,
113                };
114            }
115        }
116        Self::new(components, balances, values)
117    }
118
119    pub fn from_tree(tree: &Tree, components: Vec<String>) -> Result<Self> {
120        validate_names("component", &components)?;
121        if components.len() < 2 {
122            return Err(CompositionError::TooFewComponents {
123                found: components.len(),
124                required: 2,
125            });
126        }
127        let tip_index = tree
128            .tip_index()
129            .map_err(|error| CompositionError::TreeTipMismatch(error.to_string()))?;
130        let component_set: HashSet<&str> = components.iter().map(String::as_str).collect();
131        if tip_index.len() != components.len()
132            || tip_index.keys().any(|tip| !component_set.contains(tip))
133        {
134            return Err(CompositionError::TreeTipMismatch(format!(
135                "tree has {:?}; components have {:?}",
136                sorted(tip_index.keys().copied()),
137                sorted(components.iter().map(String::as_str))
138            )));
139        }
140
141        let mut descendants = vec![Vec::<usize>::new(); tree.node_count()];
142        for id in tree.postorder() {
143            let node = tree.node(id).unwrap();
144            if node.is_tip() {
145                let name = node.name().unwrap();
146                descendants[id.index()].push(
147                    components
148                        .iter()
149                        .position(|component| component == name)
150                        .unwrap(),
151                );
152            } else {
153                if node.children().len() != 2 {
154                    return Err(CompositionError::NonBifurcatingTree {
155                        node: id.index(),
156                        children: node.children().len(),
157                    });
158                }
159                for child in node.children() {
160                    let tips = descendants[child.index()].clone();
161                    descendants[id.index()].extend(tips);
162                }
163            }
164        }
165
166        let mut internal = Vec::with_capacity(components.len() - 1);
167        let mut queue = VecDeque::from([tree.root()]);
168        while let Some(id) = queue.pop_front() {
169            let node = tree.node(id).unwrap();
170            if node.is_tip() {
171                continue;
172            }
173            internal.push(id);
174            queue.extend(node.children().iter().copied());
175        }
176        if internal.len() != components.len() - 1 {
177            return Err(CompositionError::BasisShape {
178                rows: internal.len(),
179                columns: components.len(),
180                expected_rows: components.len() - 1,
181                expected_columns: components.len(),
182            });
183        }
184
185        let width = components.len();
186        let mut values = vec![0.0; internal.len() * width];
187        let mut balances = Vec::with_capacity(internal.len());
188        for (row, id) in internal.into_iter().enumerate() {
189            let node = tree.node(id).unwrap();
190            let negative = &descendants[node.children()[0].index()];
191            let positive = &descendants[node.children()[1].index()];
192            let positive_value = (negative.len() as f64
193                / (positive.len() * (positive.len() + negative.len())) as f64)
194                .sqrt();
195            let negative_value = -(positive.len() as f64
196                / (negative.len() * (positive.len() + negative.len())) as f64)
197                .sqrt();
198            for &column in positive {
199                values[row * width + column] = positive_value;
200            }
201            for &column in negative {
202                values[row * width + column] = negative_value;
203            }
204            balances.push(
205                node.name()
206                    .map(str::to_owned)
207                    .unwrap_or_else(|| format!("balance{row}")),
208            );
209        }
210        Self::new(components, balances, values)
211    }
212
213    #[must_use]
214    pub fn components(&self) -> &[String] {
215        &self.components
216    }
217
218    #[must_use]
219    pub fn balances(&self) -> &[String] {
220        &self.balances
221    }
222
223    #[must_use]
224    pub fn values(&self) -> &[f64] {
225        &self.values
226    }
227
228    #[must_use]
229    pub fn row(&self, index: usize) -> Option<&[f64]> {
230        let width = self.components.len();
231        self.values.get(index * width..(index + 1) * width)
232    }
233
234    pub(crate) fn component_order(&self, components: &[String]) -> Result<Vec<usize>> {
235        align(&self.components, components, "basis is missing component")
236    }
237
238    pub(crate) fn balance_order(&self, balances: &[String]) -> Result<Vec<usize>> {
239        align(&self.balances, balances, "coordinates are missing balance")
240    }
241}
242
243fn align(target: &[String], source: &[String], prefix: &str) -> Result<Vec<usize>> {
244    if target.len() != source.len() {
245        return Err(CompositionError::ComponentMismatch {
246            details: format!("expected {} identities, got {}", target.len(), source.len()),
247        });
248    }
249    target
250        .iter()
251        .map(|identity| {
252            source
253                .iter()
254                .position(|candidate| candidate == identity)
255                .ok_or_else(|| CompositionError::ComponentMismatch {
256                    details: format!("{prefix} {identity:?}"),
257                })
258        })
259        .collect()
260}
261
262fn validate_names(kind: &'static str, names: &[String]) -> Result<()> {
263    let mut seen = HashSet::with_capacity(names.len());
264    for name in names {
265        if name.is_empty() {
266            return Err(CompositionError::EmptyIdentity { kind });
267        }
268        if !seen.insert(name) {
269            return Err(CompositionError::DuplicateIdentity {
270                kind,
271                identity: name.clone(),
272            });
273        }
274    }
275    Ok(())
276}
277
278fn validate_orthonormal(values: &[f64], rows: usize, columns: usize) -> Result<()> {
279    for left in 0..rows {
280        for right in left..rows {
281            let dot: f64 = (0..columns)
282                .map(|column| values[left * columns + column] * values[right * columns + column])
283                .sum();
284            let expected = f64::from(u8::from(left == right));
285            if !dot.is_finite() || (dot - expected).abs() > 1e-10 {
286                return Err(CompositionError::NonOrthonormalBasis {
287                    left,
288                    right,
289                    value: dot,
290                });
291            }
292        }
293    }
294    Ok(())
295}
296
297fn sorted<'a>(values: impl Iterator<Item = &'a str>) -> Vec<&'a str> {
298    let mut values: Vec<_> = values.collect();
299    values.sort_unstable();
300    values
301}
302
303#[cfg(test)]
304mod tests {
305    use super::*;
306
307    #[test]
308    fn sbp_matches_skbio_example() {
309        let partitions = vec![
310            vec![1, 1, -1, -1, -1],
311            vec![1, -1, 0, 0, 0],
312            vec![0, 0, 1, -1, -1],
313            vec![0, 0, 0, 1, -1],
314        ];
315        let basis = Basis::from_sbp(
316            ["a", "b", "c", "d", "e"].map(str::to_owned).to_vec(),
317            (0..4).map(|index| format!("b{index}")).collect(),
318            &partitions,
319        )
320        .unwrap();
321        assert!((basis.row(0).unwrap()[0] - 0.547_722_557_505_166_1).abs() < 1e-12);
322        assert!((basis.row(0).unwrap()[2] + 0.365_148_371_670_111_4).abs() < 1e-12);
323    }
324
325    #[test]
326    fn tree_basis_uses_tip_identity() {
327        let tree = Tree::from_newick("((b,c)a,d)root;").unwrap();
328        let basis = Basis::from_tree(&tree, ["d", "c", "b"].map(str::to_owned).to_vec()).unwrap();
329        assert_eq!(basis.balances(), ["root", "a"]);
330        assert!((basis.row(0).unwrap()[0] - 0.816_496_580_927_726).abs() < 1e-12);
331        assert!((basis.row(1).unwrap()[1] - 0.707_106_781_186_547_5).abs() < 1e-12);
332        assert!((basis.row(1).unwrap()[2] + 0.707_106_781_186_547_5).abs() < 1e-12);
333    }
334
335    #[test]
336    fn tree_basis_rejects_tip_mismatch_and_polytomy() {
337        let mismatch = Tree::from_newick("(a,b)root;").unwrap();
338        assert!(Basis::from_tree(&mismatch, vec!["a".into(), "c".into()]).is_err());
339        let polytomy = Tree::from_newick("(a,b,c)root;").unwrap();
340        assert!(matches!(
341            Basis::from_tree(&polytomy, ["a", "b", "c"].map(str::to_owned).to_vec()),
342            Err(CompositionError::NonBifurcatingTree { .. })
343        ));
344    }
345
346    #[test]
347    fn nonorthogonal_sbp_is_rejected() {
348        let partitions = vec![vec![1, -1, 0], vec![1, 0, -1]];
349        assert!(matches!(
350            Basis::from_sbp(
351                ["a", "b", "c"].map(str::to_owned).to_vec(),
352                vec!["x".into(), "y".into()],
353                &partitions,
354            ),
355            Err(CompositionError::NonOrthonormalBasis { .. })
356        ));
357    }
358
359    #[test]
360    fn nonfinite_numeric_basis_is_rejected() {
361        assert!(matches!(
362            Basis::new(
363                vec!["a".into(), "b".into()],
364                vec!["balance".into()],
365                vec![f64::NAN, 0.0],
366            ),
367            Err(CompositionError::NonOrthonormalBasis { .. })
368        ));
369    }
370}