Motivation Many

functional classes of RNA molecules exhibit a highly conserved secondary structure but little sequence homology. Reliable alignments thus have to take structural information into account. Sankoff’s algorithm [5] that simultaneously allows the solution of the structure prediction and alignment problem is computationally expensive, O(n6) in CPU time and O(n4) in memory. Currently available software packages, e.g. FOLDALIGN [2] or dynalign [3], thus implement only restricted versions. Instead of trying to solve the alignment and the structure prediction problem simultaneously, one can start from base pairing probability matrices predicted by McCaskill’s algorithm [4]. The problem then is the alignment of these matrices. This is known to be NPcomplete in the general case, but for RNA structure alignments the threading problem remains tractable if the alignment is scored based on the notion of a common secondary structure