  We describe an algorithm for comparing two RNA secondary structures coded in
the form of trees that introduces two new operations, called node fusion and
edge fusion, besides the tree edit operations of deletion, insertion, and
relabeling classically used in the literature. This allows us to address some
serious limitations of the more traditional tree edit operations when the trees
represent RNAs and what is searched for is a common structural core of two
RNAs. Although the algorithm complexity has an exponential term, this term
depends only on the number of successive fusions that may be applied to a same
node, not on the total number of fusions. The algorithm remains therefore
efficient in practice and is used for illustrative purposes on ribosomal as
well as on other types of RNAs.
