Skip to main content

rsomics_call/
errmod.rs

1use std::sync::OnceLock;
2
3use crate::{CallError, Result};
4
5const MAX_DEPTH: usize = 255;
6const QUALITY_LEVELS: usize = 64;
7const BASES: usize = 5;
8
9#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
10#[repr(u8)]
11pub enum Nucleotide {
12    A,
13    C,
14    G,
15    T,
16    N,
17}
18
19#[derive(Clone, Copy, Debug, PartialEq, Eq)]
20pub struct BaseObservation(u16);
21
22impl BaseObservation {
23    pub fn new(base: Nucleotide, quality: u8, reverse: bool) -> Self {
24        Self(u16::from(quality.clamp(4, 63)) << 5 | u16::from(reverse) << 4 | base as u16)
25    }
26}
27
28#[derive(Clone, Debug, PartialEq)]
29pub struct LikelihoodMatrix([f32; BASES * BASES]);
30
31impl LikelihoodMatrix {
32    pub fn get(&self, first: Nucleotide, second: Nucleotide) -> f32 {
33        self.0[first as usize * BASES + second as usize]
34    }
35
36    pub fn as_slice(&self) -> &[f32] {
37        &self.0
38    }
39}
40
41pub struct ErrorModel {
42    correlation: [f64; MAX_DEPTH + 1],
43    log_binomial: Box<[f64]>,
44    heterozygous: Box<[f64]>,
45    beta: Box<[OnceLock<Box<[f64]>>]>,
46    random: HtsRandom,
47}
48
49impl Default for ErrorModel {
50    fn default() -> Self {
51        Self::new()
52    }
53}
54
55impl ErrorModel {
56    pub fn new() -> Self {
57        Self::with_dependency_correlation(0.17).unwrap()
58    }
59
60    pub fn with_dependency_correlation(dependency_correlation: f64) -> Result<Self> {
61        Self::with_dependency_correlation_and_seed(dependency_correlation, 0)
62    }
63
64    pub fn with_random_seed(seed: i32) -> Self {
65        Self::with_dependency_correlation_and_seed(0.17, seed).unwrap()
66    }
67
68    pub fn with_dependency_correlation_and_seed(
69        dependency_correlation: f64,
70        seed: i32,
71    ) -> Result<Self> {
72        if !dependency_correlation.is_finite() || !(0.0..=1.0).contains(&dependency_correlation) {
73            return Err(CallError::InvalidDependencyCorrelation);
74        }
75        let mut correlation = [0.0; MAX_DEPTH + 1];
76        correlation[0] = 1.0;
77        for (depth, value) in correlation.iter_mut().enumerate().skip(1) {
78            *value = (1.0 - dependency_correlation).powi(depth as i32) * 0.97 + 0.03;
79        }
80
81        let mut log_binomial = vec![0.0; 256 * 256];
82        for trials in 1..=MAX_DEPTH {
83            let total = log_gamma(trials as f64 + 1.0);
84            for successes in 1..=trials {
85                log_binomial[trials << 8 | successes] = total
86                    - log_gamma(successes as f64 + 1.0)
87                    - log_gamma((trials - successes) as f64 + 1.0);
88            }
89        }
90        let mut heterozygous = vec![0.0; 256 * 256];
91        for trials in 0..=MAX_DEPTH {
92            for successes in 0..=MAX_DEPTH {
93                heterozygous[trials << 8 | successes] =
94                    log_binomial[trials << 8 | successes] - std::f64::consts::LN_2 * trials as f64;
95            }
96        }
97
98        Ok(Self {
99            correlation,
100            log_binomial: log_binomial.into_boxed_slice(),
101            heterozygous: heterozygous.into_boxed_slice(),
102            beta: std::iter::repeat_with(OnceLock::new)
103                .take(MAX_DEPTH + 1)
104                .collect(),
105            random: HtsRandom::new(seed),
106        })
107    }
108
109    pub fn calculate(&mut self, observations: &mut [BaseObservation]) -> Result<LikelihoodMatrix> {
110        if observations.len() > MAX_DEPTH {
111            self.random.shuffle(observations);
112        }
113        let depth = observations.len().min(MAX_DEPTH);
114        let observations = &mut observations[..depth];
115        let depth = observations.len();
116        let mut output = [0.0; BASES * BASES];
117        if depth == 0 {
118            return Ok(LikelihoodMatrix(output));
119        }
120
121        observations.sort_unstable_by_key(|observation| observation.0);
122        let beta = self.beta[depth].get_or_init(|| self.build_beta(depth));
123        let mut base_sums = [0.0; 16];
124        let mut base_counts = [0usize; 16];
125        let mut strand_counts = [0usize; 32];
126
127        for observation in observations.iter().rev() {
128            let quality = usize::from(observation.0 >> 5).clamp(4, 63);
129            let base_strand = usize::from(observation.0 & 0x1f);
130            let base = usize::from(observation.0 & 0x0f);
131            base_sums[base] += self.correlation[strand_counts[base_strand]]
132                * beta[quality << 8 | base_counts[base]];
133            base_counts[base] += 1;
134            strand_counts[base_strand] += 1;
135        }
136
137        for first in 0..BASES {
138            let mut homozygous = 0.0f32;
139            let mut outside_count = 0;
140            for base in 0..BASES {
141                if base != first {
142                    homozygous += base_sums[base] as f32;
143                    outside_count += base_counts[base];
144                }
145            }
146            if outside_count > 0 {
147                output[first * BASES + first] = homozygous;
148            }
149
150            for second in first + 1..BASES {
151                let selected_count = base_counts[first] + base_counts[second];
152                let mut outside_sum = 0.0f32;
153                for (base, sum) in base_sums.iter().enumerate().take(BASES) {
154                    if base != first && base != second {
155                        outside_sum += *sum as f32;
156                    }
157                }
158                let value = (-4.343 * self.heterozygous[selected_count << 8 | base_counts[second]]
159                    + f64::from(outside_sum)) as f32;
160                output[first * BASES + second] = value.max(0.0);
161                output[second * BASES + first] = value.max(0.0);
162            }
163        }
164
165        Ok(LikelihoodMatrix(output))
166    }
167
168    fn build_beta(&self, depth: usize) -> Box<[f64]> {
169        let mut beta = vec![0.0; QUALITY_LEVELS * 256];
170        for quality in 1..QUALITY_LEVELS {
171            let error = 10f64.powf(-(quality as f64) / 10.0);
172            let log_error = error.ln();
173            let log_correct = (1.0 - error).ln();
174            let mut cumulative = self.log_binomial[depth << 8 | depth] + depth as f64 * log_error;
175            beta[quality << 8 | depth] = f64::INFINITY;
176            for matches in (0..depth).rev() {
177                let previous = cumulative;
178                cumulative = previous
179                    + (self.log_binomial[depth << 8 | matches]
180                        + matches as f64 * log_error
181                        + (depth - matches) as f64 * log_correct
182                        - previous)
183                        .exp()
184                        .ln_1p();
185                beta[quality << 8 | matches] =
186                    -10.0 / std::f64::consts::LN_10 * (previous - cumulative);
187            }
188        }
189        beta.into_boxed_slice()
190    }
191}
192
193struct HtsRandom {
194    state: u64,
195}
196
197impl HtsRandom {
198    fn new(seed: i32) -> Self {
199        Self {
200            state: u64::from(seed as u32) << 16 | 0x330e,
201        }
202    }
203
204    fn next_f64(&mut self) -> f64 {
205        self.state =
206            (0x5deece66du64.wrapping_mul(self.state).wrapping_add(0xb)) & ((1u64 << 48) - 1);
207        self.state as f64 / (1u64 << 48) as f64
208    }
209
210    fn shuffle<T>(&mut self, values: &mut [T]) {
211        for end in (2..=values.len()).rev() {
212            let index = (self.next_f64() * end as f64) as usize;
213            values.swap(index, end - 1);
214        }
215    }
216}
217
218fn log_gamma(value: f64) -> f64 {
219    const COEFFICIENTS: [f64; 6] = [
220        76.180_091_729_471_46,
221        -86.505_320_329_416_77,
222        24.014_098_240_830_91,
223        -1.231_739_572_450_155,
224        1.208_650_973_866_179e-3,
225        -5.395_239_384_953e-6,
226    ];
227    let shifted = value - 1.0;
228    let series = COEFFICIENTS
229        .iter()
230        .enumerate()
231        .fold(1.000_000_000_190_015, |sum, (index, coefficient)| {
232            sum + coefficient / (shifted + index as f64 + 1.0)
233        });
234    let scale = shifted + 5.5;
235    (shifted + 0.5) * scale.ln() - scale + (2.506_628_274_631_001 * series).ln()
236}
237
238#[cfg(test)]
239mod tests {
240    use super::*;
241
242    fn assert_matrix(actual: &LikelihoodMatrix, expected: [f32; 25]) {
243        for (index, (&actual, expected)) in actual.as_slice().iter().zip(expected).enumerate() {
244            assert!(
245                (actual - expected).abs() < 0.0005,
246                "matrix index {index}: {actual} != {expected}"
247            );
248        }
249    }
250
251    #[test]
252    #[allow(clippy::excessive_precision)]
253    fn matches_htslib_1_24_balanced_observations() {
254        let mut observations = Vec::new();
255        observations.extend((0..10).map(|_| BaseObservation::new(Nucleotide::A, 40, false)));
256        observations.extend((0..10).map(|_| BaseObservation::new(Nucleotide::G, 40, true)));
257        let matrix = ErrorModel::default().calculate(&mut observations).unwrap();
258        assert_matrix(
259            &matrix,
260            [
261                168.366653, 198.470032, 7.54010963, 198.470032, 198.470032, 198.470032, 336.733307,
262                198.470032, 336.733307, 336.733307, 7.54010963, 198.470032, 168.366653, 198.470032,
263                198.470032, 198.470032, 336.733307, 198.470032, 336.733307, 336.733307, 198.470032,
264                336.733307, 198.470032, 336.733307, 336.733307,
265            ],
266        );
267    }
268
269    #[test]
270    #[allow(clippy::excessive_precision)]
271    fn matches_htslib_1_24_mixed_qualities() {
272        let mut observations = [
273            BaseObservation::new(Nucleotide::A, 60, false),
274            BaseObservation::new(Nucleotide::A, 50, false),
275            BaseObservation::new(Nucleotide::A, 40, false),
276            BaseObservation::new(Nucleotide::A, 30, false),
277            BaseObservation::new(Nucleotide::A, 20, false),
278            BaseObservation::new(Nucleotide::A, 10, false),
279            BaseObservation::new(Nucleotide::A, 8, false),
280            BaseObservation::new(Nucleotide::A, 4, false),
281            BaseObservation::new(Nucleotide::C, 35, true),
282            BaseObservation::new(Nucleotide::C, 25, true),
283            BaseObservation::new(Nucleotide::C, 15, true),
284            BaseObservation::new(Nucleotide::G, 45, false),
285        ];
286        let matrix = ErrorModel::default().calculate(&mut observations).unwrap();
287        assert_matrix(
288            &matrix,
289            [
290                79.9680862, 45.147541, 63.3096428, 104.050789, 104.050789, 45.147541, 175.383667,
291                147.195404, 184.414688, 184.414688, 63.3096428, 147.195404, 186.933868, 189.944214,
292                189.944214, 104.050789, 184.414688, 189.944214, 221.142807, 221.142807, 104.050789,
293                184.414688, 189.944214, 221.142807, 221.142807,
294            ],
295        );
296    }
297
298    #[test]
299    #[allow(clippy::excessive_precision)]
300    fn matches_htslib_1_24_strand_correlation() {
301        let mut observations = [BaseObservation::new(Nucleotide::A, 40, false); 8];
302        let matrix = ErrorModel::default().calculate(&mut observations).unwrap();
303        assert_matrix(
304            &matrix,
305            [
306                0.0, 24.0827065, 24.0827065, 24.0827065, 24.0827065, 24.0827065, 176.440491,
307                176.440491, 176.440491, 176.440491, 24.0827065, 176.440491, 176.440491, 176.440491,
308                176.440491, 24.0827065, 176.440491, 176.440491, 176.440491, 176.440491, 24.0827065,
309                176.440491, 176.440491, 176.440491, 176.440491,
310            ],
311        );
312    }
313
314    #[test]
315    #[allow(clippy::excessive_precision)]
316    fn matches_htslib_1_24_deep_sampling_stream() {
317        fn observations() -> Vec<BaseObservation> {
318            (0..300)
319                .map(|index| {
320                    BaseObservation::new(
321                        if index % 3 == 0 {
322                            Nucleotide::G
323                        } else {
324                            Nucleotide::A
325                        },
326                        20 + (index % 41) as u8,
327                        index % 5 == 0,
328                    )
329                })
330                .collect()
331        }
332
333        let mut model = ErrorModel::with_random_seed(0);
334        let mut first = observations();
335        assert_matrix(
336            &model.calculate(&mut first).unwrap(),
337            [
338                504.332642, 1028.13147, 88.087204, 1028.13147, 1028.13147, 1028.13147, 1161.66272,
339                901.167419, 1161.66272, 1161.66272, 88.087204, 901.167419, 657.330017, 901.167419,
340                901.167419, 1028.13147, 1161.66272, 901.167419, 1161.66272, 1161.66272, 1028.13147,
341                1161.66272, 901.167419, 1161.66272, 1161.66272,
342            ],
343        );
344        let mut second = observations();
345        assert_matrix(
346            &model.calculate(&mut second).unwrap(),
347            [
348                506.537384, 1039.36719, 98.3605499, 1039.36719, 1039.36719, 1039.36719, 1178.02258,
349                906.291626, 1178.02258, 1178.02258, 98.3605499, 906.291626, 671.485229, 906.291626,
350                906.291626, 1039.36719, 1178.02258, 906.291626, 1178.02258, 1178.02258, 1039.36719,
351                1178.02258, 906.291626, 1178.02258, 1178.02258,
352            ],
353        );
354    }
355
356    #[test]
357    fn correlation_parameter_is_checked() {
358        assert!(ErrorModel::with_dependency_correlation(0.0).is_ok());
359        assert!(ErrorModel::with_dependency_correlation(1.0).is_ok());
360        assert!(matches!(
361            ErrorModel::with_dependency_correlation(f64::NAN),
362            Err(CallError::InvalidDependencyCorrelation)
363        ));
364        assert!(matches!(
365            ErrorModel::with_dependency_correlation(1.1),
366            Err(CallError::InvalidDependencyCorrelation)
367        ));
368    }
369}