  Alignment of structural RNAs is an important problem with a wide range of
applications. Since function is often determined by molecular structure, RNA
alignment programs should take into account both sequence and base-pairing
information for structural homology identi^Lcation. A number of successful
alignment programs are heuristic versions of Sanko^K's optimal algorithm. Most
of them require O(n4) run time. This paper describes C++ software,
RNAmountAlign, for RNA sequence/structure alignment that runs in O(n3) time and
O(n2) space; moreover, our software returns a p-value (transformable to expect
value E) based on Karlin-Altschul statistics for local alignment, as well as
parameter ^Ltting for local and global alignment. Using incremental mountain
height, a representation of structural information computable in cubic time,
RNAmountAlign implements quadratic time pairwise local, global and
global/semiglobal (query search) alignment using a weighted combination of
sequence and structural similarity. RNAmountAlign is capable of performing
progressive multiple alignment as well. Benchmarking of RNAmountAlign against
LocARNA, LARA, FOLDALIGN, DYNALIGN and STRAL shows that RNAmountAlign has
reasonably good accuracy and much faster run time supporting all alignment
types.
