RNA-d2 is a user-friendly program developed for interactively generating aesthetic and non-overlapping drawings of RNA secondary structures. It designed so that the drawings can be edited in a very natural and intuitive way, in order to emphasize structural homologies between several molecules, as well as the foldings themselves to update the base-pair sets according to new data. The program automatically produces a polygonal display in which the unpaired nucleotides are regularly positioned on circles and the stems harmoniously distributed on their periphery. RNA secondary structures can be encoded via the keyboard, but the program also automatically draws output files from thermodynamic prediction programs. The user interacts directly on different screen displays according to the editing functions. Rotation/translation of any subdomain and deletion of stems are performed on a coloured backbone view to make easier the identification of structural features, whereas addition of new base-pairings and numbering manipulation are realized on a complete polygonal view. Each modification is displayed in real time on the screen. When the display is obscured by numerous overlaps despite the colour code of the backbone view, an automatic function progressively straightens the subdomains which are highly compacted by very dissymmetric internal loops. RNA-d2 allows easy untangling and editing of RNA molecules > 1000 nucleotides long.

We have developed an algorithm and a computer program for aligning new RNA sequences with a bank of aligned homologous RNA sequences. Given a common folding structure for the bank, the program performs an alignment between the bank and a new sequence, optimal both in terms of primary and secondary structure. This method is useful to align sequences that present a common folding structure despite extensive divergence of their primary structures. It allows these preserved regions to be precisely distinguished from domains with more variable secondary structure. An optimal alignment of a sequence of length N with a bank of homologous sequences of length M is produced in O (M2N3) time and O(M2N2) space. For sequences that are too long for an algorithm of this complexity, a proposed strategy is to use a classical alignment (using only primary structure data) then improve it with the new algorithm in the regions where the bank stems are not aligned with possible stems in the new sequence. The algorithm has been implemented in Turbo Pascal on a PC, and has been used to align RNA sequences of eubacterial large ribosomal subunit.

To access the functional informations carried by RNA molecules at the level of their secondary structure interactions, we propose a comparison method based on a tree edit algorithm which takes into account the tree structure of RNA foldings. Any secondary structure is translated into a tree involving all its elementary substructures; then a shorter condensed tree is built in which any unbranched helix interspersed with bulges and interior loops is taken as a single node. This method includes several parameters: a comparison matrix between structural units, gap penalties, and the scoring between nodes of the condensed trees. Their effects have been analysed using as a model a rapidly divergent domain of the large ribosomal RNA, for which structural variation during evolution is well known. This method allows one to recognize precisely, in large target molecules, definite substructures that present with the query molecules only a limited set of closely related secondary structure features; it is still efficient if intervening features, which can correspond to insertion/deletion of entire stem regions, separate such structural elements. When coupled with a hierarchical clustering algorithm, this method is suitable for classifying RNA molecules according to their secondary structure homologies.