this stems from the groundbreaking discovery that rna is not solely a carrier of genetic information , but a key player in a wide range of essential processes within the cell , such as protein synthesis and transport , rna processing and splicing , gene silencing , and chromosome replication ( 13 ) .
rna is also involved in many pathological processes , like cancerous tumors and retroviral infections as aids .
much like proteins , understanding the functions of these active rna molecules requires methods for analyzing their tertiary structures .
however , in contrast to the wide range of 3d structure - based approaches available for proteins ( 4 ) , a similar field for rna is only now emerging .
many methods for structure analysis of rna have been developed to work at the secondary structure level , that is the level of base pairing ( 5 ) . in the absence of rna tertiary structures ,
such methods provide an excellent starting point for exploring rna structures . however , their inherent limitation is that they are incapable of predicting and annotating tertiary interactions .
these interactions are formed between secondary structure elements and are crucial for establishing the global fold of an rna ( 6,7 ) .
fortunately , in the past few years both the number and size of solved rna tertiary structures has dramatically increased .
a variety of methods are available for analyzing and classifying nucleotide conformations and spatial base interactions ( 813 ) .
several other methods have been suggested for measuring the similarity between larger rna structures , but require the structures to be with the same number of nucleotides and with a predefined correspondence between them ( 1416 ) .
fewer methods are available for locating small predefined motifs in larger structures ( 15,17 ) .
these methods are useful for finding new examples of known motifs , but are incapable of discovering novel ones .
to date , the problem of identifying a priori unknown common substructures is only partially addressed by a few methods for recognizing recurring 3d contiguous fragments ( 18,19 ) .
herein , we present a web server built around the arts method [ ( 20 ) ] for aligning 3d nucleic acid structures . compared with the current very few comparison tools available for tackling this task , arts is suitable for identifying a priori unknown common substructures that may not necessarily be contiguous .
the common substructures can be either large global folds containing hundreds and even thousands of nucleotides or small local spatial motifs with at least two successive base pairs .
arts is also highly efficient requiring typically a few seconds for comparing a pair of average - size rna structures with hundreds of nucleotides .
the tool has been used to conduct an all - against - all comparison of all the rna 3d structures currently available in the protein data bank ( pdb ) ( 21 ) .
the input is a pair of nucleic acid structures represented by the 3d coordinates of their atoms .
the phosphate atoms are singled out as critical points and each structure is represented as a set of points in 3d space , where each point is the position of a phosphate atom . using this representation
the problem is a version of the largest common point set ( lcp ) problem in computational geometry .
namely , the task is to find a rigid transformation ( rotation and translation ) that superimposes the largest number of phosphate atoms of one structure onto the phosphate atoms of the other one within a predefined bottleneck matching distance ( 22 ) error .
although this problem has been studied extensively , the current known exact and approximate algorithms for solving it are impractical , since they require o(n ) and o(n ) time , respectively , where n is the number of phosphate atoms ( 22,23 ) .
arts [ ( 20 ) ] is thus a heuristic method . by exploiting the base pairing and stacking properties of nucleic acids , it is capable of providing biologically relevant solutions in practical running times , even for large compact structures with thousands of nucleotides like the ribosome .
the goal is to maximize both the number of superimposed phosphate atoms and the number of superimposed base pairs .
the rationale is that more than half of the nucleotides in an average non - coding rna are involved in base pairing and the stems that they form are evolutionarily more conserved than loops ( 7 ) .
it is thus unlikely that an alignment with a large number of superimposed base pairs will be biologically meaningless , as might happen when solving the pure geometric lcp problem . in the first stage ,
all the possible local alignments of two successive base pairs between the structures are constructed .
then , a greedy approach is used to extend the local alignments so that a maximal number of phosphate atoms and base pairs will be superimposed .
finally , the global alignments are scored , clustered and ranked , and the highest scoring ones are reported .
we estimate the significance of the obtained alignments by computing the p - value of their score with respect to a random dataset  of pairwise alignments . in the current version of the application
 contains 245  000 alignments that have been randomly chosen from an all - against - all comparison of all the rna structures in the pdb .
