An arc-annotated sequence is a sequence, over a given alphabet, with additional structure described by a set of arcs joining pairs of positions in the sequence. Arc-annotated sequences have been widely used and studied for the representation and the comparison of RNA structures.

In (Jiang et al. 2002) a general edit distance model dedicated to arc-annotated sequences was introduced to account for both classical sequences edit operations and structural edit operations on arcs. Later in (Blin et al. 2007) it was shown that under this model, the general edit distance problem was NP-hard. Next in (Blin-Touzet 2006, Blin et al. 2010), a hierarchy of arc-annotated sequence alignment problems that highlights less general, but tractable, problems was introduced.

In this presentation, a refinement of this hierarchy of alignment problems and an extention of the class of tractable alignment problems are presented. A multi-dimensional dynamic programming algorithm is proposed to solve the most general problem of the hierarchy known to be tractable in the general edit distance model.

The full functional role of RNA in all domains of life is yet to be explored. Deep sequencing technologies generate massive data about RNA transcripts with functional potential. To decipher this information, bioinformatics methods for structural analysis are in demand. We demonstrate how to improve current secondary structure prediction in different respects.

t.b.a.