Skip to main content

dima_core/
hcs.rs

1//! Historically conserved sequences (HCS; Tharanga et al. 2025; D12, D44, D86).
2//!
3//! A position *qualifies* when its Index k-mer reaches the threshold incidence, compared
4//! exactly (count × 100 ≥ threshold × support in integers). Above 50% the Index variant is
5//! unique, so a qualifying position has exactly one conserved k-mer. Consecutive qualifying
6//! k-mers are joined into one region when they overlap or abut (as in Abd Raman et al. 2020) and
7//! agree on every overlapping column; a disagreement starts a new region marked
8//! `split_from_previous`.
9//!
10//! **Low support (D86).** Like the paper and DiMA v5.0.9, any position may qualify. Each region
11//! lists the positions in its span with support ≤ T and is *flagged* when there are any — the
12//! practice of Abd Raman et al. 2020 (conserved-sequence tables with low-support positions
13//! asterisked) and Hu et al. 2013 — and reports the exact 95% Clopper–Pearson lower bound of
14//! its members' conservation (Clopper & Pearson 1934): a k-mer shared by 3 of 3 sequences is
15//! "100% conserved" but only bounded below by 29.2%. With `eligible_only`, only positions
16//! with support > T qualify and NS/LS/ELS positions end regions (the analysis set of Hu et al.
17//! 2013; cf. Gblocks, Castresana 2000).
18
19use crate::config::Percent;
20use crate::diagnostics::{Code, Diagnostic, Tally, agree, plural};
21use crate::error::{DimaError, Result};
22use crate::model::{
23    HcsConfidence, HcsEligibility, HcsMember, HcsParameters, HcsRegion, HcsResults, HcsSource,
24    Motif, Reference, Results, SCHEMA_VERSION, ToolInfo,
25};
26use crate::numeric::clopper_pearson_lower;
27
28/// Confidence level of the reported lower bounds.
29pub const CONFIDENCE_LEVEL: f64 = 0.95;
30
31/// Citation keys of the HCS method.
32pub const REFERENCES: &[&str] = &["tharanga2025", "raman2020", "hu2013", "clopper1934"];
33/// Also cited with `eligible_only`: low-support columns end blocks, as in Gblocks.
34pub const ELIGIBLE_ONLY_REFERENCE: &str = "castresana2000";
35
36/// HCS parameters.
37#[derive(Clone, Copy, Debug, PartialEq, Eq)]
38pub struct HcsParams {
39    /// Minimum Index incidence, in (50, 100].
40    pub threshold: Percent,
41    /// Only positions with support above the threshold may qualify.
42    pub eligible_only: bool,
43}
44
45impl Default for HcsParams {
46    fn default() -> Self {
47        Self {
48            threshold: crate::config::DEFAULT_HCS_THRESHOLD,
49            eligible_only: false,
50        }
51    }
52}
53
54/// Exact two-sided 95% Clopper–Pearson lower bound of `count / support`.
55#[must_use]
56pub fn lower_bound_95(count: u64, support: u64) -> f64 {
57    clopper_pearson_lower(count, support, (1.0 - CONFIDENCE_LEVEL) / 2.0)
58}
59
60struct Open {
61    start: u64,
62    end: u64,
63    sequence: String,
64    split_from_previous: bool,
65    members: Vec<HcsMember>,
66}
67
68/// Computes the conserved regions of a results set.
69///
70/// # Errors
71/// [`DimaError::InputData`] if the results' positions are not 1, 2, … in order, or the
72/// threshold is outside (50, 100].
73pub fn compute(results: &Results, params: &HcsParams) -> Result<HcsResults> {
74    params.threshold.check_hcs_range()?;
75    let positions = &results.results;
76    if positions
77        .iter()
78        .enumerate()
79        .any(|(i, p)| p.position != i as u64 + 1)
80    {
81        return Err(DimaError::input_data(
82            None,
83            "the results' positions are not consecutive from 1",
84        )
85        .with_hint("compute conserved regions from a complete DiMA results file"));
86    }
87    let k = results.kmer_length;
88    let t = results.support_threshold;
89    let low = |pos: u64| positions[(pos - 1) as usize].support <= t;
90    let mut regions: Vec<Open> = Vec::new();
91    for p in positions {
92        if params.eligible_only && p.support <= t {
93            continue;
94        }
95        let Some(index) = p.diversity_motifs.iter().find(|v| v.motif == Motif::Index) else {
96            continue;
97        };
98        if !params.threshold.is_met_by(index.count, p.support) {
99            continue;
100        }
101        let member = HcsMember {
102            position: p.position,
103            kmer: index.sequence.clone(),
104            count: index.count,
105            support: p.support,
106            incidence: index.incidence,
107            conservation_lower_bound_95: lower_bound_95(index.count, p.support),
108        };
109        let mut split = false;
110        if let Some(r) = regions.last_mut() {
111            let last = r.members.last().map_or(r.start, |m| m.position);
112            let adjacent = p.position <= r.end + 1;
113            if adjacent {
114                let overlap = (r.end + 1 - p.position) as usize;
115                let tail = &r.sequence[r.sequence.len() - overlap..];
116                let agrees = tail.as_bytes() == &member.kmer.as_bytes()[..overlap];
117                let unbroken = !params.eligible_only || !(last + 1..p.position).any(low);
118                if agrees && unbroken {
119                    r.sequence.push_str(&member.kmer[overlap..]);
120                    r.end = p.position + k - 1;
121                    r.members.push(member);
122                    continue;
123                }
124                // Set whenever an overlapping k-mer disagrees, whatever else ends the region.
125                split = !agrees;
126            }
127        }
128        regions.push(Open {
129            start: p.position,
130            end: p.position + k - 1,
131            sequence: member.kmer.clone(),
132            split_from_previous: split,
133            members: vec![member],
134        });
135    }
136    let regions: Vec<HcsRegion> = regions
137        .into_iter()
138        .enumerate()
139        .map(|(i, r)| {
140            let first = r.members[0].position;
141            let last = r.members.last().map_or(first, |m| m.position);
142            let low_support_positions: Vec<u64> = (first..=last).filter(|&q| low(q)).collect();
143            HcsRegion {
144                id: i as u64 + 1,
145                start_column: r.start,
146                end_column: r.end,
147                length: r.end - r.start + 1,
148                sequence: r.sequence,
149                min_incidence: r
150                    .members
151                    .iter()
152                    .map(|m| m.incidence)
153                    .fold(f64::INFINITY, f64::min),
154                min_support: r.members.iter().map(|m| m.support).min().unwrap_or(0),
155                conservation_lower_bound_95: r
156                    .members
157                    .iter()
158                    .map(|m| m.conservation_lower_bound_95)
159                    .fold(f64::INFINITY, f64::min),
160                flagged: !low_support_positions.is_empty(),
161                low_support_positions,
162                split_from_previous: r.split_from_previous,
163                members: r.members,
164            }
165        })
166        .collect();
167    let flagged: Vec<&HcsRegion> = regions.iter().filter(|r| r.flagged).collect();
168    let mut diagnostics = Vec::new();
169    if !flagged.is_empty() {
170        let mut tally = Tally::default();
171        for r in &flagged {
172            tally.add(1, || {
173                format!(
174                    "region {} (columns {} to {}): min support {}, lower bound {:.1}%",
175                    r.id,
176                    r.start_column,
177                    r.end_column,
178                    r.min_support,
179                    r.conservation_lower_bound_95 * 100.0
180                )
181            });
182        }
183        diagnostics.push(
184            Diagnostic::new(
185                Code::HcsLowSupportRegions,
186                format!(
187                    "{} of {} {} positions with support at or below the threshold ({t}); {} \
188                     conservation rests on few sequences",
189                    flagged.len(),
190                    plural(
191                        regions.len() as u64,
192                        "conserved region",
193                        "conserved regions"
194                    ),
195                    agree(flagged.len() as u64, "includes", "include"),
196                    agree(flagged.len() as u64, "its", "their")
197                ),
198                tally,
199            )
200            .with_hint(
201                "see each region's conservation_lower_bound_95, or use --hcs-eligible-only to \
202                 build regions from positions with support above the threshold only",
203            ),
204        );
205    }
206    tracing::debug!(
207        regions = regions.len(),
208        flagged = flagged.len(),
209        eligible_only = params.eligible_only,
210        "conserved sequences computed"
211    );
212    Ok(HcsResults {
213        schema_version: SCHEMA_VERSION.to_owned(),
214        tool: ToolInfo {
215            name: "dima".to_owned(),
216            version: crate::citations::SOFTWARE_VERSION.to_owned(),
217        },
218        source: HcsSource {
219            query_name: results.query_name.clone(),
220            kmer_length: k,
221            support_threshold: t,
222            sequence_count: results.sequence_count,
223            input_checksum: results.run.input.checksum.clone(),
224            tool_version: results.run.tool.version.clone(),
225            results_schema_version: results.schema_version.clone(),
226        },
227        parameters: HcsParameters {
228            threshold_percent: params.threshold,
229            merge_rule: "overlap_or_adjacent".to_owned(),
230            eligibility: if params.eligible_only {
231                HcsEligibility::SupportGtThreshold
232            } else {
233                HcsEligibility::AllPositions
234            },
235            confidence: HcsConfidence {
236                method: "clopper_pearson".to_owned(),
237                level: CONFIDENCE_LEVEL,
238            },
239        },
240        region_count: regions.len() as u64,
241        flagged_region_count: flagged.len() as u64,
242        regions,
243        diagnostics,
244        references: REFERENCES
245            .iter()
246            .chain(params.eligible_only.then_some(&ELIGIBLE_ONLY_REFERENCE))
247            .map(|k| Reference::of(k))
248            .collect(),
249    })
250}