rsomics-annotation 0.1.0

Typed GFF3 and GTF validation, selection, conversion, and sequence extraction
Documentation
use std::collections::{HashMap, hash_map::Entry};
use std::io::BufRead;

use noodles_gff::feature::record::{Phase, Strand};
use rsomics_common::{Result, RsomicsError};

use crate::annotation::{AnnotationLine, Dialect, FeatureRecord, for_each_line, invalid_line};
use crate::validate::Validator;

#[derive(Clone, Copy, Debug, Eq, PartialEq)]
pub(crate) struct Span {
    pub(crate) start: u64,
    pub(crate) end: u64,
}

impl Span {
    pub(crate) fn contains(self, position: u64) -> bool {
        self.start <= position && position <= self.end
    }

    pub(crate) fn overlaps(self, other: Self) -> bool {
        self.start <= other.end && other.start <= self.end
    }
}

#[derive(Debug)]
pub(crate) struct Transcript {
    pub(crate) id: Vec<u8>,
    pub(crate) seqid: Vec<u8>,
    pub(crate) reverse: bool,
    pub(crate) exons: Vec<Span>,
    pub(crate) coding: Option<Span>,
    rank: usize,
    start: u64,
    order: usize,
}

struct CodingSegment {
    span: Span,
    phase: u8,
}

struct Building {
    seqid: Vec<u8>,
    strand: Strand,
    start: u64,
    end: u64,
    rank: usize,
    order: usize,
    exons: Vec<Span>,
    coding: Vec<CodingSegment>,
}

impl Building {
    fn new(record: &FeatureRecord, rank: usize, order: usize) -> Self {
        Self {
            seqid: record.seqid().to_vec(),
            strand: record.strand(),
            start: record.start(),
            end: record.end(),
            rank,
            order,
            exons: Vec::new(),
            coding: Vec::new(),
        }
    }

    fn update(&mut self, id: &[u8], record: &FeatureRecord, line_number: usize) -> Result<()> {
        if self.seqid != record.seqid() {
            return Err(invalid_line(
                line_number,
                format!(
                    "transcript {:?} spans multiple reference sequences",
                    String::from_utf8_lossy(id)
                ),
            ));
        }

        match (direction(self.strand), direction(record.strand())) {
            (Some(existing), Some(incoming)) if existing != incoming => {
                return Err(invalid_line(
                    line_number,
                    format!(
                        "transcript {:?} has conflicting strands",
                        String::from_utf8_lossy(id)
                    ),
                ));
            }
            (None, Some(_)) => self.strand = record.strand(),
            _ => {}
        }

        self.start = self.start.min(record.start());
        self.end = self.end.max(record.end());
        Ok(())
    }
}

struct Builder {
    transcripts: HashMap<Vec<u8>, Building>,
    seqid_ranks: HashMap<Vec<u8>, usize>,
    next_order: usize,
}

impl Builder {
    fn new() -> Self {
        Self {
            transcripts: HashMap::new(),
            seqid_ranks: HashMap::new(),
            next_order: 0,
        }
    }

    fn observe(
        &mut self,
        line_number: usize,
        dialect: Dialect,
        line: &AnnotationLine,
    ) -> Result<()> {
        let AnnotationLine::Record(record) = line else {
            return Ok(());
        };
        let class = classify(record.ty());
        let ids = match class {
            FeatureClass::Transcript => transcript_id(record, dialect).into_iter().collect(),
            FeatureClass::Exon | FeatureClass::Coding => owners(record),
            FeatureClass::Other => return Ok(()),
        };

        for id in ids {
            let building = self.get_or_create(&id, record, line_number)?;
            match class {
                FeatureClass::Exon => building.exons.push(Span {
                    start: record.start(),
                    end: record.end(),
                }),
                FeatureClass::Coding => building.coding.push(CodingSegment {
                    span: Span {
                        start: record.start(),
                        end: record.end(),
                    },
                    phase: phase(record.phase()),
                }),
                FeatureClass::Transcript | FeatureClass::Other => {}
            }
        }
        Ok(())
    }

    fn get_or_create<'a>(
        &'a mut self,
        id: &[u8],
        record: &FeatureRecord,
        line_number: usize,
    ) -> Result<&'a mut Building> {
        let next_rank = self.seqid_ranks.len();
        let rank = *self
            .seqid_ranks
            .entry(record.seqid().to_vec())
            .or_insert(next_rank);

        match self.transcripts.entry(id.to_vec()) {
            Entry::Vacant(entry) => {
                let order = self.next_order;
                self.next_order += 1;
                Ok(entry.insert(Building::new(record, rank, order)))
            }
            Entry::Occupied(mut entry) => {
                entry.get_mut().update(id, record, line_number)?;
                Ok(entry.into_mut())
            }
        }
    }

    fn finish(self) -> Result<Vec<Transcript>> {
        let mut transcripts = Vec::with_capacity(self.transcripts.len());
        for (id, building) in self.transcripts {
            let reverse = direction(building.strand).ok_or_else(|| {
                RsomicsError::InvalidInput(format!(
                    "transcript {:?} requires a forward or reverse strand",
                    String::from_utf8_lossy(&id)
                ))
            })?;
            let exons = if !building.exons.is_empty() {
                merge_spans(building.exons)
            } else if !building.coding.is_empty() {
                merge_spans(building.coding.iter().map(|segment| segment.span).collect())
            } else {
                vec![Span {
                    start: building.start,
                    end: building.end,
                }]
            };
            let coding = coding_span(&id, &building.coding, reverse)?;
            transcripts.push(Transcript {
                id,
                seqid: building.seqid,
                reverse,
                exons,
                coding,
                rank: building.rank,
                start: building.start,
                order: building.order,
            });
        }
        transcripts.sort_by_key(|transcript| (transcript.rank, transcript.start, transcript.order));
        Ok(transcripts)
    }
}

