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 }]
);
}
}