The complexity of pairwise RNA structure alignment
depends on the structural restrictions assumed for
both the input structures and the computed consensus
structure. For arbitrarily crossing input and
consensus structures, the problem is NP-hard. For
non-crossing consensus structures, Jiang et al's
algorithm [1] computes the alignment in O(n^2 m^2 ) time
where n and m denote the lengths of the two input
sequences. If also the input structures are
non-crossing, the problem n corresponds to tree
editing which can be solved in O(m^2 n(1 + log n/m ))
time [2]. We present a new algorithm that solves the
problem for dcrossing structures in O(dm^2 n log n)
time, where d is a parameter that is one for
non-crossing structures, bounded by n for crossing
structures, and much smaller than n on most practical
examples. Crossing input structures allow for
applications where the input is not a fixed structure
but is given as base-pair probability
matrices.
Keywords : RNA, sequence structure alignment, simultaneous alignment and folding