R3D Align: global pairwise alignment of RNA 3D structures using local superpositions

Abstract

Motivation: Comparing 3D structures of homologous RNA molecules yields information about sequence and structural variability. To compare large RNA 3D structures, accurate automatic comparison tools are needed. In this article, we introduce a new algorithm and web server to align large homologous RNA structures nucleotide by nucleotide using local superpositions that accommodate the flexibility of RNA molecules. Local alignments are merged to form a global alignment by employing a maximum clique algorithm on a specially defined graph that we call the 'local alignment' graph.

Results: The algorithm is implemented in a program suite and web server called 'R3D Align'. The R3D Align alignment of homologous 3D structures of 5S, 16S and 23S rRNA was compared to a high-quality hand alignment. A full comparison of the 16S alignment with the other state-of-the-art methods is also provided. The R3D Align program suite includes new diagnostic tools for the structural evaluation of RNA alignments. The R3D Align alignments were compared to those produced by other programs and were found to be the most accurate, in comparison with a high quality hand-crafted alignment and in conjunction with a series of other diagnostics presented. The number of aligned base pairs as well as measures of geometric similarity are used to evaluate the accuracy of the alignments.

Availability: R3D Align is freely available through a web server http://rna.bgsu.edu/R3DAlign. The MATLAB source code of the program suite is also freely available for download at that location.

Fig. 1.

Illustration of compatibility of alignments. Each vertex represents a four-nucleotide alignment, as in Alignment 1, Alignment 2 and Alignment 3 above. An alignment formed by merging Alignments 1 and 3 is neither a uniquely assigned nor a well-ordered alignment, while the merging of Alignments 2 and 3 violates the uniquely assigned criterion. Only alignments 1 and 2 can be merged to form a valid alignment, namely the aligning of nucleotides 1, 2, 3, 4, 5, 6, 7, 8 in the first structure with nucleotides1, 2, 3, 4, 7, 8, 9, 10 in the second structure, respectively.

Fig. 2.

A portion of the R3D Align alignment of T.th. and E.c 16S rRNA. The spreadsheet simultaneously displays aligned nucleotides and base-pairing interactions. Nucleotides in Columns 1 and 4 of the same row are aligned, as are the nucleotides in Columns 3 and 6. The kind of base-pairing interaction between the nucleotides of Columns 1 and 3 (if any) is indicated in Column 2. Column 5 indicates the base-pairing interaction between the nucleotides in Columns 4 and 6. Base pairs are annotated by FR3D using the Leontis/Westhof system. All corresponding base pair types are identical except the last row shows a near tSW base pair in E.coli Note that nucleotides U1302 in T.th. and C1302 in E.coli are not aligned to one another. This portion of the alignment indicates strong conservation between the two structures as well as proper alignment.

Fig. 3.

A section of the comparison the 16S rRNA alignment produced by different methods. To the left of the black line are nucleotides and base pairs of T.th. To the right of the black line are the corresponding nucleotides of E.coli as aligned by the different methods. R3D Align is the first method displayed to the right of the black line, followed by the manually derived base pair alignment, three other 3D-to-3D alignments, and then two sequence-based alignments.

Fig. 4.

16s rRNA alignments produced by the different methods with the nucleotides of T.th. (1j5e) listed along the top of each bar and the nucleotides of E.coli (2avy) listed along the bottom. For each nucleotide in 1j5e with a correspondence, it and the nearest 4 nt in 1j5e with a correspondence are superimposed with the corresponding 5 nt of 2avy and the line is colored according to the geometric discrepancy, as indicated by the color bar.