GLIMMER: Difference between revisions

GLIMMER
Developer(s)	Steven Salzberg & Arthur Delcher
Stable release	3.02 / 9 May 2006
Available in	C++
Type	Bioinformatics tool
License	OSI Certified Open Source Software under the Artistic License
Website	ccb.jhu.edu/software/glimmer/index.shtml

Browse history interactively

← Previous edit Next edit →

Content deleted Content added

VisualWikitext

Inline

Revision as of 17:27, 8 December 2013

Introduction

In bioinformatics, GLIMMER (Gene Locator and Interpolated Markov ModelER) is used to find genes in prokaryotic DNA.^[1] "It is effective at finding genes in bacteria, archea, viruses, typically finding 98-99% of all protein coding genes".^[1] GLIMMER was the first system that used the interpolated Markov model ^[2] to identify coding regions. The GLIMMER software is open source and is maintained by Steven Salzberg, Art Delcher, and their colleagues at the Center for Bioinformatics and Computational Biology^[3] at Johns Hopkins University.

Versions of GLIMMER

GLIMMER 1.0

First Version of GLIMMER "i.e., GLIMMER 1.0" was released in 1998 and it was published in the paper Microbial gene identification using interpolated Markov model.^[1] Markov models were used to identify microbial genes in GLIMMER 1.0. GLIMMER considers the local composition sequence dependencies which makes GLIMMER more flexible and more powerful when compared to fixed-order Markov model.

There was a comparison made between interpolated Markov model used by GLIMMER and fifth order Markov model in the paper Microbial gene identification using interpolated Markov models.^[1] "GLIMMER algortihm found 1680 genes out of 1717 annotated genes in Haemophilus influenzaeItalic text where fifth order Markov model found 1574 genes. GLIMMER found 209 additional genes which were not included in 1717 annotated genes where fifth order Markov model found 104 genes."'^[1]

GLIMMER 2.0

Second Version of GLIMMER i.e., GLIMMER 2.0 was released in 1999 and it was published in the paper Improved microbial identification with GLIMMER.^[4] This paper^[4] provides significant technical improvements such as using interpolated context model instead of interpolated markov model and resolving overlapping genes which improves the accuracy of GLIMMER.

Interpolated context models are used instead of interpolated Markov model which gives the flexibility to select any base. In interpolated markov model probability distribution of a base is determined from the immediate preceding bases. If the immediate preceding base is irrelevant amino acid translation, interpolated markov model still considers the preceding base to determine the probability of given base where as interpolated context model which was used in GLIMMER 2.0 can ignore irrelevant bases. False positive predictions were increased in GLIMMER 2.0 to reduce the number of false negative predictions. Overlapped genes are also resolved in GLIMMER 2.0.

Various comparisons between GLIMMER 1.0 and GLIMMER 2.0 were made in the paper Improved microbial identification with GLIMMER^[4] which shows improvement in the later version. "Sensitivity of GLIMMER 1.0 ranges from 98.4 to 99.7% with an average of 99.1% where as GLIMMER 2.0 has a sensitivity range from 98.6 to 99.8% with an average of 99.3%. GLIMMER 2.0 is very effective in finding genes of high density. The parasite Trypanosoma brucei, responsible for causing african sleeping sickness is being identified by GLIMMER 2.0" ^[4]

GLIMMER 3.0

Third version of GLIMMER, "GLIMMER 3.0" was released in 2007 and it was published in the paper Identifying bacterial genes and endosymbiont DNA with Glimmer.^[5] This paper describes several major changes made to the GLIMMER system including improved methods to idenitfy coding regions and start codon. Scoring of ORF in GLIMMER 3.0 is done in reverse order i.e., starting from stop codon and moves back towards the start codon. Reverse scanning helps in identifying the coding portion of the gene more accurately which is contained in the context window of IMM. GLIMMER 3.0 also improves the generated training set data by comparing the long-ORF with universal amino acid distribution of widely disparate bacterial genomes."GLIMMER 3.0 has an average long-ORF output of 57% for various organisms where as GLIMMER 2.0 has an average long-ORF output of 39%."^[5]

GLIMMER 3.0 reduces the rate of false positive predictions which were increased in GLIMMER 2.0 to reduce the number of false negative predictions. "GLIMMER 3.0 has a start-site prediction accuracy of 99.5% for 3'5' matches where as GLIMMER 2.0 has 99.1% for 3'5' matches. GLIMMER 3.0 uses a new algorithm for scanning coding regions, a new start site detetction module, and architecture which integrates all gene predictions across an entire genome."^[5]

Accessing GLIMMER

GLIMMER can be accessed in two ways.

