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

Authors: Jerzy W. Jaromczyk; Neil Moore; Christopher L. Schardl

Addresses: Department of Computer Science, University of Kentucky, Lexington, KY, USA. ' Department of Computer Science, University of Kentucky, Lexington, KY, USA. ' Department of Plant Pathology, University of Kentucky, Lexington, KY, USA

Abstract: 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.

Keywords: molecular sequence analysis; splice graphs; alternative splicing; ORF; open reading frames; molecular sequences; protein encoding; alternatively spliced genes.

DOI: 10.1504/IJCBDD.2012.049212

International Journal of Computational Biology and Drug Design, 2012 Vol.5 No.3/4, pp.284 - 297

Published online: 05 Dec 2014 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article