Non-coding regulatory RNAs (ncRNAs) regulate a host of gene functions in prokaryotes, e.g., transcription and translation regulations, RNA processing and modification, and mRNA stability. Some ncRNAs have been identified experimentally, but many are yet to be found. ncRNAs can be classified as either cis- or trans-acting. cis-ncRNAs perfectly complement their target genes and are usually encoded on the anti-sense strands of the targets. On the contrary, trans-ncRNAs regulate their target genes through short and often imperfect base-pairings with the targets, and are usually encoded elsewhere on the genome.

A whole-genome thermodynamic analysis can be performed to identify all imperfect but stable base-pairings between all annotated genes and some genomic regions encoding ncRNAs from the same species. However, the sizes of these base-paring regions are short and variable, and their melting temperatures vary greatly between perfectly and imperfectly matched targets. It is difficult to predict trans-acting ncRNAs solely based on the thermodynamic analysis. Therefore, we also have to consider known ncRNA structures to improve our predictions. We find that Hfq-binding ncRNAs, which require Hfq protein to function, share three common structural properties. We predict these special ncRNAs in E. coli and Agrobacterium tumefaciens according to a systematic, novel 5-step approach based on thermodynamic analyses as well as known structural properties of this class of ncRNAs.

Whole genome tiling microarrays are chosen to validate our predictions. We describe how the microarrays have been designed, created, and validated for E. coli MG1655 and Agrobacterium tumefaciens C58. We match our new ncRNA prediction results with known ncRNAs, calculate correlation coefficient values between each ncRNA candidate and their predicted targets measure by the whole-genome tiling microarrays, and confirm the results with 3 other ncRNA identification software tools. We also perform a gene ontology network analysis to reveal the associations of ncRNA candidates and their predicted targets. Our novel 5-step prediction method is generally applicable to other prokaryote species and may help advance ncRNA research in prokaryotes.