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}