1. You can download the latest version of GLIMMER from The Glimmer home page and follow the installation instructions give in their home page. You need a C++ compiler to run GLIMMER.

2. You can also access the online version of GLIMMER hosted by NCBI at this address

How does GLIMMER works?

1. GLIMMER primarily searches for long-ORFS. An open reading frame might overlap with any other open reading frame which will be resolved using the technique described in the sub section. Using these long-ORFS and following certain amino acid distribution GLIMMER generates training set data.

2. Using these training data, GLIMMER trains all the six markov models of coding DNA from zero to eight order and also train the model for noncoding DNA

3. GLIMMER tries to calculate the probabilities from the data. Based on the number of observations, GLIMMER determines whether to use fixed order markov model or interpolated markov model.

   a. If the number of observations are greater than 400, GLIMMER uses fixed order markov model to obtain there probabilities.

   b. If the number of observations are less than 400, GLIMMER uses interpolated markov model which is briefly explained in the next sub section.

4. GLIMMER obtains score for every long-ORF generated using all the six coding DNA models and also using non-coding DNA model.

5. If the score obtained in the previous step is greater than a certain theshold then GLIMMER predicts it to be a gene.

The steps explained above descibres the basic functionality of GLIMMER. There are various improvements made to GLIMMER and some of them are described in the following sub-sections.

The GLIMMER system

GLIMMER system consists of two programs. First program called build-imm, which takes an input set of sequences and outputs the interpolated markov model as follows.

The probability for each base i.e., A,C,G,T for all k-mers for 0 ≤ k ≤ 8 is computed. Then, for each k-mer, GLIMMER computes weight. New sequence probability is computed as follows.

\operatorname {P(S/M)=\sum _{x=1}^{n}{IMM_{8}(S_{x})}}

where n is the length of the sequence $S_{x}$ is the oligomer at position x. $IMM_{8}(S_{x})$ , the $8^{th}$ -order interpolated markov model score is computed as

