A metagenome originated from a shotgun sequencing of a microbial community is a
heterogeneous mixture of rather short sequences. A vast majority of microbial species in a
given community (99%) are likely to be non-cultivable. Many protein-coding regions in a
new metagenome are likely to code for barely detectable homologs of already known
proteins. Therefore, an ab initio method that would accurately identify the new genes is a
vitally important tool of metagenomic sequence analysis. The standard tools for ab initio …

We describe an algorithm for gene identification in DNA sequences derived from shotgun
sequencing of microbial communities. Accurate ab initio gene prediction in a short
nucleotide sequence of anonymous origin is hampered by uncertainty in model parameters.
While several machine learning approaches could be proposed to bypass this difficulty, one
effective method is to estimate parameters from dependencies, formed in evolution, between
frequencies of oligonucleotides in protein-coding regions and genome nucleotide …