BACKGROUND: BRAKER is a suite of automatic pipelines, BRAKER1 and BRAKER2, for the accurate annotation of protein-coding genes in eukaryotic genomes. Each pipeline trains statistical models of protein-coding genes based on provided evidence and, then predicts protein-coding genes in genomic sequences using both the extrinsic evidence and statistical models. For training and prediction, BRAKER1 and BRAKER2 incorporate complementary extrinsic evidence: BRAKER1 uses only RNA-seq data while BRAKER2 uses only a database of cross-species proteins. The BRAKER suite has so far not been able to reliably exceed the accuracy of BRAKER1 and BRAKER2 when incorporating both types of evidence simultaneously. Currently, for a novel genome project where both RNA-seq and protein data are available, the best option is to run both pipelines independently, and to pick one, likely better output. Therefore, one or another type of the extrinsic evidence would remain unexploited. RESULTS: We present TSEBRA, a software that selects gene predictions (transcripts) from the sets generated by BRAKER1 and BRAKER2. TSEBRA uses a set of rules to compare scores of overlapping transcripts based on their support by RNA-seq and homologous protein evidence. We show in computational experiments on genomes of 11 species that TSEBRA achieves higher accuracy than either BRAKER1 or BRAKER2 running alone and that TSEBRA compares favorably with the combiner tool EVidenceModeler. CONCLUSION: TSEBRA is an easy-to-use and fast software tool. It can be used in concert with the BRAKER pipeline to generate a gene prediction set supported by both RNA-seq and homologous protein evidence.

The genomes of mammalian species are pervasively transcribed producing as many noncoding as protein-coding RNAs. There is a growing body of evidence supporting their functional role. Long noncoding RNA (lncRNA) can bind both nucleic acids and proteins through several mechanisms. A reliable computational prediction of the most probable mechanism of lncRNA interaction can facilitate experimental validation of its function. In this study, we benchmarked computational tools capable to discriminate lncRNA from mRNA and predict lncRNA interactions with other nucleic acids. We assessed the performance of 9 tools for distinguishing protein-coding from noncoding RNAs, as well as 19 tools for prediction of RNA-RNA and RNA-DNA interactions. Our conclusions about the considered tools were based on their performances on the entire genome/transcriptome level, as it is the most common task nowadays. We found that FEELnc and CPAT distinguish between coding and noncoding mammalian transcripts in the most accurate manner. ASSA, RIBlast and LASTAL, as well as Triplexator, turned out to be the best predictors of RNA-RNA and RNA-DNA interactions, respectively. We showed that the normalization of the predicted interaction strength to the transcript length and GC content may improve the accuracy of inferring RNA interactions. Yet, all the current tools have difficulties to make accurate predictions of short-trans RNA-RNA interactions-stretches of sparse contacts. All over, there is still room for improvement in each category, especially for predictions of RNA interactions.

MOTIVATION: Gene finding in eukaryotic genomes is notoriously difficult to automate. The task is to design a work flow with a minimal set of tools that would reach state-of-the-art performance across a wide range of species. GeneMark-ET is a gene prediction tool that incorporates RNA-Seq data into unsupervised training and subsequently generates ab initio gene predictions. AUGUSTUS is a gene finder that usually requires supervised training and uses information from RNA-Seq reads in the prediction step. Complementary strengths of GeneMark-ET and AUGUSTUS provided motivation for designing a new combined tool for automatic gene prediction. RESULTS: We present BRAKER1, a pipeline for unsupervised RNA-Seq-based genome annotation that combines the advantages of GeneMark-ET and AUGUSTUS. As input, BRAKER1 requires a genome assembly file and a file in bam-format with spliced alignments of RNA-Seq reads to the genome. First, GeneMark-ET performs iterative training and generates initial gene structures. Second, AUGUSTUS uses predicted genes for training and then integrates RNA-Seq read information into final gene predictions. In our experiments, we observed that BRAKER1 was more accurate than MAKER2 when it is using RNA-Seq as sole source for training and prediction. BRAKER1 does not require pre-trained parameters or a separate expert-prepared training step. AVAILABILITY AND IMPLEMENTATION: BRAKER1 is available for download at http://bioinf.uni-greifswald.de/bioinf/braker/ and http://exon.gatech.edu/GeneMark/ CONTACT: [email protected] or [email protected] SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

