rna can play an important functional role in catalysis , e.g. ribozymes are rna enzymes that cleave rna phosphodiester bonds at specific sites ( 1 ) ; see ( 2 ) for an overview of potential therapeutic applications of ribozymes to cleave mrnas of oncogenes ( ras or bcr - abl ) and viral transcripts ( hiv-1 ) , to overcome drug resistance , control arthritis , etc .
such is the case for the aminoglycoside and macrolide families of antibiotics , which disrupt rna translation in prokaryotes by targeting ribosomal ( rrna ) ( 3 ) .
in contrast to mrna , noncoding rna ( ncrna ) is transcribed from genomic dna and plays a biologically important role , although it is not translated into protein .
examples of ncrna include ribozymes , riboswitches , micro rna , small interfering rna ( 4 ) , trna , rrna , etc .
riboswitches have recently been discovered to interact with small ligands and up- or down - regulate certain genes .
breaker and co - workers ( 5 ) report the crystal structures of the add a - riboswitch and xpt g - riboswitch aptamer modules , which distinguish between bound adenine and guanine ; see ( 6 ) for an overview of bacterial riboswitches , and ( 7 ) for the structure , as given in the pdb code 1u8d of a guanine - responsive riboswitch with the metabolite hypoxanthine .
rnaomics ( 8) , analogous to proteomics , concerns aspects of the secondary and tertiary structure , folding pathway , kinetics , comparison , function and regulation of all rna in a living organism .
rnaomics requires the application of numerous existent tools , as well as the development of new computational methods .
well - known rna computational tools include secondary structure prediction web servers mfold ( 9 ) and vienna rna package ( 10 ) , the sfold web server ( 11 ) to sample secondary structures according to the boltzmann probability distribution , the trnascan - se gene finder for trna ( 12 ) , multiple sequence alignment for the statistical detection of rna secondary structure msari ( 13 ) , dynamic programming pairwise sequence - structure alignment dynalign ( 14 ) , tertiary structure modeling tool mc - sym ( 15 ) , etc .
only a few of the many important computational tools for rna structure prediction , gene finding , alignment , etc . have been listed . in this paper
, we describe the web server rnaloss , based on the algorithm of clote ( 16 ) , which computes an aspect of the folding landscape of an rna nucleotide sequence s = s1 ,  ,  sn .
given s , this algorithm runs in time o(n ) and space o(n ) , and computes for each k , the number of k - locally optimal secondary structures ( explained below ) .
work by clote ( 16 ) was motivated by the following question , as has been suggested for proteins ( 17 ) : is it the case that rna has been under selective pressure to fold rapidly ? using the algorithm of the web server rnaloss , it appears that structural rna has a different folding landscape than random rna of the same dinucleotide frequency ; specifically , for small values of k , there appear to be fewer k - locally optimal secondary structures than in random rna . related , but distinct work has appeared in ( 1821 ) , for discussion see ( 16 ) .
a secondary structure for an rna sequence s = s1,  ,sn is an expression s = s1,  ,sn involving dot , left and right parenthesis , which is well balanced , such that nucleotides corresponding to matching parentheses are either watson  crick complements or gu wobble pairs .
a secondary structure s on rna sequence s = s1,  ,sn is defined to be a set of ordered pairs ( i , j ) , such that i + 3 < j and the following conditions are satisfied . 
 watson  crick or gu wobble pairs : if ( i , j ) belongs to s , then pair ( ai , aj ) must be one of the following canonical base pairs : ( a , u ) , ( u , a ) , ( g , c ) , ( c , g ) , ( g , u ) and ( u , g).threshold requirement : if ( i , j ) belongs to s , then j  i > 3 ; i.e. there must be at least three unpaired bases in a hairpin loop.non-existence of pseudoknots : if ( i , j ) and ( k , l ) belong to s , then it is not the case that i < k < j < l.no base triples : if ( i , j ) and ( i , k ) belong to s , then j = k ; if ( i , j ) and ( k , j ) belong to s , then i = k. watson  crick or gu wobble pairs : if ( i , j ) belongs to s , then pair ( ai , aj ) must be one of the following canonical base pairs : ( a , u ) , ( u , a ) ,
