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

Jerzy W. Jaromczyk, Neil Moore, Christopher L. Schardl

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish
Pages (from-to)284-297
Number of pages14
JournalInternational Journal of Computational Biology and Drug Design
Issue number3-4
StatePublished - Sep 2012


  • Alternative splicing
  • Molecular sequence analysis
  • ORF
  • Open reading frames
  • Splice graphs

ASJC Scopus subject areas

  • Drug Discovery
  • Computer Science Applications


Dive into the research topics of 'A linear-time algorithm for finding a maximum-length ORF in a splice graph'. Together they form a unique fingerprint.

Cite this