A linear-time algorithm for finding a maximum-length ORF in a splice graph Online publication date: Fri, 05-Dec-2014
by Jerzy W. Jaromczyk; Neil Moore; Christopher L. Schardl
International Journal of Computational Biology and Drug Design (IJCBDD), Vol. 5, No. 3/4, 2012
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.
Existing subscribers:
Go to Inderscience Online Journals to access the Full Text of this article.
If you are not a subscriber and you just want to read the full contents of this article, buy online access here.Complimentary Subscribers, Editors or Members of the Editorial Board of the International Journal of Computational Biology and Drug Design (IJCBDD):
Login with your Inderscience username and password:
Want to subscribe?
A subscription gives you complete access to all articles in the current issue, as well as to all articles in the previous three years (where applicable). See our Orders page to subscribe.
If you still need assistance, please email subs@inderscience.com
Our Blog 
Follow us on Twitter 
Visit us on Facebook