the p - value of an alignment between a pair of rna structures with n and m nucleotides is computed with respect to all alignments in  for which the number of nucleotides in the smallest structure is 20% min(n , m ) .
the resulting p - value of the alignment represents the probability that a pairwise alignment for which the size of the smallest structure is similar would receive a higher or equal score by chance .
the arts web server as well as an accompanied software package are freely available at .
it requires the user to enter an email address and a pair of nucleic acid structures in pdb format ( 21 ) .
the structures can be either uploaded to the server or retrieved from the pdb . in the second case the user has to enter a four - character pdb code , optionally followed by a colon and a list of chain ids , for instance  1u6b ,  1u6b : b and  1u6b : bc. in both cases , the structures must contain all atoms and not only the ones on the backbone .
the reason is that otherwise hydrogen bonds can not be computed and these are necessary for finding base pairs .
( a ) the entrance page of the web server . the user is required to enter an email address and a pair of nucleic acid structures in pdb format ( 21 ) .
the structures can be either uploaded to the server or retrieved from the pdb . in the second case the user has to enter a four - character pdb code , optionally followed by a colon and a list of chain ids .
( b ) a web page with a summary of the 10 top - ranking alignments obtained for  1u6b : b and  1y0q pdb codes . ( c )
the page obtained after clicking on the  bp core size field of the top - ranking alignment in the summary page presented in ( b ) .
( d ) the superimposition of the input structures displayed by pymol ( 26 ) after clicking on the  pdb alignment field of the top - ranking alignment in the summary page presented in ( b ) .
the backbone of the two structures , pdb:1u6bb and pdb:1y0q , is depicted in red and blue , respectively .
the matched base pairs are in green and the matched unpaired nucleotides are in yellow . a typical run of arts for comparing a pair of average - size nucleic acid structures with hundreds of nucleotides takes a few seconds . after the run completes , a web page with a summary of the obtained alignments
in addition , an email with a link to this web page is sent to the user .
figure 1b displays a summary page obtained for two self - splicing group i introns , the azoarcus pre - trna intron with both exons [ pdb1u6b : b ( 24 ) ] and the twort ribozyme intron [ pdb1y0q ( 25 ) ] .
the upper table shows the name of the compared structures and the number of nucleotides and base pairs in each structure .
the bottom table shows the 10 top - ranking alignments sorted in descending order by their score . besides the score
, the following data are presented for each alignment : ( i ) the number of matched base pairs ( bp core size ) ; ( ii ) the total number of matched nucleotides including unpaired ones ( core size ) ; ( iii ) the root mean square deviation ( rmsd ) between the phosphate atoms of the matched nucleotides in the core ;
( iv ) the p - value ; and ( v ) a pdb file with the aligned structures . clicking on the  bp core size field of one of the alignments displays a new page with a table of the matched base pairs .
figure 1c shows the page obtained after clicking on the  bp core size field of the top - ranking alignment in the summary page presented in figure 1b .
each line corresponds to a match between 2 base - pairs , and each entry provides the chain identifier , base type and residue number of the 2 nucleotides in the corresponding base pair .
clicking on the  core size field of one of the alignments in the summary page ( figure 1b ) displays a similar page with a table of all matched nucleotides ( paired and unpaired ) .
a pdb file with the input structures superimposed one onto another will be downloaded or presented by a viewer ( if configured ) when clicking on the  pdb alignment field of one of the alignments in the summary page .
figure 1d shows the superimposition of the input structures displayed by the pymol viewer [ ( 26 ) ] after clicking on the  pdb alignment field of the top - ranking alignment in the summary page presented in figure 1b .
are pymol [ ( 26 ) ] and rasmol ( 27 ) scripts for displaying the alignments and selecting the matched base pairs ( bpcore ) and all matched nucleotides including unpaired ones ( core ) .
it requires the user to enter an email address and a pair of nucleic acid structures in pdb format ( 21 ) .
the structures can be either uploaded to the server or retrieved from the pdb . in the second case the user has to enter a four - character pdb code , optionally followed by a colon and a list of chain ids , for instance  1u6b , 
1u6b : b and  1u6b : bc. in both cases , the structures must contain all atoms and not only the ones on the backbone .
the reason is that otherwise hydrogen bonds can not be computed and these are necessary for finding base pairs .
( a ) the entrance page of the web server . the user is required to enter an email address and a pair of nucleic acid structures in pdb format ( 21 ) .
the structures can be either uploaded to the server or retrieved from the pdb . in the second case the user has to enter a four - character pdb code , optionally followed by a colon and a list of chain ids .
( b ) a web page with a summary of the 10 top - ranking alignments obtained for  1u6b : b and  1y0q pdb codes .
( c ) the page obtained after clicking on the  bp core size field of the top - ranking alignment in the summary page presented in ( b ) .
( d ) the superimposition of the input structures displayed by pymol ( 26 ) after clicking on the  pdb alignment field of the top - ranking alignment in the summary page presented in ( b ) .
the backbone of the two structures , pdb:1u6bb and pdb:1y0q , is depicted in red and blue , respectively .
the matched base pairs are in green and the matched unpaired nucleotides are in yellow .
a typical run of arts for comparing a pair of average - size nucleic acid structures with hundreds of nucleotides takes a few seconds . after the run completes
in addition , an email with a link to this web page is sent to the user .
figure 1b displays a summary page obtained for two self - splicing group i introns , the azoarcus pre - trna intron with both exons [ pdb1u6b : b ( 24 ) ] and the twort ribozyme intron [ pdb1y0q ( 25 ) ] .
the upper table shows the name of the compared structures and the number of nucleotides and base pairs in each structure .
the bottom table shows the 10 top - ranking alignments sorted in descending order by their score . besides the score
, the following data are presented for each alignment : ( i ) the number of matched base pairs ( bp core size ) ; ( ii ) the total number of matched nucleotides including unpaired ones ( core size ) ; ( iii ) the root mean square deviation ( rmsd ) between the phosphate atoms of the matched nucleotides in the core ;
( iv ) the p - value ; and ( v ) a pdb file with the aligned structures . clicking on the  bp core size field of one of the alignments displays a new page with a table of the matched base pairs .
figure 1c shows the page obtained after clicking on the  bp core size field of the top - ranking alignment in the summary page presented in figure 1b .
each line corresponds to a match between 2 base - pairs , and each entry provides the chain identifier , base type and residue number of the 2 nucleotides in the corresponding base pair .
clicking on the  core size field of one of the alignments in the summary page ( figure 1b ) displays a similar page with a table of all matched nucleotides ( paired and unpaired ) .
a pdb file with the input structures superimposed one onto another will be downloaded or presented by a viewer ( if configured ) when clicking on the  pdb alignment field of one of the alignments in the summary page .
figure 1d shows the superimposition of the input structures displayed by the pymol viewer [ ( 26 ) ] after clicking on the  pdb alignment field of the top - ranking alignment in the summary page presented in figure 1b .
are pymol [ ( 26 ) ] and rasmol ( 27 ) scripts for displaying the alignments and selecting the matched base pairs ( bpcore ) and all matched nucleotides including unpaired ones ( core ) .
we have presented a freely available web server accompanied by a software package for 3d structural alignment of nucleic acids .
the web server receives as input a pair of tertiary structures of nucleic acids in pdb format , and searches for a priori unknown common substructures that are not necessarily contiguous .
the output consists of the top - ranking superpositions between the two input structures in pdb format and corresponding lists of matched nucleotides in the common substructures . to the best of our knowledge ,
this is the first web server that performs rna structural comparisons that are truly 3d and irrespective of the order of the nucleotides on the chain .
the only requirement is that there are at least two consecutive base pairs in the match .
the algorithm behind the web server is highly efficient , where a typical comparison of two nucleic acids takes a few seconds on a standard pc .
an all - against - all comparison of all the rna structures currently available in the pdb has been carried out and the results can be accessed via the web server . in future work we intend to allow online searches of uploaded structures against the entire pdb .
 rna molecules with common structural features may share similar functional properties . 
 structural comparison of rnas and detection of common substructures is , thus , a highly important task . 
 nevertheless , the current available tools in the rna community provide only a partial solution , since they either work at the 2d level or are suitable for detecting predefined or local contiguous tertiary motifs only . here 
 , we describe a web server built around arts , a method for aligning tertiary structures of nucleic acids ( both rna and dna ) . 
 arts receives a pair of 3d nucleic acid structures and searches for a priori unknown common substructures . 
 the search is truly 3d and irrespective of the order of the nucleotides on the chain . 
 the identified common substructures can be large global folds with hundreds and even thousands of nucleotides as well as small local motifs with at least two successive base pairs . 
 the method is highly efficient and has been used to conduct an all - against - all comparison of all the rna structures in the protein data bank . the web server together with a software package for download are freely accessible at . 
INTRODUCTION
METHOD OUTLINE
WEB SERVER
Input
Output
CONCLUSIONS