Constrained RNA Structural Alignment: Algorithms and Application to Motif Detection in the Untranslated Regions of Trypanosoma brucei mRNAs

In this paper we propose a new method for aligning two RNA secondary structures by taking into account the presence of conserved RNA substructures, or constraints, in the alignment process. Our method allows the incorporation of specific knowledge about the RNA structures being analyzed while computing their alignment and thus is very useful for RNA motif detection. We develop statistical measures to assess the significance of alignment scores. Experimental results obtained by using the constrained alignment method to search for structural motifs in the untranslated regions of Trypanosoma brucei mRNAs demonstrate the good performance of the proposed method and its superiority over existing methods.