PIntron

PIntron predicts gene structures by computing spliced alignments of transcript sequences (ESTs and mRNAs) to genomic sequences to identify exon–intron structures, transcript isoforms, and coding sequences.

Key Features:

• Linear-time spliced-alignment algorithm: Computes spliced alignments in time linear in the lengths of the transcript (P), the genomic sequence (T), and the size of the output.
• Redundancy exploitation: Leverages redundancies within transcript clusters by selecting factorizations of EST sequences that confirm splice-site junctions supported by input data.
• Maximal embeddings via embedding graph: Constructs maximal embeddings from paths in an embedding graph whose vertices represent maximal pairings between a genomic sequence (T) and an EST (P).
• Comprehensive output: Predicts full-length transcript isoforms and includes modules for coding sequence (CDS) annotation of predicted transcripts.
• Scalability: Designed to process large datasets (e.g., >20,000 ESTs and genes exceeding 1 megabase) while maintaining algorithmic efficiency.

Scientific Applications:

• Gene-structure prediction from EST/mRNA clusters: Inference of exon–intron architectures and alternative transcript isoforms from clustered transcript data.
• CDS annotation of predicted transcripts: Identification and annotation of coding sequences within predicted transcript models.
• Analysis of large or complex genomic regions: Application to long genes (>1 megabase) and large-scale EST datasets where high sensitivity and specificity are required.

Methodology:

Inputs: a genomic sequence or region and a set of ESTs and/or mRNAs; compute maximal pairings between T and P, build an embedding graph whose vertices are maximal pairings, derive maximal embeddings from paths in the embedding graph, select factorizations of ESTs that confirm splice junctions, perform the linear-time spliced-alignment algorithm, and annotate CDS on the predicted transcripts.