An algebraic language for RNA pseudoknots comparison

Abstract

Background: RNA secondary structure comparison is a fundamental task for several studies, among which are RNA structure prediction and evolution. The comparison can currently be done efficiently only for pseudoknot-free structures due to their inherent tree representation.

Results: In this work, we introduce an algebraic language to represent RNA secondary structures with arbitrary pseudoknots. Each structure is associated with a unique algebraic RNA tree that is derived from a tree grammar having concatenation, nesting and crossing as operators. From an algebraic RNA tree, an abstraction is defined in which the primary structure is neglected. The resulting structural RNA tree allows us to define a new measure of similarity calculated exploiting classical tree alignment.

Conclusions: The tree grammar with its operators permit to uniquely represent any RNA secondary structure as a tree. Structural RNA trees allow us to perform comparison of RNA secondary structures with arbitrary pseudoknots without taking into account the primary structure.

Keywords: ASPRA distance; Algebraic RNA tree; Structural RNA tree; Tree alignment; Tree grammar.

Fig. 1

Basic structural elements of RNA secondary structures: a, hairpin; b, internal loop; c, bulge; d, helix and e, multi-loop. A strong interaction is depicted with a line, a weak interaction is drawn with a zigzagged line and several consecutive strong interactions are represented by a dashed line

Fig. 2

An RNA secondary structure. Each nucleotide is represented by a ball, a strong interaction is depicted by a line and a weak interaction by a zigzagged line. a, pseudoknot-free; b, a pseudoknot, which makes the whole structure pseudoknotted

Fig. 3

The secondary structure of Fig. 2. In a, the zigzagged arcs do not cross while, in b, pseudoknots are clearly visible as crossings of arcs

Fig. 4

a, concatenation b, nesting and c, crossing of two hairpins

Fig. 5

a, an hairpin and b, the nesting of two hairpins

Fig. 6

a, concatenation of two hairpins nested into two nested hairpins. b, pseudoknot created by adding a new weak interaction between an unpaired nucleotide of the structure a and one belonging to the tail

Fig. 7

Two examples of pseudoloops. a, characterised by the crossing of two hairpins; b, characterised by the crossing of three hairpins

Fig. 8

Two examples of pseudoloops without crossings. a, a hairpin; b, a concatenation of two hairpins

Fig. 9

Not admitted RNA structure

Fig. 10

a, first and b, second step of the procedure for building the derived tree of the structure in Fig. 6b

Fig. 11

a, third and b, fourth step of the procedure for building the derived tree of the structure in Fig. 6b

Fig. 12

Algebraic RNA tree of the structure in Fig. 6b according to the regular tree grammar ${\mathcal{G}}_{\text{RNA}}$

Fig. 13

The structural RNA tree corresponding to the algebraic RNA tree in Fig. 12

Fig. 14

Two different RNA secondary structures having the same pattern of application of the crossing operator. In a, the rightmost weak interaction crosses only with one of the other two. In b, the rightmost weak interaction crosses with both the other two

Fig. 15

On the left, the structural RNA tree of the structure shown in Fig. 14a. On the right, the structural RNA tree of the structure shown in Fig. 14b

Fig. 16

Alignment of the structural RNA trees of Fig. 15

Fig. 17

An RNA secondary structure to be compared with the one in Fig. 6b

Fig. 18

The structural RNA tree of the structure in Fig. 17

Fig. 19

One of the optimal alignments of the structural RNA trees in Figs. 13 and 18