Multiple alignment of RNA sequences and structures

• Problem: identify shared motifs (potentially cis regulatory) in RNA sequences
  • Zip Codes, Ribo Switches, Splicing Signals^?, Viral Packaging Signals^? ...
  • viruses, eukaryotes, bacteria
• Holmes Lab approaches: Stemloc-AMA, Stem Loc, Evol Doer
  • Holmes I.  Accelerated probabilistic inference of RNA structure evolution.  BMC Bioinformatics. 2005 Mar 24;6:73.
  • Holmes I.  A probabilistic model for the evolution of RNA structure.  BMC Bioinformatics. 2004 Oct 26;5:166.
  • Holmes I, Rubin GM.  Pairwise RNA structure comparison with stochastic context-free grammars.  Pac Symp Biocomput. 2002;:163-74.
• Phylo Grammars (NB these are mainly used to annotate existing alignments, but can be used in likelihood functions for alignment sampling)
  • Knudsen Hein algorithm
  • Xgram Software
• Early dynamic programming solutions
  • Sankoff D.  The early introduction of dynamic programming into computational biology.  Bioinformatics. 2000 Jan;16(1):41-7.
• Benchmarks
  • Dowell RD, Eddy SR.  Evaluation of several lightweight stochastic context-free grammars for RNA secondary structure prediction.  BMC Bioinformatics. 2004 Jun 4;5:71.
  • Gardner PP, Giegerich R.  A comprehensive comparison of comparative RNA structure prediction approaches.  BMC Bioinformatics. 2004 Sep 30;5:140.
  • Hickson RE, Simon C, Perrey SW.  The performance of several multiple-sequence alignment programs in relation to secondary-structure features for an rRNA sequence.  Mol Biol Evol. 2000 Apr;17(4):530-9.
• Other recent approaches
  • Havgaard JH, Lyngso RB, Stormo GD, Gorodkin J.  Pairwise local structural alignment of RNA sequences with sequence similarity less than 40%.  Bioinformatics. 2005 May 1;21(9):1815-24. Epub 2005 Jan 18.
  • Mathews DH, Turner DH.  Dynalign: an algorithm for finding the secondary structure common to two RNA sequences.  J Mol Biol. 2002 Mar 22;317(2):191-203.
  • Yang Q, Blanchette M.  StructMiner: a tool for alignment and detection of conserved secondary structure.  Genome Inform. 2004;15(2):102-11.
  • Hofacker IL, Bernhart SH, Stadler PF.  Alignment of RNA base pairing probability matrices.  Bioinformatics. 2004 Sep 22;20(14):2222-7. Epub 2004 Apr 8.
  • Notredame C, O'Brien EA, Higgins DG.  RAGA: RNA sequence alignment by genetic algorithm.  Nucleic Acids Res. 1997 Nov 15;25(22):4570-80.
• Detecting RNA structure in alignments
  • Washietl S, Hofacker IL, Stadler PF.  Fast and reliable prediction of noncoding RNAs.  Proc Natl Acad Sci U S A. 2005 Feb 15;102(7):2454-9. Epub 2005 Jan 21.
  • Coventry A, Kleitman DJ, Berger B.  MSARI: multiple sequence alignments for statistical detection of RNA secondary structure.  Proc Natl Acad Sci U S A. 2004 Aug 17;101(33):12102-7. Epub 2004 Aug 10.
  • Juan V, Wilson C.  RNA secondary structure prediction based on free energy and phylogenetic analysis.  J Mol Biol. 1999 Jun 18;289(4):935-47.
• Pseudoknots, tree-adjoining grammars and similar formalisms
  • Rivas E, Eddy SR.  A dynamic programming algorithm for RNA structure prediction including pseudoknots.  J Mol Biol. 1999 Feb 5;285(5):2053-68.
    • Rivas E, Eddy SR.  The language of RNA: a formal grammar that includes pseudoknots.  Bioinformatics. 2000 Apr;16(4):334-40.
    • Reeder J, Giegerich R.  Design, implementation and evaluation of a practical pseudoknot folding algorithm based on thermodynamics.  BMC Bioinformatics. 2004 Aug 4;5:104.
  • Matsui H, Sato K, Sakakibara Y.  Pair stochastic tree adjoining grammars for aligning and predicting pseudoknot RNA structures.  Bioinformatics. 2005 Jun 1;21(11):2611-7. Epub 2005 Mar 22.
    • Sakakibara Y.  Grammatical inference in bioinformatics.  IEEE Trans Pattern Anal Mach Intell. 2005 Jul;27(7):1051-62.
    • Sakakibara Y.  Pair hidden Markov models on tree structures.  Bioinformatics. 2003;19 Suppl 1:i232-40.
  • Witwer C, Hofacker IL, Stadler, PF. Prediction of consensus RNA secondary structures including pseudoknots. IEEE Trans Comp Biol Bioinf. 2004 1(2):66-76.