A linear-time algorithm for finding a maximum-length ORF in a splice graph

We present a linear-time, deterministic algorithm for finding a longest Open Reading Frame (ORF) in an alternatively spliced gene represented by a splice graph. Finding protein-encoding regions is a fundamental problem in genomic and transcriptomic analysis, and in some circumstances long ORFs can provide good predictions of such regions. Splice graphs are a common way of compactly representing what may be exponentially many alternative splicings of a sequence. The efficiency of our algorithm is achieved by pruning the search space so as to bound the number of reading frames considered at any vertex of the splice graph. The algorithm guarantees that the unpruned reading frames contain at least one longest ORF of the gene. We are therefore able to find a longest ORF among all splice variants in time linear in the size of the splice graph, even though the number of potential transcripts may be much larger.