MED: a new non-supervised gene prediction algorithm for bacterial and archaeal genomes

Abstract

Background: Despite a remarkable success in the computational prediction of genes in Bacteria and Archaea, a lack of comprehensive understanding of prokaryotic gene structures prevents from further elucidation of differences among genomes. It continues to be interesting to develop new ab initio algorithms which not only accurately predict genes, but also facilitate comparative studies of prokaryotic genomes.

Results: This paper describes a new prokaryotic genefinding algorithm based on a comprehensive statistical model of protein coding Open Reading Frames (ORFs) and Translation Initiation Sites (TISs). The former is based on a linguistic "Entropy Density Profile" (EDP) model of coding DNA sequence and the latter comprises several relevant features related to the translation initiation. They are combined to form a so-called Multivariate Entropy Distance (MED) algorithm, MED 2.0, that incorporates several strategies in the iterative program. The iterations enable us to develop a non-supervised learning process and to obtain a set of genome-specific parameters for the gene structure, before making the prediction of genes.

Conclusion: Results of extensive tests show that MED 2.0 achieves a competitive high performance in the gene prediction for both 5' and 3' end matches, compared to the current best prokaryotic gene finders. The advantage of the MED 2.0 is particularly evident for GC-rich genomes and archaeal genomes. Furthermore, the genome-specific parameters given by MED 2.0 match with the current understanding of prokaryotic genomes and may serve as tools for comparative genomic studies. In particular, MED 2.0 is shown to reveal divergent translation initiation mechanisms in archaeal genomes while making a more accurate prediction of TISs compared to the existing gene finders and the current GenBank annotation.

Figure 1

Flow chart of gene prediction process with MED 2.0 system.

Figure 2

Sequence logos of TIS-upstream-regions predicted by MED 2.0 for three archaeal genomes. We present the logos of three representative archaeal genomes: M. jannaschii, N. equitans and P. abyssi. The logos of start codon at position 0 to +2 are masked off.

Figure 3

Sequence logos of TIS-upstream-regions for MED prediction and GenBank annotation to S. solfataricus. (a) Venn diagram indicating the numbers of common and different gene starts given by MED 2.0 and GenBank; (b) Sequence logos of upstream region to TISs agreed by both MED 2.0 and GenBank; (c) Sequence logos of upstream region to TISs predicted only by MED 2.0; (d) Sequence logos of upstream region to TISs annotated only in GenBank. The logos of start codon at position 0 to +2 are masked off.

Figure 4

Sequence logos of TIS-upstream-regions for MED, Glimmer, GeneMarkS and ZCURVE prediction to S. solfataricus. The three Venn diagrams indicate the number of common and different gene starts by MED 2.0 versus Glimmer 3.02 (a), GeneMarkS (b) and ZCURVE 1.0 (c), separately. The left side sequence logos are for upstream regions to the TISs predicted by MED2.0 but rejected by Glimmer 3.02 (d), GeneMarkS (f) and ZCURVE 1.0 (h). The right side sequence logos of are for upstream regions to the TISs predicted by Glimmer 3.02 (e), GeneMarkS (g) and ZCURVE 1.0 (i) but rejected by MED2.0. The logos of start codon at position 0 to +2 are masked off.