1use crate::config::Alphabet;
25use crate::error::{DimaError, Result};
26use crate::human::plural;
27use crate::model::{AlphabetMethod, ByteClass};
28
29pub const WHITESPACE: &[u8] = b" \t\r\x0B\x0C";
33
34#[must_use]
36pub const fn is_whitespace(b: u8) -> bool {
37 matches!(b, b' ' | b'\t' | b'\r' | 0x0B | 0x0C)
38}
39
40#[derive(Clone, Debug, Default, PartialEq, Eq)]
42pub struct LetterCounts([u64; 26]);
43
44impl LetterCounts {
45 pub fn add(&mut self, bytes: &[u8]) {
47 for &b in bytes {
48 let u = b.to_ascii_uppercase();
49 if u.is_ascii_uppercase() {
50 self.0[usize::from(u - b'A')] += 1;
51 }
52 }
53 }
54
55 #[must_use]
57 pub fn from_histogram(h: &[u64; 256]) -> Self {
58 let mut c = Self::default();
59 for (i, n) in c.0.iter_mut().enumerate() {
60 let upper = b'A' + u8::try_from(i).unwrap_or(0);
61 *n = h[usize::from(upper)] + h[usize::from(upper.to_ascii_lowercase())];
62 }
63 c
64 }
65
66 pub fn merge(&mut self, other: &Self) {
68 for (a, b) in self.0.iter_mut().zip(other.0) {
69 *a += b;
70 }
71 }
72
73 #[must_use]
75 pub fn get(&self, letter: u8) -> u64 {
76 debug_assert!(letter.is_ascii_uppercase());
77 self.0[usize::from(letter - b'A')]
78 }
79
80 #[must_use]
82 pub fn total(&self) -> u64 {
83 self.0.iter().sum()
84 }
85}
86
87#[must_use]
101#[allow(clippy::cast_precision_loss)] pub fn guess(ct: &LetterCounts) -> Option<Alphabet> {
103 let count = |set: &[u8]| -> (u64, u64) {
104 set.iter().fold((0, 0), |(n, x), &l| {
105 let c = ct.get(l);
106 if c > 0 { (n + c, x + 1) } else { (n, x) }
107 })
108 };
109 let n = ct.total();
110 let (n1, x1) = count(b"EFIJLOPQZ");
111 let (n2, x2) = count(b"ACG");
112 let (n3, x3) = count(b"DHKMRSVWY");
113 let nt = ct.get(b'T');
114 let nu = ct.get(b'U');
115 let nx = ct.get(b'X');
116 let nn = ct.get(b'N');
117 let (xt, xu, xn) = (u64::from(nt > 0), u64::from(nu > 0), u64::from(nn > 0));
118 let nearly_all = |k: u64| (n - k) as f64 <= 0.02 * n as f64;
119
120 if n <= 10 {
121 None
122 } else if n > 2000 && nn == n {
123 Some(Alphabet::Dna)
124 } else if n1 > 0 {
125 Some(Alphabet::Protein)
126 } else if nearly_all(n2 + nt + nn) && x2 + xt == 4 {
127 Some(Alphabet::Dna)
128 } else if nearly_all(n2 + nu + nn) && x2 + xu == 4 {
129 Some(Alphabet::Rna)
130 } else if nearly_all(n1 + n2 + n3 + nn + nt + nx) && n3 > n2 && x1 + x2 + x3 + xn + xt >= 15 {
131 Some(Alphabet::Protein)
132 } else {
133 None
134 }
135}
136
137#[derive(Clone, Debug, PartialEq, Eq)]
139pub struct Resolution {
140 pub alphabet: Alphabet,
142 pub method: AlphabetMethod,
144 pub residues_examined: u64,
146 pub contradiction: Option<String>,
148}
149
150pub fn resolve(
156 choice: Option<Alphabet>,
157 counts: &LetterCounts,
158 records_examined: u64,
159) -> Result<Resolution> {
160 let guessed = guess(counts);
161 let residues_examined = counts.total();
162 if let Some(alphabet) = choice {
163 let contradiction = guessed.filter(|g| *g != alphabet).map(|g| {
164 format!(
165 "--alphabet {alphabet} was given, but the residue composition of {} looks \
166 like {g}",
167 first_records(records_examined)
168 )
169 });
170 return Ok(Resolution {
171 alphabet,
172 method: AlphabetMethod::User,
173 residues_examined,
174 contradiction,
175 });
176 }
177 let Some(alphabet) = guessed else {
178 let (t, u) = (counts.get(b'T'), counts.get(b'U'));
179 let n = residues_examined;
180 let message = if n <= 10 {
181 format!(
182 "only {} in {}; that is too few to tell protein from nucleotide sequences",
183 plural(n, "residue letter", "residue letters"),
184 first_records(records_examined)
185 )
186 } else if t > 0 && u > 0 {
187 format!(
188 "the sequences contain both T ({t}) and U ({u}), so DNA and RNA cannot be told \
189 apart"
190 )
191 } else {
192 format!(
193 "the residue composition of {} ({}) does not identify the alphabet",
194 first_records(records_examined),
195 plural(n, "letter", "letters")
196 )
197 };
198 return Err(DimaError::input_data(None, message)
199 .with_hint("pass --alphabet protein, --alphabet dna or --alphabet rna"));
200 };
201 Ok(Resolution {
202 alphabet,
203 method: AlphabetMethod::Detected,
204 residues_examined,
205 contradiction: None,
206 })
207}
208
209fn first_records(n: u64) -> String {
211 if n == 1 {
212 "the first record".to_owned()
213 } else {
214 format!("the first {n} records")
215 }
216}
217
218#[derive(Clone, Debug)]
223pub struct ByteClassTable {
224 alphabet: Alphabet,
225 class: [ByteClass; 256],
226 canonical: [u8; 256],
227}
228
229impl ByteClassTable {
230 #[must_use]
232 pub fn new(alphabet: Alphabet) -> Self {
233 let mut class = [ByteClass::Unknown; 256];
234 let mut canonical = [0u8; 256];
235 let mut set = |bytes: &[u8], c: ByteClass| {
236 for &b in bytes {
237 for v in [b, b.to_ascii_lowercase()] {
238 class[usize::from(v)] = c;
239 }
240 }
241 };
242 set(b"-._", ByteClass::Gap);
243 set(b"~?", ByteClass::Missing);
244 set(b"*$^", ByteClass::Stop);
245 set(b"#", ByteClass::Frameshift);
246 set(WHITESPACE, ByteClass::Whitespace);
247 let (residues, ambiguity): (&[u8], &[u8]) = match alphabet {
248 Alphabet::Protein => (b"ACDEFGHIKLMNPQRSTVWYUO", b"XBJZ"),
249 Alphabet::Dna => (b"ACGTU", b"RYKMSWBDHVNXI"),
250 Alphabet::Rna => (b"ACGUT", b"RYKMSWBDHVNXI"),
251 };
252 set(ambiguity, ByteClass::Ambiguity);
253 set(residues, ByteClass::Residue);
254 for &r in residues {
255 let canon = match (alphabet, r) {
256 (Alphabet::Dna, b'U') => b'T',
257 (Alphabet::Rna, b'T') => b'U',
258 _ => r,
259 };
260 canonical[usize::from(r)] = canon;
261 canonical[usize::from(r.to_ascii_lowercase())] = canon;
262 }
263 Self {
264 alphabet,
265 class,
266 canonical,
267 }
268 }
269
270 #[must_use]
272 pub const fn alphabet(&self) -> Alphabet {
273 self.alphabet
274 }
275
276 #[must_use]
278 pub const fn class(&self, b: u8) -> ByteClass {
279 self.class[b as usize]
280 }
281
282 #[must_use]
284 pub const fn canonical(&self, b: u8) -> u8 {
285 self.canonical[b as usize]
286 }
287
288 #[must_use]
291 pub const fn is_folded_t_u(&self, b: u8) -> bool {
292 matches!(
293 (self.alphabet, b),
294 (Alphabet::Dna, b'U' | b'u') | (Alphabet::Rna, b'T' | b't')
295 )
296 }
297}
298
299#[cfg(test)]
300mod tests {
301 use super::*;
302
303 #[test]
304 fn histogram_counts_letters_like_add() {
305 let text = b"ACGTacgtNnxX-.*~ \n\t\xff\x00Zz";
306 let mut h = [0u64; 256];
307 for &b in text {
308 h[usize::from(b)] += 1;
309 }
310 let mut added = LetterCounts::default();
311 added.add(text);
312 assert_eq!(LetterCounts::from_histogram(&h), added);
313 assert_eq!(added.total(), 14);
314 }
315
316 fn counts(s: &str) -> LetterCounts {
317 let mut c = LetterCounts::default();
318 c.add(s.as_bytes());
319 c
320 }
321
322 #[test]
323 fn guess_follows_easel_rules() {
324 assert_eq!(guess(&counts("ACGTACGTAC")), None, "n ≤ 10");
325 assert_eq!(guess(&counts("ACGTACGTACG")), Some(Alphabet::Dna));
326 assert_eq!(guess(&counts("acguacguacgu")), Some(Alphabet::Rna));
327 assert_eq!(guess(&counts(&"N".repeat(2001))), Some(Alphabet::Dna));
328 assert_eq!(guess(&counts(&"N".repeat(2000))), None);
329 assert_eq!(
330 guess(&counts("ACGTACGTACGE")),
331 Some(Alphabet::Protein),
332 "giveaway E"
333 );
334 assert_eq!(guess(&counts("ACGACGACGACGA")), None);
336 let mut s = "ACGT".repeat(12);
338 s.push_str("AR");
339 assert_eq!(guess(&counts(&s)), Some(Alphabet::Dna));
340 let mut s = "ACGT".repeat(12);
341 s.push_str("RR");
342 assert_eq!(guess(&counts(&s)), None);
343 assert_eq!(guess(&counts(&"ACGTU".repeat(20))), None);
345 assert_eq!(guess(&counts("MKVDHRSWYACGTNMKVDHRSWYNTKD")), None);
349 assert_eq!(guess(&counts("ACGT-ACGT.ACGT 123")), Some(Alphabet::Dna));
351 }
352
353 #[test]
354 fn guess_on_mers_spike_protein() {
355 let fasta = include_str!("../../../samples/mers_spike_aa.fasta");
356 let mut c = LetterCounts::default();
357 for line in fasta.lines().filter(|l| !l.starts_with('>')) {
358 c.add(line.as_bytes());
359 }
360 assert_eq!(guess(&c), Some(Alphabet::Protein));
361 }
362
363 #[test]
364 fn resolve_reports_contradictions_and_failures() {
365 let dna = counts(&"ACGT".repeat(10));
366 let r = resolve(None, &dna, 3).unwrap();
367 assert_eq!(
368 (r.alphabet, r.method),
369 (Alphabet::Dna, AlphabetMethod::Detected)
370 );
371 let r = resolve(Some(Alphabet::Protein), &dna, 3).unwrap();
372 assert_eq!(r.method, AlphabetMethod::User);
373 assert!(r.contradiction.unwrap().contains("looks like dna"));
374 let e = resolve(None, &counts("ACG"), 1).unwrap_err();
375 assert!(e.to_string().contains("only 3 residue letters"));
376 assert!(e.hint().unwrap().contains("--alphabet"));
377 let e = resolve(None, &counts(&"ACGTU".repeat(20)), 4).unwrap_err();
378 assert!(e.to_string().contains("both T (20) and U (20)"));
379 assert_eq!(e.class(), crate::error::ExitClass::InvalidInput);
380 assert!(
382 resolve(Some(Alphabet::Rna), &counts(""), 0)
383 .unwrap()
384 .contradiction
385 .is_none()
386 );
387 }
388
389 #[test]
391 fn byte_tables_are_exhaustive() {
392 for alphabet in [Alphabet::Protein, Alphabet::Dna, Alphabet::Rna] {
393 let t = ByteClassTable::new(alphabet);
394 for b in 0u8..=255 {
395 let u = b.to_ascii_uppercase();
396 let expected = match u {
397 b'-' | b'.' | b'_' => ByteClass::Gap,
398 b'~' | b'?' => ByteClass::Missing,
399 b'*' | b'$' | b'^' => ByteClass::Stop,
400 b'#' => ByteClass::Frameshift,
401 b' ' | b'\t' | b'\r' | 0x0B | 0x0C => ByteClass::Whitespace,
402 _ if u.is_ascii_uppercase() => {
403 let (res, amb): (&[u8], &[u8]) = match alphabet {
404 Alphabet::Protein => (b"ACDEFGHIKLMNPQRSTVWYUO", b"XBJZ"),
405 _ => (b"ACGTU", b"RYKMSWBDHVNXI"),
406 };
407 if res.contains(&u) {
408 ByteClass::Residue
409 } else if amb.contains(&u) {
410 ByteClass::Ambiguity
411 } else {
412 ByteClass::Unknown
413 }
414 }
415 _ => ByteClass::Unknown,
416 };
417 assert_eq!(t.class(b), expected, "{alphabet} byte {b:#04x}");
418 let canon = t.canonical(b);
419 if expected == ByteClass::Residue {
420 let want = match (alphabet, u) {
421 (Alphabet::Dna, b'U') => b'T',
422 (Alphabet::Rna, b'T') => b'U',
423 _ => u,
424 };
425 assert_eq!(canon, want, "{alphabet} byte {b:#04x}");
426 } else {
427 assert_eq!(canon, 0, "{alphabet} byte {b:#04x}");
428 }
429 }
430 assert_eq!(t.class(0), ByteClass::Unknown);
431 assert_eq!(
432 t.class(b'\n'),
433 ByteClass::Unknown,
434 "line feeds never reach the table"
435 );
436 }
437 assert!(ByteClassTable::new(Alphabet::Dna).is_folded_t_u(b'u'));
438 assert!(!ByteClassTable::new(Alphabet::Dna).is_folded_t_u(b't'));
439 assert!(ByteClassTable::new(Alphabet::Rna).is_folded_t_u(b'T'));
440 assert!(!ByteClassTable::new(Alphabet::Protein).is_folded_t_u(b'U'));
441 }
442}