Skip Navigation

This Article
Right arrow Full Text (Print PDF)
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by Xu, Y.
Right arrow Articles by Uberbacher, E. C.
Right arrow Search for Related Content
PubMed
Right arrow Articles by Xu, Y.
Right arrow Articles by Uberbacher, E. C.
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

© Oxford University Press

Constructing gene models from accurately predicted exons: an application of dynamic programming

Ying Xu , Richard J. Mural 1 and Edward C. Uberbacher 2

Informatics Group, Engineering Physics and Mathematics Division Oak Ridge, TN 37831-6364, USA
1Biology Division, Oak Ridge National Laboratory Oak Ridge, TN 37831-6364, USA

2To whom reprint requests should be sent

This paper presents a computationally efficient algorithm, the Gene Assembly Program III (GAP III), for constructing gene models from a set of accurately-predicted ‘exons’. The input to the algorithm is a set of clusters of exon candidates, generated by a new version of the GRAIL coding region recognition system. The exon candidates of a cluster differ in their presumed edges and occasionally in their reading frames. Each exon candidate has a numerical score representing its ‘probability’ of being an actual exon. GAP III uses a dynamic programming algorithm to construct a gene model, complete or partial, by optimizing a predefined objective function. The optimal gene models constructed by GAP III correspond very well with the structures of genes which have been determined experimentally and reported in the Genome Sequence Database (GSDB). On a test set of 137 human and mouse DNA sequences consisting of 954 true exons, GAP III constructed 137 gene models using 892 exons, among which 859 (859/954 = 90%) are true exons and 33 (33/892 = 3%) are false positive. Among the 859 true positives, 635 (74%) match the actual exons exactly, and 838 (98%) have at least one edge correct. GAP III is computationally efficient. If we use E and C to represent the total number of exon candidates in all clusters and the number of clusters, respectively, the running time of GAP III is proportional to (E x C).


Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?


This article has been cited by other articles:


Home page
 Genome ResHome page
D. Kotlar and Y. Lavner
Gene Prediction by Spectral Rotation Measure: A New Method for Identifying Protein-Coding Regions
Genome Res., August 1, 2003; 13(8): 1930 - 1937.
[Abstract] [Full Text] [PDF]

Home page
 Nucleic Acids ResHome page
C. Mathe, M.-F. Sagot, T. Schiex, and P. Rouze
Current methods of gene prediction, their strengths and weaknesses
Nucleic Acids Res., October 1, 2002; 30(19): 4103 - 4117.
[Abstract] [Full Text] [PDF]

Home page
 Genome ResHome page
K. L. Howe, T. Chothia, and R. Durbin
GAZE: A Generic Framework for the Integration of Gene-Prediction Data by Dynamic Programming
Genome Res., September 1, 2002; 12(9): 1418 - 1427.
[Abstract] [Full Text] [PDF]

Home page
 Cancer Res.Home page
Y. Daigo, T. Nishiwaki, T. Kawasoe, M. Tamari, E. Tsuchiya, and Y. Nakamura
Molecular Cloning of a Candidate Tumor Suppressor Gene, DLC1, from Chromosome 3p21.3
Cancer Res., April 1, 1999; 59(8): 1966 - 1972.
[Abstract] [Full Text] [PDF]

Home page
 Genome ResHome page
W. S. Hayes and M. Borodovsky
How to Interpret an Anonymous Bacterial Genome: Machine Learning Approach to Gene Identification
Genome Res., November 1, 1998; 8(11): 1154 - 1171.
[Abstract] [Full Text]

Home page
 J. Biol. Chem.Home page
S. M. Mühlebach, T. Wirz, U. Brändle, and J.-C. Perriard
Evolution of the Creatine Kinases
J. Biol. Chem., May 17, 1996; 271(20): 11920 - 11929.
[Abstract] [Full Text] [PDF]


Disclaimer:
Please note that abstracts for content published before 1996 were created through digital scanning and may therefore not exactly replicate the text of the original print issues. All efforts have been made to ensure accuracy, but the Publisher will not be held responsible for any remaining inaccuracies. If you require any further clarification, please contact our Customer Services Department.