GENSCAN explained

GENSCAN
Developer:	Christopher Burge
Language:	English
Genre:	Bioinformatics tool

In bioinformatics, GENSCAN is a program to identify complete gene structures in genomic DNA. It is a GHMM-based program that can be used to predict the location of genes and their exon-intron boundaries in genomic sequences from a variety of organisms. The GENSCAN Web server can be found at MIT.^[1]

GENSCAN was developed by Christopher Burge in the research group of Samuel Karlin at Stanford University.^[2] ^[3] ^[4]

History

In 2001, the world of human gene prediction entered into Comparative genomics. This resulted in the development of a program called TWINSCAN as an adaptation of GENSCAN with higher accuracy. Other programs like N-SCAN were later developed by further adapting the GHMM model.^[5]

As of 2002, GENSCAN remained a popular tool in bioinformatics, becoming a standard feature for genomes released on University of California Santa Cruz and Ensembl Genome browser.

Implementation

Genomic Model

The primary goal when developing a genomic sequence model for GENSCAN was to identify both the general and specific properties that compose the individual functional units of eukaryotic genes (e.g. exons, introns, splice sites, promoters). Particular focus was placed upon features that are recognizable by general transcriptional, splicing and translational machinery that processes the majority of all protein coding genes, as opposed to the signals associated with transcription or splicing of genes and gene families (e.g. TATA box). In addition, a general three-periodic fifth-order Markov model of coding regions is used as opposed to models of specific protein motifs or database homology information. In addition, the model factors in the structural and density differences between compositional regions of the human genome.

Due to the usage of these elements, GENSCAN works without needing to reference similar genes in protein sequence databases. Instead, predictions produced by GENSCAN are complementary to those gathered by homology-based gene identification methods (e.g. querying protein databases with BLASTX). Overall, the structure of the model used in GENSCAN is similar to the General Hidden Markov Model.

Features

GENSCAN's implementation differs from other programs in multiple ways. A notable difference is the fact that GENSCAN utilizes a genomic sequence model that exclusively focuses double-stranded DNA where genes that are present on both strands are simultaneously analyzed. Also, GENSCAN is capable of analyzing genomes in situations where there are partial genes or no genes, rather than only being able to analyze single and complete gene sequences like other programs at its time. These two factors contribute to GENSCAN being particularly useful in analyzing longer human genomes. In addition, GENSCAN employs the concept of Maximal Dependence Decomposition such that functional signals in DNA and protein sequences can be modeled, creating the possibility for dependencies between signal positions to be considered by the program. This is implemented in GENSCAN such that a model is generated of the donor splice signal, capturing dependences that are associated with the recognition mechanisms for donor splice sites in pre-mRNA sequences.

GENSCAN has the capability of calculating the accuracy of each of its predictions by using the forward-backward algorithm.

Predicting the structure and overall composition of human genes in regard to exon and gene locations in longer sequences is an additionally useful component of GENSCAN. There are several different features that come as a part of this. One of which being the capability of capturing differences in gene structure and composition between C + G regions in the human genome, using sets of empirically generated model parameters. Another derived feature is, as mentioned before, predicting multiple genes in a sequence in addition to having the ability of working with partial genes and double-stranded DNA. Lastly, this also allows GENSCAN to capture dependencies between signal positions with new models of donor and acceptor splice sites.

Efficiency

The run time for GENSCAN scales almost linearly when provided realistically sized sequences (several kilobits minimum), but has a worst case of being quadratic.

Supplemental Usage

GENSCAN, like other genome prediction programs, doesn't produce results that totally match those of other programs. This is due to a multitude of factors including, but not limited to: differences in algorithms, parameters, and training sets. Therefore, GENSCAN has been utilized in the practice of combining two gene prediction programs' results such that if one program in the combination is confident in a sequence prediction, that sequence is used. On the other hand, if neither program is confident in their predictions, the sequence predicted is only used if both programs agree on it.

Accuracy

Tests were conducted to evaluate the accuracy of GENSCAN with short data sets. One test was done on the Burset/Guigó dataset containing 570 vertebrate multi-exon gene sequences. The data produced from this test is shown in the table below, along with the data produced by testing other programs with the same dataset. GENSCAN is shown in the table to be generally more accurate than its competitors at predicting sequences with both nucleotides and exons.

