Alignment of RNA Secondary Structures with Arbitrary Pseudoknots using Structural Sequences

Abstract Background. RNA secondary structure comparison is important for RNA classification, RNA structure prediction and for the study of evolution. Comparison can be done efficiently only for pseudoknot-free structures, while alignment of pseudoknots is more computationally challenging. Results. In this work, we start from the already introduced idea of representing RNA secondary structures with arbitrary pseudoknots using structural trees and introduce an alternative representation using sequences of integers. Each structure is associated with a unique structural sequence by identifying the way in which arcs interact in the arc diagram of the structure. Using a variant of classical edit distance, we define a new measure of dissimilarity called SERNA distance between abstractions of RNA secondary structures in which sequence is neglected and unpaired nucleotides are collapsed together to form a context.SERNA distance is then shown to be a metric, and the SERNAlign tool, based on dynamic programming, is introduced to calculate the distance and align structural sequences. SERNAling is shown to be more efficient than the tool using the structural tree approach. The level of abstraction of structural sequences is also more precise than the one of structural trees. Finally, we apply SERNA distance and agglomerative clustering to reconstruct the phylogeny of a dataset of ribosomal RNAs. We show that the performance of the reconstruction is similar to that obtained using the distance based on structural trees. Conclusions. Structural sequences and the associated SERNA distance allow one to compare the secondary structures of the RNA with arbitrary pseudo-knots efficiently (O(n²)). From a biological point of view, the distance reflects in a good way the phylogenetic classification of a curated taxonomy. The results on taxa reconstruction are similar to (or better than) the ones obtained using other tools in the literature that are able to compare pseudoknotted structures.