BACKGROUND
in recent years, biological sequence databases have grown exponentially.
these data include a rapidly increasing number of completely sequenced genomes as well as large-scale metagenomic data sets that await annotation.
for instance, the global ocean sampling expedition  deposited more than 18g metagenomic sequences already  <cit> .
the analysis of these data calls for new and more efficient methods of data analysis  <cit> .
non-protein-coding rna  genes are abundant in genomic sequences, playing diverse important biological roles  <cit> .
the genomic annotation of ncrna genes is attracting strong research focus, in particular in the context of genome annotation  <cit>  and metagenomics  <cit> .
methods for homology-based annotation have dramatically improved over the last years.
in particular, infernal  <dig>   <cit>  outperforms previous methods by orders of magnitude in speed.
nevertheless, such general purpose approaches do not reach the performance levels of customized class-specific tools, in particular trnascan-se <cit>  in terms of both speed and quality.
manual strategies in some cases  <cit>  reach superior results, but are too time-consuming for larger projects and in most cases are hard to generalize.
trnascan-se is not a single algorithm but rather a wrapper tool that combines a series of increasingly complex and expensive filters.
similarly, the major searching strategy of rfam  <cit>  is a combination of a blast-based filter followed by infernal.
the pre-filtering at sequence level with blast, however, is not ideal in particular in applications to distant homologs  <cit> .
another common approach is to apply a descriptor of sequence and structural motif to predict ncrna homologs.
the descriptor construction is a manual process requiring expert knowledge.
several descriptor languages have been developed, e.g.
rnamot  <cit> , patscan <cit> , hypal <cit> , rnamotif <cit> , and rnabob <cit> , which is also used here.
rnase p rna, possibly a remnant of the rna world  <cit> , is an important ribozyme involved in the processing of pre-trnas  <cit> .
its gene is usually designated as rnpb in bacteria.
a variable number of protein components  <cit>  facilitate substrate binding  <cit> .
rnase p rna exists in almost all organisms, but is absent in human mitochondrions  <cit> .
so far, there is compelling evidence for the loss of rnase p rna only in a single organism, the archaeon nanoarchaeum equitans  <cit> .
it is not unlikely, however, that plants, red algae, and heterokonts  <cit> , some bacteria  and some additional archaea  have lost their rnase p rna.
the archaeon methanothermobacter thermoautotrophicus may be a transition towards the loss of rnase p rna, which is catalytically inactive in this organism but can be "repaired" by a few substitutions  <cit> .
the length of most rnase p rna lies between  <dig> nt and  <dig> nt.
it is divided into two structural domains: the s-domain repsonsible for binding and the catalytically active c-domain  <cit> , see figure  <dig>  the secondary structure of rnase p rna consists of up to  <dig> conserved stems, denoted p <dig> to p <dig>  of which p <dig> to p <dig> form the s-domain, which is flanked by the c-domain  <cit> .
there are five regions with strong sequence conservation, designated cr-i to cr-v, including the p <dig> pseudoknot composed by cr-i and cr-v  <cit> .
the rnase p rna structures can be broadly assigned to five subfamilies: the bacterial types a and b , the archaeal types a and m , and a single eukaryote group   <cit> .
in addition, two eukaryotic subtypes in fungi  can be identified  <cit> .
the types arca and baca, which have been identified as ancestral states  <cit> , cover the majority of microbial rnpb genes, forming diverse sets in terms of both sequence and structure variation.
the derived types arcm and bacb, in contrast, have more uniform members.
the diversity is largest among eukaryotic rnase p rna genes.
in eukaryotes, rnase p rna is transcribed by polymerase iii  <cit> .
the human promoter elements were described recently  <cit>  to contain tata-box, pse, oct and sp1/sph elements within  <dig> nt upstream of the transcription initiation site.
a comparison of all eukaryotic promoter elements showed weak similarities only in the tata box.
in this contribution we are concerned with the detection of rnase p rna genes in genomic data from all domains of life.
in  <cit> , a pattern matching based pipeline for efficient rnpb gene prediction has been proposed.
it is not applicable to large-scale database searches in practice, however.
here, we present bcheck, a wrapper, to perform efficient rnpb gene prediction by combining the fast filtering with rnabob <cit>  and the sensitive validation by infernal.
the construction of such a method entails two tasks: the design of an efficient yet sensitive descriptor model  that acts as a filter, and the derivation of a sensitive statistics covariance model .
both components are based on a careful analysis of published rnase p rna sequences and structures.
the success of bcheck depends on the efficiency and predictive power of both models, as well as a sensible wrapping algorithm that optimizes the interplay of dm and cm.
<dig>
RESULTS
<dig>  algorithm and models
the construction of effective models of rnase p rna genes is a non-trivial task because of the lack of strong family-specific conservation.
our strategy was to first classify the training sequences into the seven sub-families identified in the literature: arca, arcm, baca, bacb, nuca, fuga and fugb.
the training set consists of sequences from the rnase p rna database  <cit>  with intact secondary structures annotated, and additional rnase p rna sequences from the rfam and from two recent publications  <cit> .
a set of randomized decoys as well as randomized genomic sequences were constructed using ushuffle <cit>  in order to determine the false positive rates.
the training of both dm and cm requires structural alignments, whose quality is crucial for both the automatic learning procedures of the infernal cms and the manual construction of the dms.
we adopted a multi-step strategy: the rnase p rna sequences were first divided into structural elements, then base-pairing regions were structure-aligned manually, and loop regions were sequence-aligned by means of muscle <cit> .
local alignments were then recombined into a "raw" global alignment for each subfamily.
these alignments contained errors, mainly caused by local foldings which were not fitting to the conservation patterns shared by the majority of members.
we applied rnafold  <cit>  to check the thermodynamic plausibility of local structure elements.
construction of dms started with these alignments.
in the course of dm construction, outliers were temporarily removed from the alignments, searched with the preliminary dms, which provided additional information to guide the re-insertion of the outlier into the alignment.
since efficiency was the major focus of dm training, we focused on selected features of local regions.
to gain consensus sequence information, each alignment column was summarized and assigned with standard, "ambiguous" iupac nucleotides  or the gap character .
the sequence was edited to take established structural knowledge into account.
the resulting consensus sequence was then annotated in the alignment.
the ralee mode  <cit>  in the emacs editor was used for visually inspecting alignments, consensus structures and conservation patterns.
regions with rich conservation in sequence and/or structure were selected for inclusion in the descriptor.
a simple example of constructing dm from alignment is shown in figure  <dig>  the dm for rnase p rna genes mainly consists of the s-domain and its flanking conserved sequences.
once the feature selection was completed, we carried out a interactive process between dm building and dm testing to adjust the parameters of feature variables balancing between false positive rate and efficiency.
among several descriptor languages we chose rnabob as search engine for our dms because of its convenient syntax and its speed.
for the subfamilies arca, baca, and nuc with strong variation, we constructed two variants, "dm selective" and "dm general", with different parameter settings.
the selective dms miss a few aberrant rnase p rna genes, while the "dm general" models have a larger false positive rate.
for each subfamily, only one cm is needed and automatically generated based on global structural alignment using the tools of the infernal package.
the bcheck wrapping algorithm takes the strategy of local to global and selective to general, figure  <dig>  at first, subfamily-specific dms locate candidate genes.
if no valid hit was produced by the "selective" model, the corresponding "dm general" is applied.
then the cm is applied in local alignment mode to validate the candidate.
valid hits, i.e., those recognized by the cm, are extended by  <dig> nt and  <dig> nt at 5' and 3' ends, respectively, and fed to the cm in global alignment to produce better estimates of the ends.
at both phases, an e-value threshold of e ≤ 10- <dig> must be reached.
to distinguish functional copy and pseudogene of eukaryotes, we analyzed their promoter regions.
for this purpose we aligned  <dig> nt upstream of polymerase iii transcripts of the same organism and compared the rnase p rna gene predictions.
while the absence of a recognizable promoter signal does not prove that the rnase p rna gene is not functional, we have adopted a conservative policy and include only bcheck results for which the presence of a promoter signal provides additional confirmation.
<dig>  applications
<dig> .
<dig> prokaryote rnpb genes in genbank
we used bcheck to scan the genomic sequences of  <dig> bacteria and  <dig> archaea organisms from genbank.
the entire computation, which surveyed  <dig> g of input sequence, took approximately  <dig> hours to complete with a single core of  <dig>  ghz intel core <dig> cpu.
bcheck produced one hit per organism for 98%  of organisms, see table  <dig>  the default algorithm yielded no prediction in  <dig> organisms, for  <dig> of which a direct cm search was successful.
these  <dig> rnase p rna genes are distributed over all  <dig> prokaryotic sub-families.
the main reason of failure is because of unusual local variations, e.g.
bulges or point mutations, which cannot be captured by the present dms.
bcheck predictions for three members of the phylum chloroflex  are only partial rnpb regions including partial-p <dig>  p <dig> and junctions between two stems.
after removing duplicate sequences from closely related strains, we obtained  <dig> unique rnpb genes of which  <dig> belong to arca,  <dig> to arcm,  <dig> to baca, and  <dig> to bacb, see table  <dig> below.
"known" refers to organisms with annotated rnpb genes, whereas "unknown" refers to organisms with no annotated rnpb genes.
the genbank files contained annotated rnpb genes for  <dig> bacteria and  <dig> archaea, all of which were among the bcheck predictions.
we then compared start-end positions of bcheck predictions and genbank annotations.
only 25% of the annotations agree within a discrepancy of  <dig> nt or less at both ends.
inspection of sequences and predicted secondary structures shows that the published sequences are in general incomplete, lacking nucleotides at the 5' end of p <dig> and 3' end of p4: at the 5' end, 66% known annotations miss flanking regions of p <dig>  ranging from  <dig> to  <dig> nucleotides.
at the 3' end, 56% known annotations miss flanking regions of p4', ranging from  <dig> to  <dig> nucleotides.
a few of the genbank annotations, furthermore, have promoter or terminator sequences included.
bcheck thus provides a substantial improvement also of the existing annotations in most cases.
the published annotation is more accurate than the bcheck prediction only in a single case: roseiflexus rs  <dig>  in five cases, the published annotations and the bcheck results differ dramatically.
in order to evaluate these cases further, we employed the cm model of the rfam, which supported the authenticity of the bcheck predictions, table  <dig>
rfam scores are bit-scores for infernal using rfam's cm models.
the discrepancies column lists features missing in the region annotated in genbank.
<dig> .
<dig> rnase p rna genes in metagenomic sequences
the gos metagenomic sequences were obtained from the camera project  <cit> .
due to the taxonomic uncertainty of the gos data set, all models of archaea, bacteria and eukaryotes were applied to search over  <dig> million sequences comprising about  <dig> g. no hit was produced by any of the eukaryotic models.
in total, bcheck predicted  <dig> rnpb genes with median e-values of 10- <dig>  in  <dig> cases two models overlap.
in these cases there is a clear difference in e-values, so that the assignment to domains is unambiguous in all positive cases.
after duplication removal,  <dig> rnpb sequences are unique,  <dig> of which belong to baca,  <dig> to arca,  <dig> to bacb, but none for arcm, see table  <dig>
the ancestral types arca and baca are clearly predominant in both genbank and gos data set.
in the marine samples, the number of baca rnpb genes exceeds 95%.
we compared rnpb sequences from two datasets with respect to their gc content, figure  <dig>  differences are particularly obvious in bacteria, where the majority of gos baca sequences have low gc-content, while the median gc content of genbank rnpb is high, with ≈  <dig> .
the gc content of rnasep rna genes seems to be influenced by the environment, which agrees to the findings of foerstner et al.
<cit> , showing the gc content of complex microbial communities seems to be globally and actively influenced by the environment.
obtaining a view of the taxonomic distribution within a microbial community is one central objective of metagenomic analysis.
we used the detected rnpb genes as a marker to infer the taxonomic distribution of gos samples.
we used blast to find the closest orthologs of  <dig> unique gos rnpb genes among the  <dig> genbank sequences using an e-value threshold of e < 10- <dig>  high scoring orthologs are found for  <dig> gos rnpb genes.
<dig> of which have only one ortholog per gene making species assignments possible, while  <dig> have multiple orthologs, all coming from the same genus, making genus assignments possbile.
these species assignments and genus assignments are shown in figure  <dig>  the identified organisms are mostly bacteria belonging to the three phyla proteobacteria, cyanobacteria and bacteroidetes.
only a single archaeon, nitrosopumilus maritimus, is recognized.
among bacteria, most sequences belong to pelagibacter ubique  and prochlorococcus marinus .
for  <dig> gos rnpbs , no close homologs are known, suggesting that they derive from unknown species.
of these,  <dig>  belong to the baca subfamily,  <dig>  to the arca subfamily, and  <dig>  to the bacb subfamily.
<dig> .
<dig> rnase p rna genes in eukaryotic genomes
we investigated  <dig> eukaryotic genomes, table  <dig>  of the previously annotated genes, we recovered  <dig> of  <dig> metazoan and  <dig> of  <dig> fungal rnase p rna genes.
we miss the otolemur garnetti sequence because of a  <dig> nt insertion within the highly conserved p <dig>  which is used as a block in most descriptors.
for the two related fungi coprinus cinereus and laccaria bicolor hypothetical rnase p rna genes have been reported  <cit> .
however, the e-values assigned by the bcheck cm is mediocre, and the insertions of several 'u's within the 'gaa' motif of the p <dig> 5' region as well as point mutations cause failure of the bcheck dm.
on the other hand, compared to  <cit> bcheck made novel predictions for  <dig> fungi and  <dig> metazoans , as well as the choanoflagellate monosiga brevicollis.
* no common promoter signals observed:  <dig> out of  <dig>
strong promoter signals were identified for meloidogyne hapla and monosiga brevicollis, supporting that these candidates are functional copies.
for  <dig> metazoan genomes, bcheck made multiple predictions.
in at least  <dig> cases, additional predictions are highly similar to the functional copy.
in genome sequence assembly, the reads originating from different copies of a repeat appear identical and cause assembly errors.
therefore these predictions seem to be due to assembly errors rather than constituting true paralogs.
in the other  <dig> cases differences in the flanking regions and the rnase p rna gene itself indicate that we see the results of gene duplications.
even though the promoter might be specific for an organism, it may differ from other polymerase iii transcripts within one species.
in each of these cases, a presumably functional rnase p rna like promoter structure was found for only one of the copies.
similar duplication patterns are observed in closely related primate, fish and rodent.
for instance, both homo sapiens and pan troglodytes have functional copies on chromosome  <dig> and a pseudogene on chromosome  <dig>  among teleosts, both danio rerio and gasterosteus aculeatus have their functional copies and pseudogenes on the chromosome  <dig>  in rodent family, rattus norvegicus and mus musculus have the pseudogenes spreading on at least  <dig> different chromosomes.
novel rnase p rna genes were detected by bcheck in many fungi, which had not been analyzed in much detail so far.
only eight sequences which were reported before were not recognized by bcheck.
in  <dig> sequences bcheck found  <dig> novel rnase p rna genes.
the remaining  <dig> genomes are either unfinished drafts, so that the rnase p rna is not contained in the data, or they belong to clades where rnase p rna may be absent.
in plants, red algae, and heterokonts rnase mrp rna, an ancient paralog of rnase p rna, is well described  <cit> .
one may speculate that it substitutes for rnase p rna in these clades, in particular given that multiple copies of rnase mrp rna are present in plant genomes.
a recent, detailed overview of the evolution of rnase p rna and its associated proteins can be found in  <cit> .
an incomplete genome assembly explains e.g.
the deviant rnase p rna in the genome of the elephant , which shows a canonical sequence interrupted by a run of ns in the latest assembly .
on the other hand, we suspect that we missed the rnase p rna in some fungi and in some of the basal eukaryotes because of highly divergent sequence and secondary structure.
<dig>  software, webserver, and database
bcheck was written in python .
input consists of dna or rna sequences in fasta format, predictions are output with fasta format or with secondary structure annotated.
besides the default search algorithm, bcheck also gives the option for searching with cm only.
however, cm-only search is at least  <dig> times slower.
we set up a bcheck webserver to facilitate online rnase p rna gene prediction.
a searchable rnpb database was developed, including genes for  <dig> microbial organisms,  <dig> eukaryote organisms and  <dig> gos sample sequences.
the predicted pseudogenes for eukaryote organisms are also included.
the "rnpb database" uses a hierarchical tree structure, consisting of  <dig> tables, implementing preorder tree traversal algorithm to process the query efficiently.
blast is also offered in the server for homology search against the database compromising  <dig> unique rnpb genes.
the server can be accessed at http://rna.tbi.univie.ac.at/bcheck.
the bcheck-pipeline can also be downloaded from the same location for local use in a linux environment.
<dig> discussion and
CONCLUSIONS
the rapidly increasing size of sequence databases requires efficient tools for data analysis.
in particular, homology annotation of small ncrnas, with their short and often poorly conserved sequences poses a severe problem for large-scale annotation.
here, we describe bcheck, an efficient pipeline to determine rnase p rna genes across all three domains of life.
in order to deal with the high variability of the rnase p rna sequences and structures, we employ descriptor-based models specific for sub-families instead of a single pattern to construct more efficient filters.
in the second step, improved covariance models are used to validate the candidates from the dm step and to determine nearly exact gene boundaries.
with bcheck, we were able to determine the rnase p rna genes in  <dig> out of  <dig> archaea,  <dig> out of  <dig> bacteria, and  <dig> out of  <dig> eukaryotes.
61% of the prokaryotic sequences and 25% of eukaryotic results were not annotated previously.
the quality of the predicted rnpb genes is much better than a large fraction of the - usually blast-based - annotation available through genbank.
the size and diversity of eukaryote genomes brings with it a particular challenge in finding rnase p rna genes, because this diversity is reflected in many aberrant features of the rnase p rna itself.
using the fungi-specific dms, we uncovered  <dig> previously unannotated sequences, which are downloadable from the bcheck server.
as in previous studies, we did not find rnase p rna candidates in plants and heterokonta.
since bcheck is more than  <dig> times faster than the direct application of infernal , it is suitable in particular as a tool to screen large high-throughput sequencing data.
with only a handful of false negatives , bcheck provides a highly efficient way to annotate newly sequenced genomes.
a particular strength of bcheck is its applicability to metagenomics data.
among the  <dig> prokaryotic genomes for which bcheck failed to detect a candidate,  <dig> have a size below  <dig>  mbp.
one of them, nanoarchaeum equitans, is among three organisms having extremely condensed genomes with length even below  <dig>  mbp.
nanoarchaeum equitans appears to have lost its rnase p rna through genomic rearrangement at trna genes under the pressure of genome condensation  <cit> .
in figure  <dig> we summarize the correlations between genome size and the size of prokaryotic rnase p rna.
even though there is no strong correlation indicated in arca and baca subfamilies, the evolutionarily younger bacb and arcm seem to be more strongly affected by changes in genome size.
at present, bcheck models were built on the conserved sequence and secondary structure features of a large sample of rnase p rna genes.
conceivably, the predictive power of the pipeline could be improved further by including additional information.
for instance, promoter and terminator regions might be utilized.
a recent survey for 7sk rnas capitalized largely on the conserved features of the characteristic pol-iii promoter signals of this ncrna class  <cit> .
a similar strategy might allow a further relaxation of the dm pattern in favor of a second filter utilizing the promoter and terminator motifs.
authors' contributions
ilh designed the study.
dy constructed descriptors, designed and implemented the pipeline.
mm prepared the training sets for eukaryote models and performed eukaryote hit validation with promoter analysis.
all authors collaborated on analyzing the data and writing the manuscript.
all authors have read and approved the final manuscript.

 in recent years, biological sequence databases have grown exponentially. these data include a rapidly increasing number of completely sequenced genomes as well as large-scale metagenomic data sets that await annotation. for instance, the global ocean sampling expedition deposited more than 18g metagenomic sequences already. the analysis of these data calls for new and more efficient methods of data analysis. non-protein-coding rna genes are abundant in genomic sequences, playing diverse important biological roles. the genomic annotation of ncrna genes is attracting strong research focus, in particular in the context of genome annotation and metagenomics. methods for homology-based annotation have dramatically improved over the last years. in particular, infernal outperforms previous methods by orders of magnitude in speed. nevertheless, such general purpose approaches do not reach the performance levels of customized class-specific tools, in particular trnascan-se in terms of both speed and quality. manual strategies in some cases reach superior results, but are too time-consuming for larger projects and in most cases are hard to generalize. trnascan-se is not a single algorithm but rather a wrapper tool that combines a series of increasingly complex and expensive filters. similarly, the major searching strategy of rfam is a combination of a blast-based filter followed by infernal. the pre-filtering at sequence level with blast, however, is not ideal in particular in applications to distant homologs. another common approach is to apply a descriptor of sequence and structural motif to predict ncrna homologs. the descriptor construction is a manual process requiring expert knowledge. several descriptor languages have been developed, e.g. rnamot, patscan, hypal, rnamotif, and rnabob, which is also used here. rnase p rna, possibly a remnant of the rna world, is an important ribozyme involved in the processing of pre-trnas. its gene is usually designated as rnpb in bacteria. a variable number of protein components facilitate substrate binding. rnase p rna exists in almost all organisms, but is absent in human mitochondrions. so far, there is compelling evidence for the loss of rnase p rna only in a single organism, the archaeon nanoarchaeum equitans. it is not unlikely, however, that plants, red algae, and heterokonts, some bacteria and some additional archaea have lost their rnase p rna. the archaeon methanothermobacter thermoautotrophicus may be a transition towards the loss of rnase p rna, which is catalytically inactive in this organism but can be "repaired" by a few substitutions. the length of most rnase p rna lies between nt and nt. it is divided into two structural domains: the s-domain repsonsible for binding and the catalytically active c-domain, see figure the secondary structure of rnase p rna consists of up to conserved stems, denoted p to p of which p to p form the s-domain, which is flanked by the c-domain. there are five regions with strong sequence conservation, designated cr-i to cr-v, including the p pseudoknot composed by cr-i and cr-v. the rnase p rna structures can be broadly assigned to five subfamilies: the bacterial types a and b, the archaeal types a and m, and a single eukaryote group. in addition, two eukaryotic subtypes in fungi can be identified. the types arca and baca, which have been identified as ancestral states, cover the majority of microbial rnpb genes, forming diverse sets in terms of both sequence and structure variation. the derived types arcm and bacb, in contrast, have more uniform members. the diversity is largest among eukaryotic rnase p rna genes. in eukaryotes, rnase p rna is transcribed by polymerase iii. the human promoter elements were described recently to contain tata-box, pse, oct and sp1/sph elements within nt upstream of the transcription initiation site. a comparison of all eukaryotic promoter elements showed weak similarities only in the tata box. in this contribution we are concerned with the detection of rnase p rna genes in genomic data from all domains of life. in, a pattern matching based pipeline for efficient rnpb gene prediction has been proposed. it is not applicable to large-scale database searches in practice, however. here, we present bcheck, a wrapper, to perform efficient rnpb gene prediction by combining the fast filtering with rnabob and the sensitive validation by infernal. the construction of such a method entails two tasks: the design of an efficient yet sensitive descriptor model that acts as a filter, and the derivation of a sensitive statistics covariance model. both components are based on a careful analysis of published rnase p rna sequences and structures. the success of bcheck depends on the efficiency and predictive power of both models, as well as a sensible wrapping algorithm that optimizes the interplay of dm and cm.  algorithm and models the construction of effective models of rnase p rna genes is a non-trivial task because of the lack of strong family-specific conservation. our strategy was to first classify the training sequences into the seven sub-families identified in the literature: arca, arcm, baca, bacb, nuca, fuga and fugb. the training set consists of sequences from the rnase p rna database with intact secondary structures annotated, and additional rnase p rna sequences from the rfam and from two recent publications. a set of randomized decoys as well as randomized genomic sequences were constructed using ushuffle in order to determine the false positive rates. the training of both dm and cm requires structural alignments, whose quality is crucial for both the automatic learning procedures of the infernal cms and the manual construction of the dms. we adopted a multi-step strategy: the rnase p rna sequences were first divided into structural elements, then base-pairing regions were structure-aligned manually, and loop regions were sequence-aligned by means of muscle. local alignments were then recombined into a "raw" global alignment for each subfamily. these alignments contained errors, mainly caused by local foldings which were not fitting to the conservation patterns shared by the majority of members. we applied rnafold to check the thermodynamic plausibility of local structure elements. construction of dms started with these alignments. in the course of dm construction, outliers were temporarily removed from the alignments, searched with the preliminary dms, which provided additional information to guide the re-insertion of the outlier into the alignment. since efficiency was the major focus of dm training, we focused on selected features of local regions. to gain consensus sequence information, each alignment column was summarized and assigned with standard, "ambiguous" iupac nucleotides or the gap character. the sequence was edited to take established structural knowledge into account. the resulting consensus sequence was then annotated in the alignment. the ralee mode in the emacs editor was used for visually inspecting alignments, consensus structures and conservation patterns. regions with rich conservation in sequence and/or structure were selected for inclusion in the descriptor. a simple example of constructing dm from alignment is shown in figure the dm for rnase p rna genes mainly consists of the s-domain and its flanking conserved sequences. once the feature selection was completed, we carried out a interactive process between dm building and dm testing to adjust the parameters of feature variables balancing between false positive rate and efficiency. among several descriptor languages we chose rnabob as search engine for our dms because of its convenient syntax and its speed. for the subfamilies arca, baca, and nuc with strong variation, we constructed two variants, "dm selective" and "dm general", with different parameter settings. the selective dms miss a few aberrant rnase p rna genes, while the "dm general" models have a larger false positive rate. for each subfamily, only one cm is needed and automatically generated based on global structural alignment using the tools of the infernal package. the bcheck wrapping algorithm takes the strategy of local to global and selective to general, figure at first, subfamily-specific dms locate candidate genes. if no valid hit was produced by the "selective" model, the corresponding "dm general" is applied. then the cm is applied in local alignment mode to validate the candidate. valid hits, i.e., those recognized by the cm, are extended by nt and nt at 5' and 3' ends, respectively, and fed to the cm in global alignment to produce better estimates of the ends. at both phases, an e-value threshold of e ≤ 10- must be reached. to distinguish functional copy and pseudogene of eukaryotes, we analyzed their promoter regions. for this purpose we aligned nt upstream of polymerase iii transcripts of the same organism and compared the rnase p rna gene predictions. while the absence of a recognizable promoter signal does not prove that the rnase p rna gene is not functional, we have adopted a conservative policy and include only bcheck results for which the presence of a promoter signal provides additional confirmation. applications. prokaryote rnpb genes in genbank we used bcheck to scan the genomic sequences of bacteria and archaea organisms from genbank. the entire computation, which surveyed g of input sequence, took approximately hours to complete with a single core of ghz intel core cpu. bcheck produced one hit per organism for 98% of organisms, see table the default algorithm yielded no prediction in organisms, for of which a direct cm search was successful. these rnase p rna genes are distributed over all prokaryotic sub-families. the main reason of failure is because of unusual local variations, e.g. bulges or point mutations, which cannot be captured by the present dms. bcheck predictions for three members of the phylum chloroflex are only partial rnpb regions including partial-p p and junctions between two stems. after removing duplicate sequences from closely related strains, we obtained unique rnpb genes of which belong to arca, to arcm, to baca, and to bacb, see table below. "known" refers to organisms with annotated rnpb genes, whereas "unknown" refers to organisms with no annotated rnpb genes. the genbank files contained annotated rnpb genes for bacteria and archaea, all of which were among the bcheck predictions. we then compared start-end positions of bcheck predictions and genbank annotations. only 25% of the annotations agree within a discrepancy of nt or less at both ends. inspection of sequences and predicted secondary structures shows that the published sequences are in general incomplete, lacking nucleotides at the 5' end of p and 3' end of p4: at the 5' end, 66% known annotations miss flanking regions of p ranging from to nucleotides. at the 3' end, 56% known annotations miss flanking regions of p4', ranging from to nucleotides. a few of the genbank annotations, furthermore, have promoter or terminator sequences included. bcheck thus provides a substantial improvement also of the existing annotations in most cases. the published annotation is more accurate than the bcheck prediction only in a single case: roseiflexus rs in five cases, the published annotations and the bcheck results differ dramatically. in order to evaluate these cases further, we employed the cm model of the rfam, which supported the authenticity of the bcheck predictions, table rfam scores are bit-scores for infernal using rfam's cm models. the discrepancies column lists features missing in the region annotated in genbank.. rnase p rna genes in metagenomic sequences the gos metagenomic sequences were obtained from the camera project. due to the taxonomic uncertainty of the gos data set, all models of archaea, bacteria and eukaryotes were applied to search over million sequences comprising about g. no hit was produced by any of the eukaryotic models. in total, bcheck predicted rnpb genes with median e-values of 10- in cases two models overlap. in these cases there is a clear difference in e-values, so that the assignment to domains is unambiguous in all positive cases. after duplication removal, rnpb sequences are unique, of which belong to baca, to arca, to bacb, but none for arcm, see table the ancestral types arca and baca are clearly predominant in both genbank and gos data set. in the marine samples, the number of baca rnpb genes exceeds 95%. we compared rnpb sequences from two datasets with respect to their gc content, figure differences are particularly obvious in bacteria, where the majority of gos baca sequences have low gc-content, while the median gc content of genbank rnpb is high, with ≈. the gc content of rnasep rna genes seems to be influenced by the environment, which agrees to the findings of foerstner et al., showing the gc content of complex microbial communities seems to be globally and actively influenced by the environment. obtaining a view of the taxonomic distribution within a microbial community is one central objective of metagenomic analysis. we used the detected rnpb genes as a marker to infer the taxonomic distribution of gos samples. we used blast to find the closest orthologs of unique gos rnpb genes among the genbank sequences using an e-value threshold of e < 10- high scoring orthologs are found for gos rnpb genes. of which have only one ortholog per gene making species assignments possible, while have multiple orthologs, all coming from the same genus, making genus assignments possbile. these species assignments and genus assignments are shown in figure the identified organisms are mostly bacteria belonging to the three phyla proteobacteria, cyanobacteria and bacteroidetes. only a single archaeon, nitrosopumilus maritimus, is recognized. among bacteria, most sequences belong to pelagibacter ubique and prochlorococcus marinus. for gos rnpbs, no close homologs are known, suggesting that they derive from unknown species. of these, belong to the baca subfamily, to the arca subfamily, and to the bacb subfamily.. rnase p rna genes in eukaryotic genomes we investigated eukaryotic genomes, table of the previously annotated genes, we recovered of metazoan and of fungal rnase p rna genes. we miss the otolemur garnetti sequence because of a nt insertion within the highly conserved p which is used as a block in most descriptors. for the two related fungi coprinus cinereus and laccaria bicolor hypothetical rnase p rna genes have been reported. however, the e-values assigned by the bcheck cm is mediocre, and the insertions of several'u's within the'gaa' motif of the p 5' region as well as point mutations cause failure of the bcheck dm. on the other hand, compared to bcheck made novel predictions for fungi and metazoans, as well as the choanoflagellate monosiga brevicollis. * no common promoter signals observed: out of strong promoter signals were identified for meloidogyne hapla and monosiga brevicollis, supporting that these candidates are functional copies. for metazoan genomes, bcheck made multiple predictions. in at least cases, additional predictions are highly similar to the functional copy. in genome sequence assembly, the reads originating from different copies of a repeat appear identical and cause assembly errors. therefore these predictions seem to be due to assembly errors rather than constituting true paralogs. in the other cases differences in the flanking regions and the rnase p rna gene itself indicate that we see the results of gene duplications. even though the promoter might be specific for an organism, it may differ from other polymerase iii transcripts within one species. in each of these cases, a presumably functional rnase p rna like promoter structure was found for only one of the copies. similar duplication patterns are observed in closely related primate, fish and rodent. for instance, both homo sapiens and pan troglodytes have functional copies on chromosome and a pseudogene on chromosome among teleosts, both danio rerio and gasterosteus aculeatus have their functional copies and pseudogenes on the chromosome in rodent family, rattus norvegicus and mus musculus have the pseudogenes spreading on at least different chromosomes. novel rnase p rna genes were detected by bcheck in many fungi, which had not been analyzed in much detail so far. only eight sequences which were reported before were not recognized by bcheck. in sequences bcheck found novel rnase p rna genes. the remaining genomes are either unfinished drafts, so that the rnase p rna is not contained in the data, or they belong to clades where rnase p rna may be absent. in plants, red algae, and heterokonts rnase mrp rna, an ancient paralog of rnase p rna, is well described. one may speculate that it substitutes for rnase p rna in these clades, in particular given that multiple copies of rnase mrp rna are present in plant genomes. a recent, detailed overview of the evolution of rnase p rna and its associated proteins can be found in. an incomplete genome assembly explains e.g. the deviant rnase p rna in the genome of the elephant, which shows a canonical sequence interrupted by a run of ns in the latest assembly. on the other hand, we suspect that we missed the rnase p rna in some fungi and in some of the basal eukaryotes because of highly divergent sequence and secondary structure. software, webserver, and database bcheck was written in python. input consists of dna or rna sequences in fasta format, predictions are output with fasta format or with secondary structure annotated. besides the default search algorithm, bcheck also gives the option for searching with cm only. however, cm-only search is at least times slower. we set up a bcheck webserver to facilitate online rnase p rna gene prediction. a searchable rnpb database was developed, including genes for microbial organisms, eukaryote organisms and gos sample sequences. the predicted pseudogenes for eukaryote organisms are also included. the "rnpb database" uses a hierarchical tree structure, consisting of tables, implementing preorder tree traversal algorithm to process the query efficiently. blast is also offered in the server for homology search against the database compromising unique rnpb genes. the server can be accessed at http://rna.tbi.univie.ac.at/bcheck. the bcheck-pipeline can also be downloaded from the same location for local use in a linux environment. discussion and  the rapidly increasing size of sequence databases requires efficient tools for data analysis. in particular, homology annotation of small ncrnas, with their short and often poorly conserved sequences poses a severe problem for large-scale annotation. here, we describe bcheck, an efficient pipeline to determine rnase p rna genes across all three domains of life. in order to deal with the high variability of the rnase p rna sequences and structures, we employ descriptor-based models specific for sub-families instead of a single pattern to construct more efficient filters. in the second step, improved covariance models are used to validate the candidates from the dm step and to determine nearly exact gene boundaries. with bcheck, we were able to determine the rnase p rna genes in out of archaea, out of bacteria, and out of eukaryotes. 61% of the prokaryotic sequences and 25% of eukaryotic results were not annotated previously. the quality of the predicted rnpb genes is much better than a large fraction of the - usually blast-based - annotation available through genbank. the size and diversity of eukaryote genomes brings with it a particular challenge in finding rnase p rna genes, because this diversity is reflected in many aberrant features of the rnase p rna itself. using the fungi-specific dms, we uncovered previously unannotated sequences, which are downloadable from the bcheck server. as in previous studies, we did not find rnase p rna candidates in plants and heterokonta. since bcheck is more than times faster than the direct application of infernal, it is suitable in particular as a tool to screen large high-throughput sequencing data. with only a handful of false negatives, bcheck provides a highly efficient way to annotate newly sequenced genomes. a particular strength of bcheck is its applicability to metagenomics data. among the prokaryotic genomes for which bcheck failed to detect a candidate, have a size below mbp. one of them, nanoarchaeum equitans, is among three organisms having extremely condensed genomes with length even below mbp. nanoarchaeum equitans appears to have lost its rnase p rna through genomic rearrangement at trna genes under the pressure of genome condensation. in figure we summarize the correlations between genome size and the size of prokaryotic rnase p rna. even though there is no strong correlation indicated in arca and baca subfamilies, the evolutionarily younger bacb and arcm seem to be more strongly affected by changes in genome size. at present, bcheck models were built on the conserved sequence and secondary structure features of a large sample of rnase p rna genes. conceivably, the predictive power of the pipeline could be improved further by including additional information. for instance, promoter and terminator regions might be utilized. a recent survey for 7sk rnas capitalized largely on the conserved features of the characteristic pol-iii promoter signals of this ncrna class. a similar strategy might allow a further relaxation of the dm pattern in favor of a second filter utilizing the promoter and terminator motifs. authors' contributions ilh designed the study. dy constructed descriptors, designed and implemented the pipeline. mm prepared the training sets for eukaryote models and performed eukaryote hit validation with promoter analysis. all authors collaborated on analyzing the data and writing the manuscript. all authors have read and approved the final manuscript. 