( g , c ) , ( c , g ) , ( g , u ) and ( u , g ) . threshold requirement : if ( i , j ) belongs to s , then j  i > 3 ; i.e. there must be at least three unpaired bases in a hairpin loop . non - existence of pseudoknots : if ( i , j ) and ( k , l ) belong to s , then it is not the case that i < k < j < l. no base triples : if ( i , j ) and ( i , k ) belong to s , then j = k ; if ( i , j ) and ( k , j ) belong to s , then i = k. a secondary structure is k - locally optimal if it has k fewer base pairs than the maximum possible number [ i.e. than in the nussinov  jacobson optimal structure ( 22,23 ) ] , and yet no base pairs can be added without violating the definition of secondary structure ( e.g. without introducing a pseudoknot ) . to illustrate this notion , consider the rna sequence ggggccccc , which has three as the maximum possible number of base pairs , as given in the structure ( ( (  ) ) ) .
there is only one structure having 3 bp , so the number of 0-locally optimal secondary structures is 1 . on the other hand ,
the latter are listed as follows : ( i ) (  ) .... ( ii ) ( .... ) .. ( iii )  ( ..... ) .
the algorithm of ( 16 ) uses dynamic programming to compute , for each i < j and each k , the number of k - locally optimal secondary structures on the subsequence s = si,  ,sj .
additionally , the algorithm must keep track of visible nucleotides and positions , i.e. those external to any base pair [ for technical details see ( 16 ) ] .
a secondary structure s on rna sequence s = s1,  ,sn is defined to be a set of ordered pairs ( i , j ) , such that i + 3 < j and the following conditions are satisfied . 
 watson  crick or gu wobble pairs : if ( i , j ) belongs to s , then pair ( ai , aj ) must be one of the following canonical base pairs : ( a , u ) , ( u , a ) , ( g , c ) , ( c , g ) , ( g , u ) and ( u , g).threshold requirement : if ( i , j ) belongs to s , then j 
