in bacteria , the number of characterized small , noncoding rnas ( srnas ) that have intrinsic functions as regulators has steadily increased in recent years . many srnas act by posttranscriptionally regulating mrnas via basepairing interactions ( 1 ) . in escherichia coli , all of the srnas that act by basepairing affect either the stability or translation of the mrna target . in most cases , the mrna targets of srna regulation are trans - encoded , and the srna : mrna basepairing interactions are interrupted by gaps in the pairing . further , most srnas in this class bind to the rna chaperone hfq , which has been shown to facilitate the interaction between many srnas and their targets ( 2 ) . here , we describe a program , targetrna , which can effectively predict mrna targets of basepairing srnas . while a number of approaches have been described for identifying targets of microrna genes in eukaryotes ( 37 ) , there have been relatively few computational tools developed for characterizing targets of srna regulators in bacteria . ( 8) describe one such tool , which has been applied successfully in the genome of listeria monocytogenes , though the program is not available as a webserver . vogel and wagner ( 9 ) offer a comprehensive review of approaches , both computational and experimental , for identifying targets of bacterial srnas . the program we describe here , targetrna , is accessible via a webserver that has been operating and publicly available since 2005 , processing approximately 1000 sequence submissions per month . the webserver consists of a 16 cpu parallel computing cluster , and targetrnas underlying search algorithm has been designed for parallel computation , in order to increase performance and to process efficiently a large number of sequence submissions . the predictive performance of targetrna has been validated experimentally in e. coli using both northern blot and microarray experiments ( 10 ) . additionally , predictions from targetrna have been validated in other organisms , such as in vibrio cholerae ( 11 ) and in neisseria meningitidis ( 12 ) , or are consistent with experimentally validated interactions , such as in salmonella ( 13 ) . targetrna takes , as input , a genomic sequence that may correspond to a srna gene . targetrna then searches each annotated message in the user - specified genome for mrnas that evince statistically significant basepair - binding potential to the input srna sequence . basepair - binding potential of a srna with each mrna is determined using one of two user - selected hybridization scoring methods . a detailed description of the hybridization scoring methods has been described previously ( 10 ) . in summary , waterman dynamic program ( 14 ) , except that instead of assessing homology potential , basepairing potential is assessed . the stacked basepair model of hybridization scoring is based on stacking and destabilizing energies of interacting sequences . the stacked basepair model calculates the minimum free energy of hybridization for two rna sequences , without allowing intramolecular basepairings . this model for hybridization scoring closely follows that developed and used for the rnahybrid algorithm ( 7 ) . the stacked basepair model is computationally more intensive than the individual basepair model and , as a result , increases the time required for calculating basepair binding potential by a factor of approximately five for most sequence inputs . once targetrna determines hybridization scores for the srna sequence with each message in a genome , the statistical significance of each potential srna : mrna interaction is assessed . determination of statistical significance is similar to that described for the rnahybrid algorithm ( 7 ) . ten thousand random rna sequences are generated such that the nucleotides in the random sequences are drawn from the distribution of nucleotides in the actual mrna search space . the hybridization score is computed for each of these random sequences and the srna sequence . the resulting distribution of ten thousand hybridization scores is used to estimate a p - value for an srna : mrna hybridization score by determining the probability of observing a score , by chance , equal to or less than the given srna : mrna hybridization score . after computing the statistical significance of basepair binding between a srna sequence and each message in a genome , targetrna outputs a ranked list of mrnas in a genome whose basepair - binding potential with the srna sequence meets a significance threshold ( the default is a p - value  0.01 ) . messages with statistically significant basepair - binding potential are considered candidate targets of srna regulation . figure 1 illustrates example output from targetrna when searching for mrna targets of the srna gene spot42 in e. coli ( 15 ) . as shown in figure 1 , targetrna outputs , for each candidate mrna target identified , an annotation of the mrna , a visual representation of its predicted basepair binding with the srna , and a p - value corresponding to the significance of the hybridization score of the predicted srna : mrna interaction . to facilitate further investigation of candidate message targets , each identified target is linked to the entrez gene database ( 16 ) from the national center for biotechnology information . the time required for targetrna to process an input sequence and generate results depends on the length of the sequence and the parameter selection but typically takes only a few seconds . output from targetrna is available via both a formatted web page and a text file . figure 1.the figure illustrates example output from using the targetrna webserver with default parameter settings to search for message targets of the srna spot42 in escherichia coli . in the middle of the figure , the six message targets predicted by targetrna are summarized . in the bottom of the figure , the predicted interaction between spot42 and one of the six predicted targets , galk , is illustrated . the predicted interaction between spot42 and galk consists of 41 nucleotides ( from nucleotide 21 to 61 ) in the 109 nucleotide srna spot42 , and 39 nucleotides ( from 19 nucleotides upstream of the galk start codon to 20 nucleotides downstream in the galk coding sequence ) in the galk message . the figure illustrates example output from using the targetrna webserver with default parameter settings to search for message targets of the srna spot42 in escherichia coli . in the middle of the figure , the six message targets predicted by targetrna are summarized . in the bottom of the figure , the predicted interaction between spot42 and one of the six predicted targets , galk , is illustrated . the predicted interaction between spot42 and galk consists of 41 nucleotides ( from nucleotide 21 to 61 ) in the 109 nucleotide srna spot42 , and 39 nucleotides ( from 19 nucleotides upstream of the galk start codon to 20 nucleotides downstream in the galk coding sequence ) in the galk message . the targetrna webserver provides a number of advanced search options that allow users more flexible control over the target search space beyond that provided by the default parameter settings . targetrna provides the option of automatically identifying and removing the region of the srna sequence corresponding to the terminator stem - loop since , in many cases , the terminator stem - loop does not participate in the srna : mrna interaction . users have the option of focusing their search around the 5 utr or 3 utr of messages , specifying the number of nucleotides to include upstream and downstream of the messages start codon or stop codon . specifying regions around the 5 utr to be searched may be advantageous since many documented target interactions occur in particular regions , such as around the ribosome - binding sites , of messages . a seed , which corresponds to a minimum required length for at least one stretch of consecutive basepaired nucleotides in the srna : mrna interaction , can also be specified . the seed is meant to reflect , biologically , the initial interaction between srna and mrna , which has been shown in some cases to be a stretch of unpaired nucleotides in a loop of the srna that first basepairs with the target message . while targetrna searches each annotated message in a genome by default , users have the option of searching an individual message in order to explore more carefully a particular interaction predicted by targetrna . when searching for targets of a srna in a given organism , targetrna also offers the option of calculating the hybridization scores of orthologous targets with orthologous srnas in other organisms . since many srna genes are conserved across related species , the program can thus suggest whether it is likely that the targets and hybridization interactions are conserved . the various user - adjustable program parameters have the benefit of allowing a user to explore the tradeoff between sensitivity and specificity when assessing results of the targetrna program . for instance , removing the srna terminator sequence , focusing searches for targets to regions around translation start sites of messages , and setting a seed threshold above about five nucleotides can eliminate many false positive predictions . however , too much stringency with these parameters may result in a lack of identification of true targets . for example , some srna : mrna interactions include the terminator sequence of the srna , such as the oxys : fhla interaction ( 17,18 ) in e. coli , and some srnas interact with messages somewhat distant from the message 's start of translation , such as dsra ( 19 ) and rpra ( 20 ) when interacting with rpos in e. coli . thus , the default parameter settings provide only a starting point for message target investigation . default parameter settings were determined by optimizing performance of targetrna on srna : mrna interactions in e. coli reported prior to 2005 . considering the recent growth in the number of srna : mrna interactions reported in the literature across a range of bacterial species , we have revisited the issue of whether different default parameter settings would improve the performance of targetrna . when accounting for a broad set of srna : mrna interactions in different species , we did not find a set of parameters that led to significant improvement , over the current default parameter settings , in successfully identifying targets of srna regulation . a recent addition to the targetrna webserver is a companion program to targetrna called rnatarget , which provides  reverse searching capabilities . whereas targetrna takes as input the sequence of a candidate srna region and searches the genome for possible message targets , rnatarget takes as input the sequence of a candidate message target of an unknown srna regulator and searches the genome for regions containing possible srna regulators of the target sequence . rnatarget searches all intergenic sequences greater than 50 nucleotides in length in the genome for regions that evince significant basepair - binding potential to the input candidate target sequence . rnatarget outputs a ranked list of intergenic regions in the genome whose basepair - binding potential with the target sequence meets a significance threshold ( the default is a p - value  0.01 ) . intergenic regions with statistically significant basepair - binding potential are considered as candidate regions corresponding to a srna regulator . figure 2 illustrates example output from rnatarget when searching intergenic regions for candidate srna regulators of the mrna target galk in e. coli . it has been reported previously that the srna spot42 , which resides in the intergenic region of the genome between genes pola and yiha , interacts with and regulates galk ( 21 ) . as shown in figure 2 , rnatarget outputs , for each intergenic region identified , the flanking protein - coding genes , a visual representation of the predicted basepair binding between the two genomic sequences , and a p - value corresponding to the significance of the hybridization score of the predicted mrna : srna interaction . it is worth noting that rnatarget searches only for genomic regions demonstrating basepair - binding potential to the target sequence , it does not attempt to identify other properties of genomic sequences suggestive of srna genes , such as transcription initiation or termination sequences . several other computational programs are available for predicting srna genes in a genome based on various sources of evidence , including transcription signals and comparative genomics information ( 22 ) . figure 2.the figure illustrates example output from using the rnatarget program with default parameter settings to search for intergenic regions in e. coli that evince basepair binding potential with a region of the galk message around its ribosome binding site . ( b ) details of the predicted interaction between galk and one of the intergenic regions , between genes pola and yiha , is shown . the srna spot42 , which resides in this intergenic region , is known to interact with and regulate galk ( 21 ) . the predicted interaction between the intergenic region and galk consists of 41 nucleotides ( from nucleotide 167 to 207 ) in the 380 nucleotide pola yiha intergenic region , and 39 nucleotides ( from 19 nucleotides upstream of the galk start codon to 20 nucleotides downstream in the galk coding sequence ) in the galk message . the figure illustrates example output from using the rnatarget program with default parameter settings to search for intergenic regions in e. coli that evince basepair binding potential with a region of the galk message around its ribosome binding site . ( b ) details of the predicted interaction between galk and one of the intergenic regions , between genes pola and yiha , is shown . the srna spot42 , which resides in this intergenic region , is known to interact with and regulate galk ( 21 ) . the predicted interaction between the intergenic region and galk consists of 41 nucleotides ( from nucleotide 167 to 207 ) in the 380 nucleotide pola yiha intergenic region , and 39 nucleotides ( from 19 nucleotides upstream of the galk start codon to 20 nucleotides downstream in the galk coding sequence ) in the galk message . targetrna is a freely available webserver that predicts message targets of srna action in bacteria . assessment of targetrna 's performance suggests that the predictive performance of targetrna varies between srnas . for some srna regulators where one or more targets have been reported in the literature , targetrna successfully identifies the majority of targets , whereas for other srna regulators with one or more targets , targetrna identifies few , if any , targets ( 10 ) . targetrna operates under the assumption that the basepair - binding potential of two genomic sequences , corresponding to an srna and a mrna target , can serve as a predictor , albeit imperfect , for the interaction of the two rnas . conserved basepair - binding potential of two genomic sequences across different genomes can provide further evidence for srna : mrna interaction . however , other factors that may contribute to srna : mrna interactions , such as rna secondary structure or the role of hfq , are not modeled by the program . as more examples of srna : mrna interactions are reported across a range of bacteria , we will gain a better understanding of the various rna properties and components within the cell that contribute to the interactions , and computational methods that aid in investigation of these interactions can be evolved appropriately to incorporate the new insights .
many small rna ( srna ) genes in bacteria act as posttranscriptional regulators of target messenger rnas . here 
 , we present targetrna , a web tool for predicting mrna targets of srna action in bacteria . 
 targetrna takes as input a genomic sequence that may correspond to an srna gene . 
 targetrna then uses a dynamic programming algorithm to search each annotated message in a specified genome for mrnas that evince basepair - binding potential to the input srna sequence . 
 based on the calculated basepair - binding potential of each message with the given srna regulator , targetrna outputs a ranked list of candidate mrna targets along with the predicted basepairing interaction of each target to the srna . 
 the predictive performance of targetrna has been validated experimentally in several bacterial organisms . 
 targetrna is freely available at http://snowwhite.wellesley.edu/targetrna .