bcheck is implemented as webserver and can also be downloaded for local use from http://rna.tbi.univie.ac.at/bcheck we present bcheck, a wrapper tool which predicts rnase p rna genes by combining the speed of pattern matching and sensitivity of covariance models. scanning all microbial genomes in genbank identifies rnase p rna genes in 98% of microbial chromosomal sequences within just hours on single cpu. for eukaryotic chromosomes bcheck could identify the known rnase p rna genes in out of metazoan genomes and out of fungi genomes. bcheck predicted novel eukaryotic rnase p rna genes, of which are from fungi. scanning of meta-genomic data from the global ocean sampling expedition, comprising over million sample sequences, predicted unique genes, 98% of which fall into ancestral bacteria a type of rnase p rna and 66% of which have no close homolog to known prokaryotic rnase p rna. the combination of efficient filtering by means of a descriptor-based search and subsequent construction of a high-quality gene model by means of a covariance model provides an efficient method for the detection of rnase p rna genes in large-scale sequencing data. comparing to existing annotations found in of the genbank files, bcheck predictions have more intact structure and are automatically classified by subfamily membership. the core of bcheck is a library of subfamily specific descriptor models and covariance models.
 effective bioinformatics solutions are needed to tackle challenges posed by industrial-scale genome annotation. we present bcheck, a wrapper tool which predicts rnase p rna genes by combining the speed of pattern matching and sensitivity of covariance models. the core of bcheck is a library of subfamily specific descriptor models and covariance models.  scanning all microbial genomes in genbank identifies rnase p rna genes in 98% of microbial chromosomal sequences within just hours on single cpu. comparing to existing annotations found in of the genbank files, bcheck predictions have more intact structure and are automatically classified by subfamily membership. for eukaryotic chromosomes bcheck could identify the known rnase p rna genes in out of metazoan genomes and out of fungi genomes. bcheck predicted novel eukaryotic rnase p rna genes, of which are from fungi. gene duplication events are observed in at least metazoan organisms. scanning of meta-genomic data from the global ocean sampling expedition, comprising over million sample sequences, predicted unique genes, 98% of which fall into ancestral bacteria a type of rnase p rna and 66% of which have no close homolog to known prokaryotic rnase p rna.  the combination of efficient filtering by means of a descriptor-based search and subsequent construction of a high-quality gene model by means of a covariance model provides an efficient method for the detection of rnase p rna genes in large-scale sequencing data. bcheck is implemented as webserver and can also be downloaded for local use from http://rna.tbi.univie.ac.at/bcheck 