Skip to main content

dima_core/
alphabet.rs

1//! Sequence alphabets: detection from residue composition and per-byte symbol classes.
2//!
3//! **Detection** is a port of Easel's `esl_abc_GuessAlphabet()` (Eddy 2011; Easel commit
4//! 07ca83ba9ef0414dba9ce0a9331d465b5eb58f2b, `esl_alphabet.c`, BSD licence — see
5//! THIRD-PARTY-NOTICES), applied to the letters of the first input batch. Easel's rules were
6//! tuned to make no false calls on NCBI nr/nt, Pfam and Rfam; when unsure they return
7//! "unknown", and DiMA then asks the user for `--alphabet` rather than guessing.
8//!
9//! **Symbol classes** (case-folded first):
10//!
11//! | Class | Protein | DNA / RNA |
12//! |---|---|---|
13//! | residue | `ACDEFGHIKLMNPQRSTVWY` + `U` (selenocysteine; Böck et al. 1991) and `O` (pyrrolysine; Srinivasan et al. 2002) | `ACGT` / `ACGU` (T and U folded to the alphabet's letter) |
14//! | gap | `-` `.` `_` | same |
15//! | missing | `~` `?` | same |
16//! | ambiguity | `X` `B` `J` `Z` | `R Y K M S W B D H V N X I` (IUPAC-IUB; Cornish-Bowden 1985) |
17//! | stop | `*` `$` `^` | same (LANL "Codes and Symbols in Sequence Alignments"; Gene Cutter help) |
18//! | frameshift | `#` | same |
19//! | whitespace | space, TAB, CR, VT, FF (ignored) | same |
20//!
21//! Every class except *residue* and *whitespace* excludes the k-mers that contain it; anything
22//! else is *unknown* and handled by the validation mode.
23
24use crate::config::Alphabet;
25use crate::error::{DimaError, Result};
26use crate::human::plural;
27use crate::model::{AlphabetMethod, ByteClass};
28
29/// The white-space bytes of FASTA text (D37): space, TAB, CR, VT and FF (the POSIX `space`
30/// class without the line feed). They are ignored inside sequence lines, and lines made only of
31/// them are skipped before the first record.
32pub const WHITESPACE: &[u8] = b" \t\r\x0B\x0C";
33
34/// `true` for a [`WHITESPACE`] byte.
35#[must_use]
36pub const fn is_whitespace(b: u8) -> bool {
37    matches!(b, b' ' | b'\t' | b'\r' | 0x0B | 0x0C)
38}
39
40/// Counts of the letters A–Z, case-insensitive (Easel's `ct[0..25]`).
41#[derive(Clone, Debug, Default, PartialEq, Eq)]
42pub struct LetterCounts([u64; 26]);
43
44impl LetterCounts {
45    /// Adds the letters of `bytes` (non-letters are ignored).
46    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    /// The letters of a byte histogram (`h[b]` = occurrences of byte `b`), case-insensitive.
56    #[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    /// Adds another tally.
67    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    /// Count of one upper-case letter.
74    #[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    /// Total letters.
81    #[must_use]
82    pub fn total(&self) -> u64 {
83        self.0.iter().sum()
84    }
85}
86
87/// Easel's `esl_abc_GuessAlphabet()`: the alphabet implied by a letter composition, or `None`
88/// when the composition does not determine it.
89///
90/// Rules, in order (n = total letters):
91/// 1. n ≤ 10 → unknown (too little evidence);
92/// 2. n > 2000 and all N → DNA (genome assemblies led by N runs);
93/// 3. any of `EFIJLOPQZ` → protein;
94/// 4. ≥ 98% `ACGTN` and all of A, C, G, T seen → DNA;
95/// 5. ≥ 98% `ACGUN` and all of A, C, G, U seen → RNA;
96/// 6. ≥ 98% amino-acid letters (or N, T, X), more `DHKMRSVWY` than `ACG`, and at least 15
97///    different letters seen → protein (as written in Easel this cannot fire: when rule 3 does not
98///    apply, at most 14 of these letters can occur; kept for fidelity);
99/// 7. otherwise unknown.
100#[must_use]
101#[allow(clippy::cast_precision_loss)] // Exactly as Easel: int64 counts compared in double.
102pub 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/// The alphabet decision for a run.
138#[derive(Clone, Debug, PartialEq, Eq)]
139pub struct Resolution {
140    /// The alphabet used.
141    pub alphabet: Alphabet,
142    /// Whether it was detected or given.
143    pub method: AlphabetMethod,
144    /// Letters examined.
145    pub residues_examined: u64,
146    /// Why the data contradict an explicit choice, if they do.
147    pub contradiction: Option<String>,
148}
149
150/// Resolves the alphabet from the user's choice and the probe's letter counts.
151///
152/// # Errors
153/// [`DimaError::InputData`] when no alphabet was given and the composition does not determine
154/// one, with a hint to pass `--alphabet`.
155pub 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
209/// `the first record` or `the first N records`.
210fn 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/// Per-byte classification and canonical spelling for one alphabet.
219///
220/// `canonical(b)` is the upper-case residue (with T/U folded) for residues and 0 for every
221/// other byte, so a k-mer is valid exactly when none of its canonical bytes is 0.
222#[derive(Clone, Debug)]
223pub struct ByteClassTable {
224    alphabet: Alphabet,
225    class: [ByteClass; 256],
226    canonical: [u8; 256],
227}
228
229impl ByteClassTable {
230    /// Builds the table for `alphabet`.
231    #[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    /// The alphabet of the table.
271    #[must_use]
272    pub const fn alphabet(&self) -> Alphabet {
273        self.alphabet
274    }
275
276    /// Class of a byte.
277    #[must_use]
278    pub const fn class(&self, b: u8) -> ByteClass {
279        self.class[b as usize]
280    }
281
282    /// Canonical residue for a residue byte, 0 for any other byte.
283    #[must_use]
284    pub const fn canonical(&self, b: u8) -> u8 {
285        self.canonical[b as usize]
286    }
287
288    /// `true` for the letter that is folded into the alphabet's spelling (U in DNA, T in RNA),
289    /// in either case.
290    #[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        // Missing T: not all four seen.
335        assert_eq!(guess(&counts("ACGACGACGACGA")), None);
336        // 2% tolerance: 1 foreign letter (R) in 50 is allowed, 2 in 50 is not.
337        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        // Both T and U substantially: neither DNA nor RNA.
344        assert_eq!(guess(&counts(&"ACGTU".repeat(20))), None);
345        // Rule 6 needs 15 distinct letters, but without the giveaway letters only 14 (ACG,
346        // DHKMRSVWY, N, T) can occur, so in the current Easel it never fires: a protein with none
347        // of EFIJLOPQZ stays unknown (and DiMA asks for --alphabet). The port keeps this.
348        assert_eq!(guess(&counts("MKVDHRSWYACGTNMKVDHRSWYNTKD")), None);
349        // Digits and punctuation are ignored.
350        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        // An explicit choice works even without evidence.
381        assert!(
382            resolve(Some(Alphabet::Rna), &counts(""), 0)
383                .unwrap()
384                .contradiction
385                .is_none()
386        );
387    }
388
389    /// Every byte value × every alphabet has exactly the documented class.
390    #[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}