SUMMARY: Frameshift (FS) prediction is important for analysis and biological interpretation of metagenomic sequences. Since a genomic context of a short metagenomic sequence is rarely known, there is not enough data available to estimate parameters of species-specific statistical models of protein-coding and non-coding regions. The challenge of ab initio FS detection is, therefore, two fold: (i) to find a way to infer necessary model parameters and (ii) to identify positions of frameshifts (if any). Here we describe a new tool, MetaGeneTack, which uses a heuristic method to estimate parameters of sequence models used in the FS detection algorithm. It is shown on multiple test sets that the MetaGeneTack FS detection performance is comparable or better than the one of earlier developed program FragGeneScan. AVAILABILITY AND IMPLEMENTATION: MetaGeneTack is available as a web server at http://exon.gatech.edu/GeneTack/cgi/metagenetack.cgi. Academic users can download a standalone version of the program from http://exon.gatech.edu/license_download.cgi.

Emerging knowledge of whole prokaryotic transcriptomes could validate a number of theoretical concepts introduced in the early days of genomics. What are the rules connecting gene expression levels with sequence determinants such as quantitative scores of promoters and terminators? Are translation efficiency measures, e.g. codon adaptation index and RBS score related to gene expression? We used the whole transcriptome shotgun sequencing of a bacterial pathogen Bacillus anthracis to assess correlation of gene expression level with promoter, terminator and RBS scores, codon adaptation index, as well as with a new measure of gene translational efficiency, average translation speed. We compared computational predictions of operon topologies with the transcript borders inferred from RNA-Seq reads. Transcriptome mapping may also improve existing gene annotation. Upon assessment of accuracy of current annotation of protein-coding genes in the B. anthracis genome we have shown that the transcriptome data indicate existence of more than a hundred genes missing in the annotation though predicted by an ab initio gene finder. Interestingly, we observed that many pseudogenes possess not only a sequence with detectable coding potential but also promoters that maintain transcriptional activity.

Next generation sequencing is quickly changing long standing paradigms of genomics in terms of what is feasible to accomplish within a ldquoresearch life timerdquo and what is supposed to remain beyond limits of reliable experimental analysis. Sequencing and mapping of a prokaryote transcriptome can provide experimental validation for computationally predicted genes annotated in a prokaryotic genome. In this study we use the transcriptome sequencing to assess the accuracy of the public annotation of genes in a genome of important pathogen Bacillus anthracis. We show that the transcriptome data confirm existence of a number of genes missing in the annotation. Also, the transcriptome data indicate that pseudogenes, genes with frameshifts and in frame stop codons, do keep the transcriptional activity (while possessing a coding potential as well) and continue to present a challenge for accurate annotation.

One of the main goals of computational genomics is fast and accurate biological interpretation of newly sequenced genomic DNA. The complexity of the task varies among genomes but is never simple. Currently, for a new genome a custom built annotation pipeline is constructed by integration of ab initio and comparative genomic methods. Still, a consistent solution of the jigsaw puzzle of genome annotation frequently requires additional experimental efforts (such as EST/cDNA sequencing, etc.) Current ab initio gene finding algorithms use statistical analysis and optimization to solve the gene identification problem restated as search for the optimal parse of the genomic sequence into fragments with distinct statistical characteristics. This problem setting leads to a classic task for dynamic programming: search for an optimal path through a network with weights/scores assigned to nodes and vertices. Obviously, assignment of weights/scores plays a critical role and may present a significant challenge. This task is equivalent to estimation of parameters of statistical models (hidden Markov models) representing a mosaic of functional sequences and sites in a given genome. The task is rather easy when large sets of validated training sequences are available. However, it is not the case for hundreds of currently unfolding genome sequencing and annotation projects. In the lecture we will consider the general schemes of ab initio gene prediction. We will discuss estimation of model parameters without a training set. We will show that this unsupervised approach is possible and is becoming very important for two rapidly developing branches of genomics: i/ for prokaryotic metagenomes that are becoming a rich source of information about non-cultivated microbial species and ii/ for "compact" eukaryotic genomes, such as fungi, which relatively short genome size (less than 50 MB) allows to obtain complete genome sequence in a relatively short time.

One of the major goals of computational sequence analysis is to find sequence similarities, which could serve as evidence of structural and functional conservation, as well as of evolutionary relations among the sequences. Since the degree of similarity is usually assessed by the sequence alignment score, it is necessary to know if a score is high enough to indicate a biologically interesting alignment. A powerful approach to defining score cutoffs is based on the evaluation of the statistical significance of alignments. The statistical significance of an alignment score is frequently assessed by its P-value, which is the probability that this score or a higher one can occur simply by chance, given the probabilistic models for the sequences. In this review we discuss the general role of P-value estimation in sequence analysis, and give a description of theoretical methods and computational approaches to the estimation of statistical signifiance for important classes of sequence analysis problems. In particular, we concentrate on the P-value estimation techniques for single sequence studies (both score-based and score-free), global and local pairwise sequence alignments, multiple alignments, sequence-to-profile alignments and alignments built with hidden Markov models. We anticipate that the review will be useful both to researchers professionally working in bioinformatics as well as to biomedical scientists interested in using contemporary methods of DNA and protein sequence analysis.

