Pure multiple RNA secondary structure alignments: a progressive profile approach

In functional, noncoding RNA, structure is often essential to function. While the full 3D structure is very difficult to determine, the 2D structure of an RNA molecule gives good clues to its 3D structure, and for molecules of moderate length, it can be predicted with good reliability. Structure comparison is, in analogy to sequence comparison, the essential technique to infer related function. We provide a method for computing multiple alignments of RNA secondary structures under the tree alignment model, which is suitable to cluster RNA molecules purely on the structural level, i.e., sequence similarity is not required. We give a systematic generalization of the profile alignment method from strings to trees and forests. We introduce a tree profile representation of RNA secondary structure alignments which allows reasonable scoring in structure comparison. Besides the technical aspects, an RNA profile is a useful data structure to represent multiple structures of RNA sequences. Moreover, we propose a visualization of RNA consensus structures that is enriched by the full sequence information.

1. Introduction

The investigation of RNA secondary structures is a challenging task in molecular biology. RNA molecules have a variety of functions in the cell, which often depend on structural properties. A similar structure often implies a similar function, the converse conclusion is weaker. If there is a certain amount of conservation on the sequence level, a multiple sequence alignment of RNAs, having a similar function, can elucidate conserved structural regions among these sequences. However, functional RNA families such as tRNA, rRNA, and RNAse P RNA exhibit a highly conserved secondary structure but little sequence similarity. Therefore, it is of general interest to compare RNA secondary structures directly, i.e., without relying on sequence similarity [1], [2], [3]. These approaches are limited to a pairwise comparison. Stemtrace [4] is an interactive visualization tool for comparative RNA structure analysis. However, it requires manual intervention. An early approach for multiple structure comparison based on sequence alignments is provided in [5]. A multiple structure alignment strategy which builds upon pairwise structure alignment and multiple sequence alignment is implemented in the tool MARNA [6]. It calculates pairwise similarities of RNA structures, based on the algorithm in [3], which in turn are used to weight edges in the multiple sequence alignment tool T-Coffee [7]. As T-Coffee computes a sequence alignment, this step inherits the problem of pairwise sequence alignments of RNA structures. That is: A base-pair is not treated as a unit.