i > 3 ; i.e. there must be at least three unpaired bases in a hairpin loop.non-existence of pseudoknots : if ( i , j ) and ( k , l ) belong to s , then it is not the case that i < k < j < l.no base triples : if ( i , j ) and ( i , k ) belong to s , then j = k ; if ( i , j ) and ( k , j ) belong to s , then i = k. watson  crick or gu wobble pairs : if ( i , j ) belongs to s , then pair ( ai , aj ) must be one of the following canonical base pairs : ( a , u ) , ( u , a ) , ( g , c ) , ( c , g ) , ( g , u ) and ( u , g ) . threshold requirement : if ( i , j ) belongs to s , then j  i > 3 ; i.e. there must be at least three unpaired bases in a hairpin loop .
non - existence of pseudoknots : if ( i , j ) and ( k , l ) belong to s , then it is not the case that i < k < j < l. no base triples : if ( i , j ) and ( i , k ) belong to s , then j = k ; if ( i , j ) and ( k , j ) belong to s , then i = k. a secondary structure is k - locally optimal if it has k fewer base pairs than the maximum possible number [ i.e. than in the nussinov  jacobson optimal structure ( 22,23 ) ] , and yet no base pairs can be added without violating the definition of secondary structure ( e.g. without introducing a pseudoknot ) . to illustrate this notion ,
consider the rna sequence ggggccccc , which has three as the maximum possible number of base pairs , as given in the structure ( ( (  ) ) ) .
there is only one structure having 3 bp , so the number of 0-locally optimal secondary structures is 1 . on the other hand ,
the latter are listed as follows : ( i ) (  ) .... ( ii ) ( .... ) .. ( iii )  ( ..... ) .
the algorithm of ( 16 ) uses dynamic programming to compute , for each i < j and each k , the number of k - locally optimal secondary structures on the subsequence s = si,  ,sj .
additionally , the algorithm must keep track of visible nucleotides and positions , i.e. those external to any base pair [ for technical details see ( 16 ) ] .
the web server rnaloss implements a new algorithm , described in ( 16 ) , running in o(n ) time and o(n ) space , which computes for a given rna sequence s = s1,  ,sn and all k  0 , the number of k - locally optimal secondary structures for s. an rna nucleotide sequence may be input by uploading a fasta - format file or by entering a nucleotide sequence in the blank provided on the web server form .
three tables are returned by rnaloss : the number of k - locally optimal secondary structures , the relative density of states ( i.e. the ratio of number of k - locally optimal structures over the total number of locally optimal structures ) and the minimum free energy ( mfe ) of a sample k - locally optimal secondary structure ( for each value of k , rnaloss computes a single k - locally optimal secondary structure , denoted here as sk , among the many possible k - locally optimal structures . since this feature was implemented for debugging purposes , the current version of rnaloss does not guarantee that sk has lowest mfe as evaluated by rnaeval , over all k - locally optimal secondary structures . for this reason ,
the energy of sample structures sk does not necessarily increase monotonically with increasing value of k ) . for the latter , mfe is computed using rnafold from the vienna rna package .
figure 2 lists the number of k - locally optimal secondary structures as computed by rnaloss for type iii hammerhead ribozyme af170517 from rfam ( 24 ) .
figure 3 presents the relative density of states for k - locally optimal secondary structures for af170517 .
owing to algorithmic time and space constraints , the rnaloss web server immediately processes rna of length at most 60 nt , while for rna of length 61100 nt , the results are emailed to the user . currently , rnaloss refuses to process any sequence of length > 100 nt .
current hardware supporting rnaloss web server consists of a beowulf - style cluster comprising 6 dell 1650 , 2  1300 mhz pentium iii , 2 gb ram with 4 apple xserve , 2  1333 mhz g4 , 2 gb ram and finally 6 dell 1850 , 2  2800 mhz xeon em64 t , 2 gb ram .
pentium iii nodes are running redhat linux 9 , xeon em64 t nodes are running whitebox linux 3 and g4 nodes are running macos 10.2.8 .
upon testing , structurally important rna , such as selenocysteine insertion sequence elements , precursor mrnas , type iii hammerhead ribozymes and trna , all have a markedly smaller number of k - locally optimal structures than that of random rna of the same dinucleotide frequency , for small and moderate values of k. since the free energy of k - locally optimal secondary structures is generally closer to that of the native state for small k , this suggests that structural rna has been optimized not only to have low folding energy ( 25 ) , but also to have relatively few potential kinetic traps .
this suggests that rnaloss might be of use in designing rna sequences for rapid folding .
users may input an rna sequence consisting of upper or lower case nucleotides a , c , g , t , u , either by uploading a fasta - format file ( a ) or by pasting a nucleotide sequence into ( b ) .
output of web server rnaloss on type iii hammerhead ribozyme af170517 from rfam ( 24 ) .
the web server rnaloss outputs a table of number of k - locally optimal secondary structures , for each possible value of k  0 ( shown here ) .
additionally , tables for the relative density of states and mfe values of sample k - locally optimal secondary structures are displayed in the browser ( data not shown ) .
column graph of relative density of states is obtained by clicking a hot link from the previous screen shot . for each value of k
 0 , the ratio of number of k - locally optimal secondary structures over the total number of locally optimal secondary structures is displayed .
 rnaomics , analogous to proteomics , concerns aspects of the secondary and tertiary structure , folding pathway , kinetics , comparison , function and regulation of all rna in a living organism . given recently discovered roles played by micro rna , small interfering rna , riboswitches , ribozymes , etc . , it is important to gain insight into the folding process of rna sequences . 
 we describe the web server rnaloss , which provides information about the distribution of locally optimal secondary structures , that possibly form kinetic traps in the folding process 
 . the tool rnaloss may be useful in designing rna sequences which not only have low folding energy , but whose distribution of locally optimal secondary structures would suggest rapid and robust folding . 
 website : . 
INTRODUCTION
METHODS
Definition
WEB SERVER
DISCUSSION
Figures and Tables