pub(crate) fn load<R: BufRead>(input: R, dialect: Dialect) -> Result<Vec<Transcript>> {
    let mut validator = Validator::new(dialect);
    let mut builder = Builder::new();
    for_each_line(input, dialect, |line_number, line| {
        validator.observe(line_number, &line)?;
        builder.observe(line_number, dialect, &line)
    })?;
    validator.finish()?;
    builder.finish()
}

fn transcript_id(record: &FeatureRecord, dialect: Dialect) -> Option<Vec<u8>> {
    let key = match dialect {
        Dialect::Gff3 => b"ID".as_slice(),
        Dialect::Gtf => b"transcript_id".as_slice(),
    };
    record
        .attribute_values(key)
        .and_then(|values| values.first().map(|value| value.to_vec()))
}

fn owners(record: &FeatureRecord) -> Vec<Vec<u8>> {
    record
        .attribute_values(b"Parent")
        .or_else(|| record.attribute_values(b"transcript_id"))
        .unwrap_or_default()
        .into_iter()
        .map(<[u8]>::to_vec)
        .collect()
}

fn classify(ty: &[u8]) -> FeatureClass {
    let lower: Vec<u8> = ty.iter().map(u8::to_ascii_lowercase).collect();
    if matches!(lower.as_slice(), b"cds" | b"start_codon" | b"stop_codon") {
        FeatureClass::Coding
    } else if lower.ends_with(b"exon") || lower.windows(3).any(|window| window == b"utr") {
        FeatureClass::Exon
    } else if lower.ends_with(b"rna") || lower.ends_with(b"transcript") {
        FeatureClass::Transcript
    } else {
        FeatureClass::Other
    }
}

fn phase(value: Option<Phase>) -> u8 {
    match value {
        Some(Phase::One) => 1,
        Some(Phase::Two) => 2,
        Some(Phase::Zero) | None => 0,
    }
}

fn direction(strand: Strand) -> Option<bool> {
    match strand {
        Strand::Forward => Some(false),
        Strand::Reverse => Some(true),
        Strand::None | Strand::Unknown => None,
    }
}

fn merge_spans(mut spans: Vec<Span>) -> Vec<Span> {
    spans.sort_unstable_by_key(|span| span.start);
    let mut merged: Vec<Span> = Vec::with_capacity(spans.len());
    for span in spans {
        if let Some(previous) = merged.last_mut()
            && span.start <= previous.end.saturating_add(1)
        {
            previous.end = previous.end.max(span.end);
        } else {
            merged.push(span);
        }
    }
    merged
}

fn coding_span(id: &[u8], segments: &[CodingSegment], reverse: bool) -> Result<Option<Span>> {
    if segments.is_empty() {
        return Ok(None);
    }
    let start = segments
        .iter()
        .map(|segment| segment.span.start)
        .min()
        .ok_or_else(|| RsomicsError::InvalidInput("missing CDS start".to_owned()))?;
    let end = segments
        .iter()
        .map(|segment| segment.span.end)
        .max()
        .ok_or_else(|| RsomicsError::InvalidInput("missing CDS end".to_owned()))?;
    let boundary = if reverse {
        segments.iter().max_by_key(|segment| segment.span.end)
    } else {
        segments.iter().min_by_key(|segment| segment.span.start)
    }
    .ok_or_else(|| RsomicsError::InvalidInput("missing CDS boundary".to_owned()))?;
    let phase = u64::from(boundary.phase);
    let coding = if reverse {
        Span {
            start,
            end: end.saturating_sub(phase),
        }
    } else {
        Span {
            start: start + phase,
            end,
        }
    };
    if coding.start > coding.end {
        return Err(RsomicsError::InvalidInput(format!(
            "transcript {:?} phase {phase} inverts its coding span",
            String::from_utf8_lossy(id)
        )));
    }
    Ok(Some(coding))
}

#[derive(Clone, Copy)]
enum FeatureClass {
    Transcript,
    Exon,
    Coding,
    Other,
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn rejects_conflicting_transcript_sequences() {
        let input = b"##gff-version 3\n\
            chr1\tsrc\tmRNA\t1\t3\t.\t+\t.\tID=t1\n\
            chr2\tsrc\texon\t1\t3\t.\t+\t.\tParent=t1\n";
        let error = load(&input[..], Dialect::Gff3).unwrap_err();
        assert!(error.to_string().contains("multiple reference"), "{error}");
    }

    #[test]
    fn derives_exons_from_coding_segments() {
        let input = b"##gff-version 3\n\
            chr1\tsrc\tmRNA\t1\t12\t.\t+\t.\tID=t1\n\
            chr1\tsrc\tCDS\t1\t3\t.\t+\t0\tParent=t1\n\
            chr1\tsrc\tCDS\t10\t12\t.\t+\t0\tParent=t1\n";
        let transcripts = load(&input[..], Dialect::Gff3).unwrap();
        assert_eq!(
            transcripts[0].exons,
            [Span { start: 1, end: 3 }, Span { start: 10, end: 12 }]
        );
    }
}