GENSCAN Accuracy vs. Other Programs!Program!Sequences!Nucleotide Sensitivity!Nucleotide Specificity!Nucleotide Approximate Correlation!Nucleotide Correlation Coefficient!Exon Sensitivity!Exon Specificity!Exon Average!Missed Exons!Wrong Exons
GENSCAN	570	0.93	0.93	0.91	0.92	0.78	0.81	0.80	0.09	0.05
FGENEH	569	0.77	0.88	0.78	0.80	0.61	0.64	0.64	0.15	0.12
GeneID	570	0.63	0.81	0.67	0.65	0.44	0.46	0.45	0.28	0.24
Genie	570	0.76	0.77	0.72	n/a	0.55	0.48	0.51	0.17	0.33
GenLang	570	0.72	0.79	0.69	0.71	0.51	0.52	0.52	0.21	0.22
GeneParser2	562	0.66	0.79	0.67	0.65	0.35	0.40	0.37	0.34	0.17
GRAIL2	570	0.72	0.87	0.75	0.76	0.36	0.43	0.40	0.25	0.11
SORFIND	561	0.71	0.85	0.73	0.72	0.42	0.47	0.45	0.24	0.14
Xpound	570	0.61	0.87	0.68	0.69	0.15	0.18	0.17	0.33	0.13
GeneID+	478	0.91	0.91	0.88	0.88	0.73	0.70	0.71	0.07	0.13
GeneParser3	478	0.86	0.91	0.86	0.85	0.56	0.58	0.57	0.14	0.09

Furthermore, the table shown below specifically describes the accuracy of GENSCAN in regard to genomic sequences organized by ranges of C + G and types of organisms. We can see in the data provided that GENSCAN's accuracy variation was rather insensitive to C + G content and organism type. This further demonstrates GENSCAN's independence of factors that would have impacted the results of comparable genome prediction programs.

GENSCAN Accuracy for Sequences Organized by C+G Content and Organism!Subset!Sequences!Nucleotide Sensitivity!Nucleotide Specificity!Nucleotide Approximate Correlation!Nucleotide Correlation Coefficient!Exon Sensitivity!Exon Specificity!Exon Average!Missed Exons!Wrong Exons
C + G <40	86	0.90	0.95	0.90	0.93	0.78	0.87	0.84	0.14	0.05
C + G 40-50	220	0.94	0.92	0.91	0.91	0.80	0.82	0.82	0.08	0.05
C + G 50-60	208	0.93	0.93	0.90	0.92	0.75	0.77	0.77	0.08	0.05
C + G >60	56	0.97	0.89	0.90	0.90	0.76	0.77	0.76	0.07	0.08
Primates	237	0.96	0.94	0.93	0.94	0.81	0.82	0.82	0.07	0.05
Rodents	191	0.90	0.93	0.89	0.91	0.75	0.80	0.78	0.11	0.05
Non-mamm. Vert.	72	0.93	0.93	0.90	0.93	0.81	0.85	0.84	0.11	0.06

A separate test was conducted on GENSCAN's accuracy using two GeneParser data sets that are stripped of all genes that are more than 25% of a match regarding amino acids with those in previous GeneParser test sets. The resulting data of this test and of the same test performed on other programs is shown in the table below. We can see that there is little variation between the accuracy of GENSCAN under the aforementioned Burset/Guigó data set and the GeneParser data sets. However, certain data points with higher fluctuation (e.g. 98% CC on high C + G nucleotides in GeneParser set II vs. 90% CC on C + G >60 nucleotides in Burset/Guigó) may be attributed to the GeneParser data sets being much smaller in sample size. The tests on the aforementioned three data sets provided enough information to form respective conclusions. However, these datasets are not of realistic size, therefore, their reliability and scope are justifiably brought into question.

