As one of the earliest problems in computational biology, RNA secondary structure prediction
(sometimes referred to as "RNA folding") problem has attracted attention again,
thanks to the recent discoveries of many novel non-coding RNA molecules. The two common
approaches to this problem are de novo prediction of RNA secondary structure based
on energy minimization and the consensus folding approach (computing the common secondary
structure for a set of unaligned RNA sequences). Consensus folding algorithms work
well when the correct seed alignment is part of the input to the problem. However, seed
alignment itself is a challenging problem for diverged RNA families. In this paper, we propose
a novel framework to predict the common secondary structure for unaligned RNA
sequences. By matching putative stacks in RNA sequences, we make use of both primary
sequence information and thermodynamic stability for prediction at the same time. We show
that our method can predict the correct common RNA secondary structures even when we
are given only a limited number of unaligned RNA sequences, and it outperforms current
algorithms in sensitivity and accuracy.
