Skip to main content

rsomics_count/
model.rs

1use std::collections::HashMap;
2
3use rsomics_common::{Result, RsomicsError};
4use rsomics_intervals::Interval;
5use smallvec::SmallVec;
6
7const BIN_SIZE: u64 = 16 * 1024;
8
9#[derive(Clone, Copy, Debug, Eq, PartialEq)]
10pub(crate) enum Strand {
11    Forward,
12    Reverse,
13    Unknown,
14}
15
16impl Strand {
17    pub(crate) fn parse(value: &str) -> Result<Self> {
18        match value {
19            "+" => Ok(Self::Forward),
20            "-" => Ok(Self::Reverse),
21            "." => Ok(Self::Unknown),
22            _ => Err(RsomicsError::InvalidInput(format!(
23                "invalid annotation strand {value:?}"
24            ))),
25        }
26    }
27
28    pub(crate) const fn as_str(self) -> &'static str {
29        match self {
30            Self::Forward => "+",
31            Self::Reverse => "-",
32            Self::Unknown => ".",
33        }
34    }
35}
36
37#[derive(Clone, Copy, Debug, Eq, PartialEq)]
38pub enum StrandMode {
39    Unstranded,
40    Sense,
41    Antisense,
42}
43
44#[derive(Clone, Copy, Debug, Eq, PartialEq)]
45pub enum CountLevel {
46    MetaFeature,
47    Feature,
48}
49
50#[derive(Clone, Debug)]
51pub(crate) struct Block {
52    pub(crate) chrom: Option<u32>,
53    pub(crate) start: u64,
54    pub(crate) end: u64,
55}
56
57pub(crate) type Blocks = SmallVec<[Block; 2]>;
58pub(crate) type Hits = SmallVec<[Hit; 4]>;
59
60impl Block {
61    pub(crate) fn new(chrom: Option<u32>, start: u64, end: u64) -> Result<Self> {
62        let interval = Interval::new((), start, end)
63            .map_err(|error| RsomicsError::InvalidInput(error.to_string()))?;
64        if interval.is_empty() {
65            return Err(RsomicsError::InvalidInput(
66                "alignment block has zero length".to_owned(),
67            ));
68        }
69        Ok(Self {
70            chrom,
71            start: interval.start(),
72            end: interval.end(),
73        })
74    }
75
76    pub(crate) const fn len(&self) -> u64 {
77        self.end - self.start
78    }
79}
80
81#[derive(Clone, Debug)]
82pub(crate) struct PartInput {
83    pub(crate) id: String,
84    pub(crate) chrom: String,
85    pub(crate) start: u64,
86    pub(crate) end: u64,
87    pub(crate) strand: Strand,
88}
89
90#[derive(Clone, Debug)]
91struct Part {
92    interval: Interval<String>,
93    chrom_id: u32,
94    strand: Strand,
95    row: usize,
96}
97
98#[derive(Clone, Debug)]
99pub(crate) struct FeatureRow {
100    id: String,
101    parts: Vec<usize>,
102    length: u64,
103}
104
105impl FeatureRow {
106    #[must_use]
107    pub(crate) fn id(&self) -> &str {
108        &self.id
109    }
110
111    #[must_use]
112    pub(crate) const fn length(&self) -> u64 {
113        self.length
114    }
115}
116
117#[derive(Clone, Debug)]
118pub(crate) struct FeatureSet {
119    rows: Vec<FeatureRow>,
120    parts: Vec<Part>,
121    chrom_ids: HashMap<String, u32>,
122    index: HashMap<u32, HashMap<u64, Vec<usize>>>,
123}
124
125#[derive(Clone, Copy, Debug, Eq, PartialEq)]
126pub(crate) struct Hit {
127    pub(crate) row: usize,
128    pub(crate) overlap_bases: u64,
129    pub(crate) feature_overlap_bases: u64,
130    pub(crate) feature_length: u64,
131}
132
133impl FeatureSet {
134    pub(crate) fn build(inputs: Vec<PartInput>, level: CountLevel) -> Result<Self> {
135        if inputs.is_empty() {
136            return Err(RsomicsError::InvalidInput(
137                "annotation contains no selected features".to_owned(),
138            ));
139        }
140
141        let mut rows = Vec::<FeatureRow>::new();
142        let mut parts = Vec::<Part>::with_capacity(inputs.len());
143        let mut groups = HashMap::<String, usize>::new();
144        let mut chrom_ids = HashMap::<String, u32>::new();
145
146        for input in inputs {
147            let next_chrom_id = u32::try_from(chrom_ids.len()).map_err(|_| {
148                RsomicsError::InvalidInput("too many annotation chromosomes".to_owned())
149            })?;
150            let chrom_id = *chrom_ids
151                .entry(input.chrom.clone())
152                .or_insert(next_chrom_id);
153            let interval = Interval::new(input.chrom, input.start, input.end)
154                .map_err(|error| RsomicsError::InvalidInput(error.to_string()))?;
155            if interval.is_empty() {
156                return Err(RsomicsError::InvalidInput(format!(
157                    "feature {} has zero length",
158                    input.id
159                )));
160            }
161            let row = match level {
162                CountLevel::Feature => {
163                    let row = rows.len();
164                    rows.push(FeatureRow {
165                        id: input.id,
166                        parts: Vec::new(),
167                        length: 0,
168                    });
169                    row
170                }
171                CountLevel::MetaFeature => match groups.get(&input.id).copied() {
172                    Some(row) => row,
173                    None => {
174                        let row = rows.len();
175                        groups.insert(input.id.clone(), row);
176                        rows.push(FeatureRow {
177                            id: input.id,
178                            parts: Vec::new(),
179                            length: 0,
180                        });
181                        row
182                    }
183                },
184            };
185            let part = parts.len();
186            parts.push(Part {
187                interval,
188                chrom_id,
189                strand: input.strand,
190                row,
191            });
192            rows[row].parts.push(part);
193        }
194
195        for row in &mut rows {
196            row.length = union_length(row.parts.iter().map(|&part| &parts[part]));
197        }
198
199        let mut index: HashMap<u32, HashMap<u64, Vec<usize>>> = HashMap::new();
200        for (part_index, part) in parts.iter().enumerate() {
201            let first = part.interval.start() / BIN_SIZE;
202            let last = (part.interval.end() - 1) / BIN_SIZE;
203            let bins = index.entry(part.chrom_id).or_default();
204            for bin in first..=last {
205                bins.entry(bin).or_default().push(part_index);
206            }
207        }
208
209        Ok(Self {
210            rows,
211            parts,
212            chrom_ids,
213            index,
214        })
215    }
216
217    #[must_use]
218    pub(crate) fn rows(&self) -> &[FeatureRow] {
219        &self.rows
220    }
221
222    pub(crate) fn chrom_id(&self, name: &str) -> Option<u32> {
223        self.chrom_ids.get(name).copied()
224    }
225
226    pub(crate) fn hits(
227        &self,
228        blocks: &[Block],
229        strand_mode: StrandMode,
230        reverse: bool,
231        track_feature_fraction: bool,
232    ) -> Hits {
233        let mut candidates = SmallVec::<[usize; 16]>::new();
234        for block in blocks {
235            let Some(chrom) = block.chrom else {
236                continue;
237            };
238            let Some(bins) = self.index.get(&chrom) else {
239                continue;
240            };
241            let first = block.start / BIN_SIZE;
242            let last = (block.end - 1) / BIN_SIZE;
243            for bin in first..=last {
244                if let Some(parts) = bins.get(&bin) {
245                    candidates.extend_from_slice(parts);
246                }
247            }
248        }
249        candidates.sort_unstable();
250        candidates.dedup();
251
252        let mut intersections = SmallVec::<[(usize, u32, u64, u64); 16]>::new();
253        let mut feature_overlaps = SmallVec::<[(usize, u64, u64); 16]>::new();
254        for part_index in candidates {
255            let part = &self.parts[part_index];
256            if !strand_matches(part.strand, strand_mode, reverse) {
257                continue;
258            }
259            let mut part_intersections = SmallVec::<[(u64, u64); 4]>::new();
260            for block in blocks
261                .iter()
262                .filter(|block| block.chrom == Some(part.chrom_id))
263            {
264                let start = block.start.max(part.interval.start());
265                let end = block.end.min(part.interval.end());
266                if start < end {
267                    intersections.push((part.row, part.chrom_id, start, end));
268                    if track_feature_fraction {
269                        part_intersections.push((start, end));
270                    }
271                }
272            }
273            if track_feature_fraction {
274                let overlap = union_interval_length(&mut part_intersections);
275                if overlap > 0 {
276                    feature_overlaps.push((part.row, overlap, part.interval.len()));
277                }
278            }
279        }
280        union_hits(intersections, feature_overlaps)
281    }
282
283    pub(crate) fn fields(&self, row: usize) -> (String, String, String, String) {
284        let row = &self.rows[row];
285        let mut chrom = Vec::with_capacity(row.parts.len());
286        let mut start = Vec::with_capacity(row.parts.len());
287        let mut end = Vec::with_capacity(row.parts.len());
288        let mut strand = Vec::with_capacity(row.parts.len());
289        for &part in &row.parts {
290            let part = &self.parts[part];
291            chrom.push(part.interval.chrom());
292            start.push((part.interval.start() + 1).to_string());
293            end.push(part.interval.end().to_string());
294            strand.push(part.strand.as_str());
295        }
296        (
297            chrom.join(";"),
298            start.join(";"),
299            end.join(";"),
300            strand.join(";"),
301        )
302    }
303}
304
305fn strand_matches(feature: Strand, mode: StrandMode, reverse: bool) -> bool {
306    match mode {
307        StrandMode::Unstranded => true,
308        StrandMode::Sense => matches!(
309            (feature, reverse),
310            (Strand::Forward, false) | (Strand::Reverse, true)
311        ),
312        StrandMode::Antisense => matches!(
313            (feature, reverse),
314            (Strand::Forward, true) | (Strand::Reverse, false)
315        ),
316    }
317}
318
319fn union_length<'a>(parts: impl Iterator<Item = &'a Part>) -> u64 {
320    union_tuples(
321        parts
322            .map(|part| {
323                (
324                    part.interval.chrom().to_owned(),
325                    part.interval.start(),
326                    part.interval.end(),
327                )
328            })
329            .collect(),
330    )
331}
332
333fn union_tuples(mut intervals: Vec<(String, u64, u64)>) -> u64 {
334    intervals.sort_unstable_by(|left, right| {
335        left.0
336            .cmp(&right.0)
337            .then(left.1.cmp(&right.1))
338            .then(left.2.cmp(&right.2))
339    });
340    let mut total = 0;
341    let mut current: Option<(String, u64, u64)> = None;
342    for (chrom, start, end) in intervals {
343        match current.as_mut() {
344            Some((current_chrom, _, current_end))
345                if *current_chrom == chrom && start <= *current_end =>
346            {
347                *current_end = (*current_end).max(end);
348            }
349            Some((_, current_start, current_end)) => {
350                total += *current_end - *current_start;
351                current = Some((chrom, start, end));
352            }
353            None => current = Some((chrom, start, end)),
354        }
355    }
356    if let Some((_, start, end)) = current {
357        total += end - start;
358    }
359    total
360}
361
362fn union_interval_length(intervals: &mut SmallVec<[(u64, u64); 4]>) -> u64 {
363    intervals.sort_unstable();
364    let mut total = 0;
365    let mut current = None;
366    for (start, end) in intervals.drain(..) {
367        match current.as_mut() {
368            Some((_, current_end)) if start <= *current_end => {
369                *current_end = (*current_end).max(end);
370            }
371            Some((current_start, current_end)) => {
372                total += *current_end - *current_start;
373                current = Some((start, end));
374            }
375            None => current = Some((start, end)),
376        }
377    }
378    if let Some((start, end)) = current {
379        total += end - start;
380    }
381    total
382}
383
384fn union_hits(
385    mut intervals: SmallVec<[(usize, u32, u64, u64); 16]>,
386    feature_overlaps: SmallVec<[(usize, u64, u64); 16]>,
387) -> Hits {
388    let mut best = HashMap::<usize, (u64, u64)>::new();
389    for (row, overlap, length) in feature_overlaps {
390        let candidate = (overlap, length);
391        let current = best.entry(row).or_insert(candidate);
392        if u128::from(overlap) * u128::from(current.1) > u128::from(current.0) * u128::from(length)
393        {
394            *current = candidate;
395        }
396    }
397    intervals.sort_unstable();
398    let mut hits = Hits::new();
399    let mut current: Option<(usize, u32, u64, u64)> = None;
400    let mut row_total = 0;
401    for (row, chrom, start, end) in intervals {
402        match current.as_mut() {
403            Some((current_row, current_chrom, _, current_end))
404                if *current_row == row && *current_chrom == chrom && start <= *current_end =>
405            {
406                *current_end = (*current_end).max(end);
407            }
408            Some((current_row, _, current_start, current_end)) => {
409                row_total += *current_end - *current_start;
410                if *current_row != row {
411                    let (feature_overlap_bases, feature_length) =
412                        best.get(current_row).copied().unwrap_or((1, 1));
413                    hits.push(Hit {
414                        row: *current_row,
415                        overlap_bases: row_total,
416                        feature_overlap_bases,
417                        feature_length,
418                    });
419                    row_total = 0;
420                }
421                current = Some((row, chrom, start, end));
422            }
423            None => current = Some((row, chrom, start, end)),
424        }
425    }
426    if let Some((row, _, start, end)) = current {
427        row_total += end - start;
428        let (feature_overlap_bases, feature_length) = best.get(&row).copied().unwrap_or((1, 1));
429        hits.push(Hit {
430            row,
431            overlap_bases: row_total,
432            feature_overlap_bases,
433            feature_length,
434        });
435    }
436    hits
437}
438
439#[cfg(test)]
440mod tests {
441    use super::*;
442
443    fn part(id: &str, start: u64, end: u64, strand: Strand) -> PartInput {
444        PartInput {
445            id: id.to_owned(),
446            chrom: "chr1".to_owned(),
447            start,
448            end,
449            strand,
450        }
451    }
452
453    #[test]
454    fn meta_feature_length_is_a_union() {
455        let features = FeatureSet::build(
456            vec![
457                part("g", 300, 350, Strand::Forward),
458                part("g", 340, 400, Strand::Forward),
459            ],
460            CountLevel::MetaFeature,
461        )
462        .unwrap();
463        assert_eq!(features.rows()[0].length(), 100);
464    }
465
466    #[test]
467    fn query_deduplicates_overlapping_parts_and_blocks() {
468        let features = FeatureSet::build(
469            vec![
470                part("g", 100, 150, Strand::Forward),
471                part("g", 140, 200, Strand::Forward),
472            ],
473            CountLevel::MetaFeature,
474        )
475        .unwrap();
476        let hits = features.hits(
477            &[Block::new(Some(0), 130, 170).unwrap()],
478            StrandMode::Unstranded,
479            false,
480            false,
481        );
482        assert_eq!(hits[0].overlap_bases, 40);
483    }
484
485    #[test]
486    fn strand_modes_filter_candidates() {
487        let features = FeatureSet::build(
488            vec![
489                part("plus", 100, 200, Strand::Forward),
490                part("minus", 100, 200, Strand::Reverse),
491            ],
492            CountLevel::MetaFeature,
493        )
494        .unwrap();
495        let block = Block::new(Some(0), 120, 140).unwrap();
496        assert_eq!(
497            features.hits(
498                std::slice::from_ref(&block),
499                StrandMode::Sense,
500                false,
501                false,
502            )[0]
503            .row,
504            0
505        );
506        assert_eq!(
507            features.hits(&[block], StrandMode::Antisense, false, false)[0].row,
508            1
509        );
510    }
511}