\operatorname {IMM_{k}(S_{x})=Y_{k}(S_{x-1})*P_{k}(S_{x})+[1-{Y_{k}(S_{(}x-1)]*IMM_{k-1}(S_{x})}}

"where $Y_{k}(S_{x-1})$ is the weight of the k-mer at position x-1 in the sequence S and $P_{k}(S_{x})$ is the estimate obtained from the training data of the probability of the base located at position x in the $k^{th}$ -order model."^[1]

The probability of base $S_{x}$ given the i previous bases is computed as follows.

\operatorname {P_{i}(S_{x})=P(s_{x}/S_{x,j})=f(S_{x,j})/\sum _{be{[acgt]}}\operatorname {f(S_{x,i},b)} }

"The value of $Y_{i}(S_{x})$ associated with $P_{i}(S_{x})$ can be regarded as a measure of confidence in the accuracy of this value as an estimate of the true probability. GLIMMER uses two criteria to determine $Y_{i}(S_{x})$ . The first of these is simple frequency occurence in which the number of occurences of context string $S_{x,i}$ in the training data exceeds a specific threshold value, then $Y_{i}(S_{x})$ is set to 1.0. The current default value for threshold is 400, which gives 95% confidence. When there are insufficient sample occurances of a context string, build-imm employ additional criteria to determine $Y$ value. For a given context string $S_{x,i}$ of length i, build-imm compare the observed frequenices of the following base $f(S_{x,i},a)$ , $f(S_{x,i},c)$ , $f(S_{x,i},g)$ , $f(S_{x,i},t)$ with the previously calculated interpolated markov model probabilties using the the next shorter context, $IMM_{i-1}(S_{x,{i-1}},a)$ , $IMM_{i-1}(S_{x,{i-1}},c)$ , $IMM_{i-1}(S_{x,{i-1}},g)$ , $IMM_{i-1}(S_{x,{i-1}},t)$ . Using a $X^{2}$ test, build-imm determine how likely it is that the four observed frequencies are consistent with the IMM values from the next shorter context."^[1]

The second program called glimmer, then uses this IMM to identify putative gene in an entire genome. GLIMMER identifies all the open reading frame which score higher than threshold and check for overlapping genes. Resolving overlapping genes is explained in the next sub-section.

Equations and explanation of the terms used above are taken from the paper 'Microbial gene identification using interpolated Markov models^[1]

Resolving overlapping genes

In GLIMMER 1.0, when two genes A and B overlap, the overlap region is scored. If A is longer than B, and if A scores higher on the overlap region, and if moving B's start site will not resolve the overlap, then B is rejected.

GLIMMER 2.0 provided a better solution to resolve the overlap. In GLIMMER 2.0, when two potential genes A and B overlap, the overlap region is scored. Suppose gene A scores higher, four different orientations are considered.

In the above case, moving of start sites does not remove the overlap. If A is significantly longer than B, then B is rejected or else both A and B are called genes, with a doubtful overlap.

In the above case, moving of B can resolve the overlap, A and B can be called non overlapped genes but if B is significantly shorter than A, then B is rejected.

In the above case, moving of A can resolve the overlap. A is only moved if overlap is a small fraction of A or else B is rejected.

In the above case, both A and B can be moved. We first move the start of B until the overlap region scores higher for B. Then we move the start of A until it scores higher. Then B again, and so on, until either the overlap is eliminated or no further moves can be made.

The above example has been taken from the paper 'Identifying bacterial genes and endosymbiont DNA with Glimmer'^[5]

Ribosome binding sites

Ribosome binding site(RBS) signal can be used to find true start site position. GLIMMER results are passed as an input for RBSfinder program to predict ribosome binding sites. GLIMMER 3.0 integrates RBSfinder program into gene predicting function itself.

ELPH software( which was determined as highly effective at identifying RBS in the paper^[5]) is used for identifying RBS and is available at this website. Gibbs sampling algorithm is used to identify shared motif in any set of sequences. This shared motif sequences and their length is given as input to ELPH. ELPH then computes the position weight matrix(PWM) which will be used by GLIMMER 3 to score any potential RBS found by RBSfinder. The above process is done when we have a substantial amount of training genes. If there are inadequate number of training genes, GLIMMER 3 can bootstrap itself to generate a set of gene predictions which can be used as input to ELPH. ELPH now computes PWM and this PWM can be again used on the same set of genes to get more accurate results for start-sites. This process can be repeated for many iterations to obtain more consistent PWM and gene predcition results.

Performance of GLIMMER

Glimmer is the system of choice for genome annotation efforts on a wide range of bacterial, archaeal, and viral species. In a large-scale reannotation effort at the DNA Data Bank of Japan (DDBJ, which mirrors Genbank). Kosuge et al. (2006)^[6] examined the gene finding methods used for 183 genomes. They reported that of these projects, Glimmer was the gene finder for 49%, followed by GeneMark with 12%, with other algorithms used in 3% or fewer of the projects. (They also reported that 33% of genomes used "other" programs, which in many cases meant that they could not identify the method. Excluding those cases, Glimmer was used for 73% of the genomes for which the methods could be unambiguously identified.) Glimmer was used by the DDBJ to re-annotate all bacterial genomes in the International Nucleotide Sequence Databases.^[7] It is also being used by this group to annotate viruses.^[8] Glimmer is part of the bacterial annotation pipeline at the National Center for Biotechnology Information (NCBI),^[9] which also maintains a web server for Glimmer,^[10] as do sites in Germany,^[11] Canada,.^[12]

Glimmer is a highly cited bioinformatics system in the scientific literature. According to Google Scholar, as of early 2011 the original Glimmer article (Salzberg et al., 1998)^[1] has been cited 581 times, and the Glimmer 2.0 article (Delcher et al., 1999)^[4] has been cited 950 times.

References

^ ^a ^b ^c ^d ^e ^f ^g ^h ⁱ Attention: This template ({{cite pmid}}) is deprecated. To cite the publication identified by PMID 9421513, please use {{cite journal}} with |pmid=9421513 instead.
^ Attention: This template ({{cite pmid}}) is deprecated. To cite the publication identified by PMID 10395796 , please use {{cite journal}} with |pmid=10395796 instead.
^ "Center for Computational Biology". Johns Hopkins University. Retrieved 23 March 2013.
^ ^a ^b ^c ^d ^e Attention: This template ({{cite pmid}}) is deprecated. To cite the publication identified by PMID 10556321, please use {{cite journal}} with |pmid=10556321 instead.
^ ^a ^b ^c ^d ^e Attention: This template ({{cite pmid}}) is deprecated. To cite the publication identified by PMID 17237039, please use {{cite journal}} with |pmid=17237039 instead.
^ Attention: This template ({{cite pmid}}) is deprecated. To cite the publication identified by PMID 17166861, please use {{cite journal}} with |pmid=17166861 instead.
^ Attention: This template ({{cite pmid}}) is deprecated. To cite the publication identified by PMID 17108353, please use {{cite journal}} with |pmid=17108353 instead.
^ Attention: This template ({{cite pmid}}) is deprecated. To cite the publication identified by PMID 17158166, please use {{cite journal}} with |pmid=17158166 instead.
^ "NCBI Prokaryotic Genomes Automatic Annotation Pipeline (PGAAP)". Center for Bioinformatics and Computational Biology. Retrieved 23 March 2012.
^ "Microbial Genome Annotation Tools". Center for Bioinformatics and Computational Biology. Retrieved 23 March 2012.
^ "TiCo". Institut für Mikrobiologie und Genetik, Universität Göttingen. Retrieved 23 March 2012.
^ "BASys Bacterial Annotation System". Retrieved 23 March 2012.

External links

The Glimmer home page at CCB, Johns Hopkins University, from which the software can be downloaded.

[Salzberg-1] ^ ^a ^b ^c ^d ^e ^f ^g ^h ⁱ Attention: This template ({{cite pmid}}) is deprecated. To cite the publication identified by PMID 9421513, please use {{cite journal}} with |pmid=9421513 instead.

[Pertea-2] Attention: This template ({{cite pmid}}) is deprecated. To cite the publication identified by PMID 10395796 , please use {{cite journal}} with |pmid=10395796 instead.

[3] "Center for Computational Biology". Johns Hopkins University. Retrieved 23 March 2013.

[Delcher-4] Attention: This template ({{cite pmid}}) is deprecated. To cite the publication identified by PMID 10556321, please use {{cite journal}} with |pmid=10556321 instead.

[Bratke-5] Attention: This template ({{cite pmid}}) is deprecated. To cite the publication identified by PMID 17237039, please use {{cite journal}} with |pmid=17237039 instead.

[Kosuge-6] Attention: This template ({{cite pmid}}) is deprecated. To cite the publication identified by PMID 17166861, please use {{cite journal}} with |pmid=17166861 instead.

[Sugawara-7] Attention: This template ({{cite pmid}}) is deprecated. To cite the publication identified by PMID 17108353, please use {{cite journal}} with |pmid=17108353 instead.

[Hirata-8] Attention: This template ({{cite pmid}}) is deprecated. To cite the publication identified by PMID 17158166, please use {{cite journal}} with |pmid=17158166 instead.

[9] "NCBI Prokaryotic Genomes Automatic Annotation Pipeline (PGAAP)". Center for Bioinformatics and Computational Biology. Retrieved 23 March 2012.

[10] "Microbial Genome Annotation Tools". Center for Bioinformatics and Computational Biology. Retrieved 23 March 2012.

[11] "TiCo". Institut für Mikrobiologie und Genetik, Universität Göttingen. Retrieved 23 March 2012.

[12] "BASys Bacterial Annotation System". Retrieved 23 March 2012.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

@@ Line 51: / Line 51: @@
     a. If the number of observations are greater than 400, GLIMMER uses fixed order [[markov model]] to obtain there probabilities.
-    b. If the number of observations are less than 400, GLIMMER uses [[interpolated]] [[markov model]] which is breifly explained in the next sub section.
+    b. If the number of observations are less than 400, GLIMMER uses [[interpolated]] [[markov model]] which is briefly explained in the next sub section.
 . GLIMMER obtains score for every long-ORF generated using all the six coding DNA models and also using non-coding DNA model.
@@ Line 57: / Line 57: @@
 . If the score obtained in the previous step is greater than a certain theshold then GLIMMER predicts it to be a gene.
-The steps explained above descibres the basic functionality of GLIMMER. There are various improvements made to GLIMMER and some of them are described in the follwing sub-sections.
+The steps explained above descibres the basic functionality of GLIMMER. There are various improvements made to GLIMMER and some of them are described in the following sub-sections.
 ===The GLIMMER system===
@@ Line 63: / Line 63: @@
 GLIMMER system consists of two programs. First program called build-imm, which takes an input set of sequences and outputs the [[interpolated]] [[markov model]] as follows.
-The probability for each base i.e, A,C,G,T for all [[k-mer]]s for 0 ≤ k ≤ 8 is computed. Then, for each [[k-mer]], GLIMMER computes weight. New sequence probability is computed as follows.
+The probability for each base i.e., A,C,G,T for all [[k-mer]]s for 0 ≤ k ≤ 8 is computed. Then, for each [[k-mer]], GLIMMER computes weight. New sequence probability is computed as follows.
 <center><math>\operatorname{P(S/M)=\sum_{x=1}^n{IMM_8(S_x)}}</math></center>
@@ Line 91: / Line 91: @@
 [[File:Case 1.png|thumb|center|Case 1]]
-In the above case, moving of start sites does not remove the overlap. If A is signifcantly longer than B, then B is rejected or else both A and B are called genes, with a doubtful overlap.
+In the above case, moving of start sites does not remove the overlap. If A is significantly longer than B, then B is rejected or else both A and B are called genes, with a doubtful overlap.
 [[File:Case2.png|thumb|center|Case 2]]