Finding the most significant common sequence and structure motifs in a set of RNA sequences

We present a computational scheme to locally align a collection of RNA sequences using sequence and structure constraints. In addition, the method searches for the resulting alignments with the most significant common motifs, among all possible collec-tions. The first part utilizes a simplified version of the Sankoff algorithm for simultaneous folding and align-ment of RNA sequences, but maintains tractability by constructing multi-sequence alignments from pair-wise comparisons. The algorithm finds the multiple alignments using a greedy approach and has simila-rities to both CLUSTAL and CONSENSUS, but the core algorithm assures that the pairwise alignments are optimized for both sequence and structure conserva-tion. The choice of scoring system and the method of progressively constructing the final solution are im-portant considerations that are discussed. Example solutions, and comparisons with other approaches, are provided. The solutions include finding consensus structures identical to published ones