GENSCAN vs. Other Programs Prediction Accuracy Under Data Sets I and II!Program!GeneID I!GeneID II!GRAIL3 I!GRAIL3 II!GeneParser2 I!GeneParser2 II!GENSCAN I!GENSCAN II
All sequences
Correlation	0.69	0.55	0.83	0.75	0.78	0.80	0.93	0.93
Sensitivity	0.69	0.50	0.83	0.68	0.87	0.82	0.98	0.95
Specificity	0.77	0.75	0.87	0.91	0.76	0.86	0.90	0.94
Exons Correct	0.42	0.33	0.52	0.31	0.47	0.46	0.79	0.76
Exons Overlapped	0.73	0.64	0.81	0.58	0.87	0.76	0.96	0.91
High C + G
Correlation	0.65	0.73	0.88	0.80	0.89	0.71	0.94	0.98
Sensitivity	0.72	0.85	0.87	0.80	0.90	0.65	1.00	0.98
Specificity	0.73	0.73	0.95	0.88	0.93	0.87	0.91	0.98
Exons Correct	0.38	0.43	0.67	0.50	0.64	0.57	0.76	0.64
Exons Overlapped	0.80	0.86	0.89	0.79	0.96	0.79	1.00	0.93
Medium C + G
Correlation	0.67	0.52	0.83	0.75	0.75	0.82	0.93	0.94
Sensitivity	0.65	0.47	0.86	0.68	0.86	0.84	0.97	0.95
Specificity	0.77	0.76	0.84	0.91	0.70	0.87	0.90	0.95
Exons Correct	0.37	0.29	0.51	0.32	0.41	0.46	0.79	0.79
Exons Overlapped	0.67	0.62	0.83	0.28	0.84	0.79	0.96	0.93
Low C + G
Correlation	0.81	0.62	0.62	0.62	0.72	0.67	0.92	0.81
Sensitivity	0.82	0.56	0.51	0.45	0.79	0.71	0.93	0.80
Specificity	0.85	0.71	0.87	0.89	0.75	0.67	0.94	0.84
Exons Correct	0.80	0.47	0.25	0.16	0.40	0.37	0.85	0.68
Exons Overlapped	0.85	0.63	0.55	0.42	0.85	0.58	0.85	0.74

In 1997, GENSCAN was found to have a higher accuracy than previous gene prediction programs. However, work still needed to be done due to how GENSCAN was shown to only predict 10-15% of genes accurately on realistic data sets. Because of inaccuracies like this, any predictions given by GENSCAN and other programs must be verified by comparing them to a Complementary DNA sequence, a Expressed sequence tag (EST) sequence, or a known protein sequence.^[6]

Notes and References

http://genes.mit.edu/GENSCAN.html The GENSCAN Web Server at MIT
Burge, C. B. (1998) Modeling dependencies in pre-mRNA splicing signals. In Salzberg, S., Searls, D. and Kasif, S., eds. Computational Methods in Molecular Biology, Elsevier Science, Amsterdam, pp. 127-163.
Burge . Christopher . Christopher Burge . Karlin . Samuel . Samuel Karlin . Prediction of complete gene structures in human genomic DNA . 10.1006/jmbi.1997.0951 . Journal of Molecular Biology . 268 . 1 . 78–94 . 1997 . 9149143 . dead . https://web.archive.org/web/20150620094015/https://ai.stanford.edu/~serafim/cs262/Papers/GENSCAN.pdf . 2015-06-20. 10.1.1.115.3107 .
10.1016/S0959-440X(98)80069-9 . Burge . C. . Christopher Burge . Karlin . S. . Samuel Karlin . Finding the genes in genomic DNA . Current Opinion in Structural Biology . 8 . 3 . 346–354 . 1998 . 9666331. free .
Flicek . Paul . 2007 . Gene prediction: compare and CONTRAST . Genome Biology . 8 . 12 . 233 . 10.1186/gb-2007-8-12-233 . 1474-760X . 2246255 . 18096089 . free .
Rogic . S. . Ouellette . B.F. F. . Mackworth . A. K. . 2002-08-01 . Improving gene recognition accuracy by combining predictions from two gene-finding programs . Bioinformatics . 18 . 8 . 1034–1045 . 10.1093/bioinformatics/18.8.1034 . 12176826 . 1367-4803. free .