Alfredo Pulvirenti, University of Catania, Italy

Algorithms for RNA structure alignment
The discovery of functional non-coding RNAs (ncRNAs), has made essential the structural alignment of RNAs (pairwise and multiple). Many alignment methods for non-coding RNAs have been proposed. Pairwise alignment is mainly based on various approximations of the Sankoff algorithm, which have resulted in considerable improvement in the accuracy. On the other hand, although the importance of multiple structural alignment for multiple sequence RNA alignment has been widely recognized, the practical merit of structural alignment still remains unclear, as compared to traditional sequence-based methods. In this tutorial algorithms for pairwise and multiple sequence/structure alignment will be surveyed. The tutorial will highlights the key concepts, ideas and techniques behind the RNA alignment. Finally alignment accuracy assessment in connection with issues related to the scoring of ncRNA alignments will be discussed.

References:
Davydov E, Batzoglou S, 2006. A computational model for RNA multiple structural alignment. Theor. Comput. Sci. 368, 3 (Dec. 2006)

Bradley RK, Pachter L, Holmes I. 2008, Specific Alignment of Structured RNA: Stochastic Grammars and Sequence Annealing. Bioinformatics. 2008 Sep 16

Dowell RD, Eddy SR, 2006 Efficient pairwise RNA structure prediction and alignment using sequence alignment constraints BMC Bioinformatics 2006, 7:400.

Havgaard JH, Lyng RB, Stormo GD, Gorodkin J, 2005, Pairwise local structural alignment of RNA sequences with sequence similarity less than 40%, Bioinformatics Vol. 21 no. 9 2005

Sankoff D, 1985, Simultaneous Solution of the RNA Folding, Alignment, and Protosequence Problems. SIAM J Appl Math 1985,45:810-825.

Bauer M, Klau GW, Reinert K, 2007, Accurate multiple sequence-structure alignment of RNA sequences using combinatorial optimization BMC Bioinformatics 2007, 8:271

Tabei Y, Kiryu H, Kin T, Asai K, 2008, A fast structural multiple alignment method for long RNA Sequences BMC Bioinformatics 2008, 9:33

Dror O, Nussinov R, Wolfson H, 2005 ARTS: alignment of RNA tertiary structures, Bioinformatics Vol 21 suppl 2 2005

Gardner PP, Wilm A,Washiet S, 2005, A benchmark of multiple sequence alignment programs upon structural RNAs Nucleic Acids Research, 2005, Vol. 33, No. 8

Katoh K, Toh H, Improved accuracy of multiple ncRNA alignment by incorporating structural information into a MAFFT-based framework, BMC Bioinformatics 2008, 9:212

Siebert S, Backofen R, 2005, MARNA: multiple alignment and consensus structure prediction of RNAs based on sequence structure comparisons Bioinformatics, Vol. 21 no. 16 2005

Kiryu H, Tabei Y, Kin T, Asai K, 2007, Murlet: a practical multiple alignment tool for structural RNA sequences Bioinformatics Vol. 23 no. 13 2007

Wilm A, Higgins DG, Notredame C, 2008, R-Coffee: a method for multiple alignment of non-coding RNA Nucleic Acids Research, 2008, Vol. 36, No. 9

Xu X, Ji Y, Stormo GD, 2008, RNA Sampler: a new sampling based algorithm for common RNA secondary structure prediction and structural alignment Nucleic Acids Research, 2008, Vol. 36, Web Server issue

Höchsmann M, Voss B, Giegerich R, 2004, Pure Multiple RNA Secondary Structure Alignments: A Progressive Profile Approach, IEEE TCBB, VOL. 1, NO. 1, 2004