Algorithm Description

MetaTISA is designed to post-process an existing gene annotation pipeline for metagenome, with an aim to improve its prediction accuracy of translation initiation sites (TISs). It takes inputs as a set of shotgun fragments and a set of CDS annotations, and outputs refined initiation sites.

The method constitutes two steps in TIS prediction. First, it uses binning techniques to classify all input fragments. Fragments binned in the same clade are assumed to have closely phylogenic origin, and hence share a similar mechanism in translation initiation. Then, the recently developed tool, TriTISA, is modified to predict TIS for each clade of fragments in an unsupervised iterative manner.

• Binning Method

Binning is to assign an anonymous sequence fragment to certain phylogenic group. A number of binning method currently published may include BLAST, K-mer (Sandberg, et al., 2001), SOM (Abe, et al., 2003), PhyloPythia (McHardy, et al., 2007), TETRA (Teeling, et al., 2004), etc. At this stage, we implemented the K-mer method, and plan to include other methods in the future.

The k-mer is a supervised method and employs a naive Bayesian classifier for sequence binning. The training data is the k-mer frequencies compiled for each phylogenic clade. Given a sequence fragment, the k-mer method calculates a likelihood score for each clade based on the pre-compiled frequencies, and assigns the fragment to the clade that produces the highest likelihood score (Sandberg, et al., 2001). We prepared the training sets from completely sequenced genomes, and chose one genome per genus to reduce redundancy (the genus list). Each genome presents a phylogenic clade, and the fragment is binned to genus level.

• TIS Prediction

We have recently proposed an unsupervised method for TIS prediction for microbial genomes (Hu et al., 2009). The method classifies all TIS candidates into three categories: true TISs, false TISs upstream of the true TISs (in noncoding region), and false TISs downstream of the TISs (in coding region). The features of sequences around TISs for each category are characterized by a non-homogenous Markov model. The three models are trained by an iterative self-learning procedure. At each step, the Markov models are combined by a Bayesian methodology, which assign three post-probabilities to each candidate TIS: the probability that the TIS is a true TIS (P_t), that it is from non-coding region (P_nc), and that it is from coding region (P_c). TriTISA predict the one with the highest P_t score as the TIS of a gene. The updated annotation constitute the training set for the next step of iteration. To further improve the prediction accuracies, TriTISA employs a cascade combination of different orders of Markov model, namely it first uses a 0^th-order Markov model for initial refinements, and then move to higher (1^st an 2^rd) order Markov models in the later steps of the iteration. Test on simulation data and experimentally verified data show that TriTISA produces a more accurate and robust prediction than the state-of-the-art  (Hu et al., 2009).

Here, we modified the TriTISA algorithm to post-process annotation for metagenomic binned fragments. CDSs from binned fragments are assumed to share similar machinery in translation initiation, and the sequence pattern for each set of TISs are homogenous across the clade. The assumptions allow the parameters to be trained as that trained for a single genome. CDSs are extended to the 5'-most before post-processing, and CDSs that are complete in their 5'-ends are used for parameter training. With the converged parameters, TriTISA calculates for each candidate TIS three scores: P_t, P_nc and P_c. For CDSs that are complete in their 5'-ends, the start codon is predicted as the candidate start that shows the highest P_t score. For CDSs that are incomplete in their 5'-ends, we need to estimate whether the start codon is missing. In other words, is the 5'-most start-codon-like triplet belong to coding region? We estimate the distribution of P_co from training set, and it is readily to have a threshold to say if a candidate is from coding regions (at a 95% confidence interval). For CDSs that are estimated to contain start codons, we predict the TIS following the procedure acting on training CDSs.

Figure 1 Program flow chart of MetaTISA

��

Performance Evaluation