BACKGROUND: The accuracy of protein secondary structure prediction has been improving steadily towards the 88% estimated theoretical limit. There are two types of prediction algorithms: Single-sequence prediction algorithms imply that information about other (homologous) proteins is not available, while algorithms of the second type imply that information about homologous proteins is available, and use it intensively. The single-sequence algorithms could make an important contribution to studies of proteins with no detected homologs, however the accuracy of protein secondary structure prediction from a single-sequence is not as high as when the additional evolutionary information is present. RESULTS: In this paper, we further refine and extend the hidden semi-Markov model (HSMM) initially considered in the BSPSS algorithm. We introduce an improved residue dependency model by considering the patterns of statistically significant amino acid correlation at structural segment borders. We also derive models that specialize on different sections of the dependency structure and incorporate them into HSMM. In addition, we implement an iterative training method to refine estimates of HSMM parameters. The three-state-per-residue accuracy and other accuracy measures of the new method, IPSSP, are shown to be comparable or better than ones for BSPSS as well as for PSIPRED, tested under the single-sequence condition. CONCLUSIONS: We have shown that new dependency models and training methods bring further improvements to single-sequence protein secondary structure prediction. The results are obtained under cross-validation conditions using a dataset with no pair of sequences having significant sequence similarity. As new sequences are added to the database it is possible to augment the dependency structure and obtain even higher accuracy. Current and future advances should contribute to the improvement of function prediction for orphan proteins inscrutable to current similarity search methods.

This paper describes a framework we have developed for the visual analysis of large-scale phylogeny hierarchies populated with the genomic data of various organisms. This framework allows the user to quickly browse the phylogeny hierarchy of organisms from the highest level down to the level of an individual genome for the desired organism of interest. Based on this framework, the user can initiate gene-finding and gene-matching analyses and view the resulting annotated coding potential graphs in the same multi-scale visualization framework, permitting correlative analysis and further investigation. This paper introduces our framework and describes the data structures and algorithms that support it.

Mark Borodovsky, Andrey Rzhetsky, Dmitrij Frishman; The Fifth Georgia Tech—Oak Ridge National Laboratory International Conference in Bioinformatics: in sil

