Alignment of RNA secondary structures with arbitrary pseudoknots using structural sequences

Abstract Background Comparison of RNA secondary structures is fundamental for RNA classification, motif analysis, and evolutionary studies. While efficient methods exist for pseudoknot-free structures, the comparison of RNA secondary structures with arbitrary pseudoknots remains computationally challenging. The aim of this study is to introduce a novel sequence-based representation and an associated alignment distance for efficiently comparing RNA secondary structures with arbitrary pseudoknots. Results We introduce a novel representation of RNA secondary structures with arbitrary pseudoknots based on integer sequences, called structural sequences. On this representation, we define the SERNA distance, an extension of the classical edit distance with structural correctness constraints, and prove that it is a metric. We present SERNAlign, an open-source tool that computes the SERNA distance using dynamic programming with quadratic time complexity. To evaluate the proposed distance, we conduct two complementary experiments within a clustering-based evaluation framework: classification of experimentally validated pseudoknot motifs, which directly targets the design goal of SERNA, and phylogenetic clustering of ribosomal RNAs as a robustness check against existing structural distances. Across both tasks, SERNA demonstrates competitive clustering performance with respect to state-of-the-art comparison methods, while providing improved discrimination in complex motif settings and significantly lower computational cost compared to structure-based approaches.