Due to the lacking of experimentally verified TISs in metagenome project, the only way to reliably evaluate the prediction performance is to simulate a metagenome based on artificial shotgun sequences from complete microbial genomes. The validities of the k-mer method and the TriTISA method are documented previously (Sandberg et al., 2001; Hu et al. 2009. Here we tested their combined effect on TIS prediction for metagenomes with shotgun sequences simulated from 95 randomly selected genomes plus 5 genomes where experimentally verified TISs are available (Hu et al. 2009). Two sets of simulation were created with different settings of fragment length: L = 700 bps and L = 400 bps. We selected genes that have experimentally verified TISs from the five genomes as benchmarks. Since many of their start codons are absent from the fragments, we calculate sensitivity TP/TP+FN (sn) and specificity TN/TN+FP (sp) for accuracy measurements, where TP, TN, FP, and FN denote the numbers of true positives, true negatives, false positives, and false negatives, respectively. We demonstrate the performance of MetaTISA used to process the outputs of the newest version of MetaGene, namely MetaGeneAnnotator or MGA (Noguchi et al. 2008) (Table 1, 2). Similar improvements are obtained for Neural Net (Hoff et al., 2008) (data not shown).
��

Table 1. Accuracies calculated according to the RefSeq whole genome annotation

Table 2. Accuracies calculated according to experimentally verified TISs

��

>NC_000913_1
	  2     109   -
	  124     699   -
>NC_000913_2
	  3     305   +
	   539    700   +
>NC_000913_3
	  1     411   -
	   442    699   -
>NC_000913_4
	  2     685   -
>NC_000913_5
	  1     699   +

>mgutLn1_U_BL_aaa09a05_b1 Mouse Gut Community PT3 : mgutLn1_U_BL_aaa09a05_b1
AAATCTCGCCCTGTGGTGGATTCCTTTTCCCATTGCCCGATCTTATTTTT
ATCTTCCAAAAATGACGAACTGGACAAGATCCTGGGTCTTTCGGTGGGCG
GGGATGATTACGTGGCAAAGCCGTTCAGCCCGAAGGAGATCGCGTATCGG
GTCAAGGCGCAGCTCCGGCGGGCCGCGTATCAGCAAGACCCGTCGGAGGA
GGAGCTCATAAAAACAGGGGAATTGGAAATTGACGTGGAGGGCTGCAGGG
TCACAAAAGGCGGCAGCCCCATAGAACTGACCGCGCGGGAATTTGAAATC
CTGCGGTATCTGGCGGAAAATCAAGGCCGGGTCATCAGCCGCGAACGCTT
ATATGAAACCATCTGGGGCGAGGACAGCTTCGGGTGCGACAATACGGTCA
TGGTGCATATCCGGCATCTGCGTGAAAAAATAGAGGACGATCCCGCGGCG
CCCCGATACATCATCACGATGAAAGGATTAGGCTATAAGCTGGTGGACCC
TTATGAAGAATAAAAGCGATCTCAATCTGTTTTTTCGTTCGTTCGGCATT
GTCGTGATTGTGATCTTCGCGGCCATTGCAGCGGGGATATGCCTGTTTTA
TTATGTGTTCGCGATTCCGGCGCGGGAGGGACTCAGCCTGGCCTCATGGC
CAGACGTGTATACAGACAATTTTTCCCTTCAGCTTGAAGAAGAACAGGGA
GAGCTTAAAGTAAAAGAATTCGGGATTGAAGATCTGGACCGGTATGGCTT
ATGGCTGCAGGTGATCGATGAAACGGGACAGGAGTTTTTTCACACAATAA
GCCGGAGACCTGTCCCAACAGCTATACGGCCTCGAGCTTTTGGCATTCGG
GTACGAACGTTTA

<seqname> <source> <feature> <start> <end> <score> <strand> <frame> [attributes] [comments]

##gff-version  3
##MetaTISA
##metagenome sequence name: NC_000913_45
NC_000913_45   MetaTISA        CDS     3       395     .       -       .
##gff-version  3
##MetaTISA
##metagenome sequence name: NC_000913_255
NC_000913_255  MetaTISA        CDS     2       298     .       -       .
NC_000913_255  MetaTISA        CDS     320     616     .       -       .

Contact us

©2008 MetaTISA