Secondary structure prediction has been an essential task in determining the structure and function of proteins. Prediction accuracy is improving every year towards the estimated 88% theoretical limit (Rost. B., http://cubic.bioc.columbia.edu/papers/2002 rev dekker/paper.html). There are two approaches for the secondary structure prediction. The first one, ab initio (single sequence) prediction, does not use any homology information. The evolutionary information, if available, is used by the second approach to improve the prediction accuracy by a few percentages (Schmidler, S.C. et al., J. Computational Biology, vol.7, no.1/2, p.233-48, 2000). We address the problem of single sequence prediction by developing a semi Markov HMM, similar to the one proposed by Schmidler et al. We introduce a better dependency model by considering the statistically significant amino acid correlation patterns at segment borders. Also, we propose an internal dependency model considering right to left dependencies without modifying the left to right HMM topology. In addition, we propose an iterative training method to estimate the HMM parameters better. Putting all these together, we obtained 1.5% improvement in three-state-per-residue accuracy.

In this paper, we review developments in probabilistic methods of gene recognition in prokaryotic genomes with the emphasis on connections to the general theory of hidden Markov models (HMM). We show that the Bayesian method implemented in GeneMark, a frequently used gene-finding tool, can be augmented and reintroduced as a rigorous forward-backward (FB) algorithm for local posterior decoding described in the HMM theory. Another earlier developed method, prokaryotic GeneMark.hmm, uses a modification of the Viterbi algorithm for HMM with duration to identify the most likely global path through hidden functional states given the DNA sequence. GeneMark and GeneMark.hmm programs are worth using in concert for analysing prokaryotic DNA sequences that arguably do not follow any exact mathematical model. The new extension of GeneMark using the FB algorithm was implemented in the software program GeneMark.fba. Given the DNA sequence, this program determines an a posteriori probability for each nucleotide to belong to coding or non-coding region. Also, for any open reading frame (ORF), it assigns a score defined as a probabilistic measure of all paths through hidden states that traverse the ORF as a coding region. The prediction accuracy of GeneMark.fba determined in our tests was compared favourably to the accuracy of the initial (standard) GeneMark program. Comparison to the prokaryotic GeneMark.hmm has also demonstrated a certain, yet species-specific, degree of improvement in raw gene detection, ie detection of correct reading frame (and stop codon). The accuracy of exact gene prediction, which is concerned about precise prediction of gene start (which in a prokaryotic genome unambiguously defines the reading frame and stop codon, thus, the whole protein product), still remains more accurate in GeneMarkS, which uses more elaborate HMM to specifically address this task.

MOTIVATION: Markov chain models of DNA sequences have frequently been used in gene finding algorithms. Performance of the algorithm critically depends on the model structure and parameters. Still, the issue of choosing the model structure has not been studied with sufficient attention. RESULTS: We have assessed performance of several types of Markov chain models, both fixed order (FO) models and models with interpolation, within the framework of the GeneMark algorithm. The performance was measured in two ways: (i) the accuracy of detection of protein-coding potential in artificial DNA sequences and (ii) the accuracy of identifying genes in real prokaryotic genomes. We observed that the models built by deleted interpolation (DI) slightly outperformed other models in detecting protein-coding potential in artificial DNA sequences with GC content in the medium range and also in detecting genes in real genomes with medium GC content. For artificial and real genomic DNA with high or low GC content, we observed that the models built by DI were in some cases slightly outperformed by FO models.

Mark Borodovsky, Eugene Koonin, Chris Burge, Jim Fickett, John Logsdon, Andrej Sali, Gary Stormo, Igor Zhulin; THE THIRD GEORGIA TECH–EMORY INTERNATIONAL C

This issue of Bioinformatics contains reports on selected papers presented at the international conference in Atlanta.The conference was held at one of the midtown hotels offering a magnificent bird's-eye view to the cosmopolitan capital of the Southeast of the USA.The conference agenda included keynote lectures by Russell Doolittle, Walter Fitch and Walter Gilbert, 19 plenary and contributed talks and more than 50 poster presentations.The focus of the conference was on the most intriguing issues of comparative and structural genomics, functional interpretation of nucleic acid and protein sequences, inferring 3D structure from sequence data and deciphering the history of biomolecular evolution (http://exon.biology.gatech.edu/conference).Submission of manuscripts to the Bioinformatics special issue has been a parallel avenue of presentation for the conference participants.Eighteen papers were submitted to the peer review process and nine were accepted for publication.The issue starts with the papers devoted to DNA sequence analysis and gene finding, followed by the papers on protein sequence analysis and protein structure prediction.Single pass sequencing of the 5 and 3 ends of cloned cDNA sequences represents an efficient approach to large scale characterization of the set of genes expressed by an organism.In the past few years huge numbers of such sequences, termed 'expressed sequence tags' or ESTs, have been determined from human and a variety of other organisms, and deposited in public databases.Such sequences represent a powerful resource for identifying genes, but suffer from the relatively high rates of sequencing errors typical of single pass data.Frameshift errors, in particular, can obscure the results of similarity searches based on translations of putative EST ORFs.The paper entitled 'FramePlus: Aligning DNA to protein sequences' by E. Halperin, S. Faigler and R. Gill-More describes a new algorithm specifically tailored to allow for moderate to high rates of frameshift errors.The new techniques resulted in improvements in the ability to detect homologies between ESTs and known proteins in peptide database searches.

MOTIVATION: Tightly packed prokaryotic genes frequently overlap with each other. This feature, rarely seen in eukaryotic DNA, makes detection of translation initiation sites and, therefore, exact predictions of prokaryotic genes notoriously difficult. Improving the accuracy of precise gene prediction in prokaryotic genomic DNA remains an important open problem. RESULTS: A software program implementing a new algorithm utilizing a uniform Hidden Markov Model for prokaryotic gene prediction was developed. The algorithm analyzes a given DNA sequence in each of six possible global reading frames independently. Twelve complete prokaryotic genomes were analyzed using the new tool. The accuracy of gene finding, predicting locations of protein-coding ORFs, as well as the accuracy of precise gene prediction, and detecting the whole gene including translation initiation codon were assessed by comparison with existing annotation. It was shown that in terms of gene finding, the program performs at least as well as the previously developed tools, such as GeneMark and GLIMMER. In terms of precise gene prediction the new program was shown to be more accurate, by several percentage points, than earlier developed tools, such as GeneMark.hmm, ECOPARSE and ORPHEUS. The results of testing the program indicated the possibility of systematic bias in start codon annotation in several early sequenced prokaryotic genomes. AVAILABILITY: The new gene-finding program can be accessed through the Web site: http:@dixie.biology.gatech.edu/GeneMark/fbf.cgi CONTACT: [email protected].

An exact expression for the variance of random frequency that a given word has in text generated by a Markov chain is presented. The result is applied to periodic Markov chains, which describe the protein-coding DNA sequences better than simple Markov chains. A new solution to the problem of word overlap is proposed. It was found that the expected frequency and overlapping properties determine most of the variance. The expectation and variance of counts for triplets are compared with experimental counts in Escherichia coli coding sequences.