like proteins , finding structural similarities between rnas often helps biologists to better understand their shared potential functionality that might not be detected only using rna primary sequences . as rna structures currently solved and deposited in the protein data bank ( pdb ) ( 1 ) continue to grow in both number and size , exhaustive search approaches to comparing a query rna structure with every rna structure in the pdb can be very difficult and time consuming because finding their similar substructures has been shown to be computational intractable ( 2 ) . therefore , currently available search tools , such as rna frabase ( 3,4 ) and fastr3d ( 5 ) , employ some heuristics to search the pdb for fragments of known rna 3d structures that possess the same 2d structures as found in the entire query rna , which can be implemented in an efficient way . however , these search tools still suffer from some limitations as described below , although they can serve as useful tools to process and analyze various aspects of rna 3d structures in the pdb . basically , both rna frabase and fastr3d , as mentioned above , are mainly dedicated to searching for rnas whose 2d structures annotated in the pdb are entirely identical to that of the query rna . in particular , they do not allow insertions and deletions in their structural alignments for comparing the query with each rna structure in the pdb . however , there are many rnas whose overall 3d structures are similar , but their entire 2d structures , as well as their primary sequences and lengths , are not the same . for instance , the two trnas ( pdb ids : 1ehz and 3kix ) shown in figure 1 exhibit similar whole 3d structures , but they have different sequences , lengths and 2d structures annotated in the pdb . therefore , while querying one of these two trnas , rna frabase and fastr3d both fail to find the other one with any structural similarity . on the other hand , some rnas may share only similar 3d substructures , rather than entire 3d structures , as illustrated in figure 2 . due to the intrinsic limitations described above , both rna frabase and fastr3d will miss these locally similar rna structures in their search results . in addition , neither of rna frabase and fastr3d currently provides any statistical values ( e.g. e - value ) for each rna structure hit to indicate its significance . figure 1.two trnas : ( a ) pdb i d : 1ehz and chain i d : a ; ( b ) pdb i d : 3kix and chain i d : w ; ( c ) superimposition of their 3d structures with root mean square deviation ( rmsd ) of 2.457  ; and ( d ) their 1d sequences ( with identity of 44% ) and 2d structures annotated in the pdb . figure 2.two trnas : ( a ) pdb i d : 1wz2 and chain i d : d ; ( b ) pdb i d : 3kix and chain i d : v ; and ( c ) their two similar substructures , one in blue and magenta ( with an rmsd of 1.314  ) and the other in green and orange ( with an rmsd of 1.622  ) . two trnas : ( a ) pdb i d : 1ehz and chain i d : a ; ( b ) pdb i d : 3kix and chain i d : w ; ( c ) superimposition of their 3d structures with root mean square deviation ( rmsd ) of 2.457  ; and ( d ) their 1d sequences ( with identity of 44% ) and 2d structures annotated in the pdb . two trnas : ( a ) pdb i d : 1wz2 and chain i d : d ; ( b ) pdb i d : 3kix and chain i d : v ; and ( c ) their two similar substructures , one in blue and magenta ( with an rmsd of 1.314  ) and the other in green and orange ( with an rmsd of 1.622  ) . in this study , we have therefore developed a blast - like search tool , called r3d - blast , to overcome the above limitations in rna frabase and fastr3d . the basic idea behind r3d - blast is that all the rna 3d structures in the pdb are first encoded as 1d structural sequences using a structural alphabet developed in our previous work ( 6 ) , and blast , a popular bioinformatics tool to find homologous proteins / rnas only based on their sequence similarity ( 7 ) , is then applied to search these 1d structural sequences for the rnas whose 1d structural sequences are locally similar to that of a query rna . the experimental results have shown that our r3d - blast ( i ) can quickly return its search result to the user , ( ii ) has better performance than both rna frabase and fastr3d for finding those rnas whose entire or nearly entire 3d structures are similar to that of the query rna and ( iii ) outputs a lot of other rnas that have substructures similar to that of the query , which , however , can not be done either by rna frabase or fastr3d . in addition , our r3d - blast provides an e - value for each rna substructure hit to indicate its statistical significance . it is noteworthy that , although our r3d - blast is dedicated to searching for similar rna substructures , it can still be used to find some rna structural motifs that particularly are single - stranded , such as hairpin loops and pseudoknots , where their nucleotides are contiguous in the rna sequence . actually , several useful tools , like primos ( 8) and fr3d ( 9 ) , have currently been developed to search for a wide variety of motifs in rna structures , including multi - stranded ones like k - turn , s - turn and sarcin - ricin motifs . primos uses two pseudo - torsion angles to represent rna backbone conformations and performs structural motif searches by analyzing the differences in the backbone conformation between a query motif and the rna structures in the pdb . as for fr3d , it searches for a query motif in an rna structure based on a base - centered approach that analyzes geometric discrepancy between the query and candidate motifs and/or uses symbolic constraints specifying base  base interaction , base identity and sequence continuity . we first encode all the rna 3d structures currently deposited in the pdb ( as of december 2010 ) as 1d structural sequences using the structural alphabet of 23 distinct nucleotide conformations , which was constructed previously by us using the pseudo - torsion angles (  and  ) of rna nucleotide backbones ( 6 ) . we then apply blast ( 7 ) to searching these 1d structural sequences for the rna substructures whose 1d structural sequences are similar to that of the query rna substructure . to properly score each alignment obtained by r3d - blast , we also define a 23    23 blosum - like substitution matrix based on the observed and estimated probabilities of occurrence for each pair of aligned structural letters ( 6 ) . in addition , our r3d - blast provides an e - value to measure the statistical significance of each rna substructure hit . altschul equation e  =  kmn ( 10 ) , where m and n , respectively , are the sizes of the query rna structure and the database , s is a raw score of the structural alignment and k and  are statistical parameters , respectively , depending on the structural letter composition of rna structures being aligned and the used scoring function . to obtain accurate parameter estimates , we utilize the island method , which was proposed by altschul et al . ( 11 ) for estimating our k and  values , according to different sets of gap open and extension penalties . it is inevitable that some rna substructure hits returned by r3d - blast , particularly with high e - values , may not be similar to the substructure of the query rna in their 3d structures . therefore , we design an optional filter for further screening out the rna substructure hits whose rmsd values and/or structural alignment scores ( sas ) with respect to the query rna substructure are greater than some predefined thresholds . sas is defined as 100    rmsd/(number of aligned residues ) , which was introduced by kolodny et al . ( 12 ) , who have shown that sas can serve as a useful measure to separate good structural alignments from less good ones . in the interest of running time , except the blast program that was downloaded from ncbi , the kernel of r3d - blast , as well as its web interface , was written in php . the server of r3d - blast is currently installed on ibm pc with 2.8 ghz processor and 3 gb ram under linux system and its rna structure database is updated every 3 months . r3d - blast is easy to operate for the user either by entering a pdb i d for the query rna structure or by uploading its file in the pdb format , optionally with specified residue range . then r3d - blast will quickly return its search results to the user in an output page that contains the information of each rna hit in the pdb , including its pdb i d , chain i d , title to describe the experiment , classification of molecule , experimental method to determine the structure , structure resolution and released date , and the details of its structural alignment with the query , including e - values , range and length of aligned residues and calculated rmsd and sas ( if rmsd / sas filter is selected ) . in the output page , r3d - blast also provides the user with a hyperlink to show the graphical display of the structural superposition between the query and each r3d - blast hit by jmol , as well as the details of their structural sequence alignment and primary sequence alignment . if needed , the user can select different parameter settings about alignment ( that can be either gapped or ungapped ) and its used gap penalty to run r3d - blast , and also modify the e - value threshold to further restrict the search results of r3d - blast . figure 3.the top panel shows the interface of r3d - blast with a query of trna ( pdb i d : 1wz2 and chain i d : d ) , and the bottom panel presents its search results by highlighting two similar substructures identified in another trna ( pdb i d : 3kix and chain i d : v ) and their superpositions with the corresponding substructures of the query . the top panel shows the interface of r3d - blast with a query of trna ( pdb i d : 1wz2 and chain i d : d ) , and the bottom panel presents its search results by highlighting two similar substructures identified in another trna ( pdb i d : 3kix and chain i d : v ) and their superpositions with the corresponding substructures of the query . to validate r3d - blast , we have tested it on some rna 3d structures , and also compared its search results with those obtained by similar tools , rna frabase ( version 2.0 ) and fastr3d , even though rna frabase and fastr3d are both designed for searching similar whole rna structures while our r3d - blast is for similar rna substructures . unless specified , all the tools were run on the respective servers with default parameters . the experimental results we obtained by testing r3d - blast , rna frabase and fastr3d on five different kinds of rnas with different lengths are shown in table 1 , where the percentage in the title of the table means the query coverage , which is defined as the percent of the query length that is included in the structural alignment . except trna in this testing dataset , our r3d - blast found the same or more number of rna hits with 3d structures entirely similar to that of the query ( i.e. with query coverage of 100% ) as compared to both rna frabase and fastr3d . this is because that , as mentioned before , two rnas may share a very similar whole 3d structure even though their 2d structures , as well as their sequence lengths , are different . as for the trna , both rna frabase and fastr3d returned more rnas when compared with the rna hits with 100% query coverage in the search result of our r3d - blast . recall that the algorithms in both rna frabase and fastr3d were designed to search for those rnas whose entire 2d structures are exactly the same as that of the query . indeed , those rnas found by rna frabase or fastr3d have the same 2d structures . however , some regions near the ends of these trna 3d structures are not quite similar . as a result , the dissimilar regions were finally removed from the trnas returned by our r3d - blast . in fact , all the trnas identified by both rna frabase and fastr3d , along with other trnas , can still be found by our r3d - blast with the query coverage of at least 90% . as also shown in table 1 , our r3d - blast returned a lot of other rnas with their substructures similar to that of the query trna ( with < 90% query coverage ) , which can not be done either by rna frabase or by fastr3d . finally , in table 2 we show the cpu time of our r3d - blast when querying with the rnas listed in table 1 . as indicated in table 2 , our r3d - blast can finish its jobs within a few to several seconds if the option to filter by rmsd / sas is not selected ( default ) ; otherwise , additional time is required for computing the rmsd and sas values between the query and all the hits returned by r3d - blast , which can be from a few seconds to several minutes , depending on the number of the r3d - blast hits and their query coverages . table 1.comparison of search results obtained by r3d - blast , rna frabase ( version 2.0 ) and fastr3dquerypdb_chainrange / lengthr3d - blastrnafastr3d100%90%<90%totalfrabasepseudoknot2avy_a499 - 544/468913811149 ( 2.4)83 ( 0.7)40 ( 0.6)riboswitch1y27_x14 - 81/68391827 ( 1.2)1 ( 0)1 ( 0)trna1ehz_a1 - 76/76762259321 ( 3.1)15 ( 1.6)17 ( 1.3)5s rrna3cc2_91 - 121/1214063184247 ( 2.3)19 ( 0.2)17 ( 0.2)ribozyme1x8w_b96 - 414/247111516 ( 2.1)1 ( 0)1 ( 0)16s rrna2avy_a5 - 1534/15302811991207 ( 4.0)2 ( 0.1)0 ( 0)the values presented in the parentheses for each tool are the average rmsd values (  ) between the query and hits . 
 table 2.cpu time for running our r3d - blastqueryfiltered by rmsd / sasnoyespseudoknot6  s1.2  minriboswitch1  s4  strna5  s44  s5s rrna10  s1  minribozyme3  s7  s16s rrna36  s21.2  min comparison of search results obtained by r3d - blast , rna frabase ( version 2.0 ) and fastr3d the values presented in the parentheses for each tool are the average rmsd values (  ) between the query and hits . to the best of our knowledge , our r3d - blast is the first web server that can quickly and accurately search the pdb for rnas that share similar 3d substructures with a query rna . we believe that it can be helpful for biologists to reveal functional and evolutionary relationships of rnas even without detectable sequence similarity . national science council of republic of china under grants ( nsc97 - 2221-e-009 - 081-my3 to c.l.l . and nsc99 - 2113-m-009 - 005-my3 to h .- t . c. ) in part . funding for open access charge : national science council of republic of china .
r3d - blast is a blast - like search tool that allows the user to quickly and accurately search against the pdb for rna structures sharing similar substructures with a specified query rna structure . 
 the basic idea behind r3d - blast is that all the rna 3d structures deposited in the pdb are first encoded as 1d structural sequences using a structural alphabet of 23 distinct nucleotide conformations , and blast is then applied to these 1d structural sequences to search for those rna substructures whose 1d structural sequences are similar to that of the query rna substructure . 
 r3d - blast takes as input an rna 3d structure in the pdb format and outputs all substructures of the hits similar to that of the query with a graphical display to show their structural superposition . 
 in addition , each rna substructure hit found by r3d - blast has an associated e - value to measure its statistical significance . 
 r3d - blast is now available online at http://genome.cs.nthu.edu.tw/r3d-blast/ for public access .