Multiple RNAAlignment

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, StemLoc, Evol Doer
  • Holmes &: Accelerated probabilistic inference of RNA structure evolution. BMC Bioinformatics 2005;6:73.
  • Holmes &: A probabilistic model for the evolution of RNA structure. BMC Bioinformatics 2004;5:166.
  • Holmes & Rubin: 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 &: The early introduction of dynamic programming into computational biology. Bioinformatics 2000;16:41-7.
• Benchmarks
  • Dowell & Eddy: Evaluation of several lightweight stochastic context-free grammars for RNA secondary structure prediction. BMC Bioinformatics 2004;5:71.
  • Gardner & Giegerich: A comprehensive comparison of comparative RNA structure prediction approaches. BMC Bioinformatics 2004;5:140.
  • Hickson et al.: The performance of several multiple-sequence alignment programs in relation to secondary-structure features for an rRNA sequence. Mol. Biol. Evol. 2000;17:530-9.
• Other recent approaches
  • Havgaard et al.: Pairwise local structural alignment of RNA sequences with sequence similarity less than 40%. Bioinformatics 2005;21:1815-24.
  • Mathews & Turner: Dynalign: an algorithm for finding the secondary structure common to two RNA sequences. J. Mol. Biol. 2002;317:191-203.
  • Yang & Blanchette: StructMiner: a tool for alignment and detection of conserved secondary structure. Genome Inform 2004;15:102-11.
  • Hofacker et al.: Alignment of RNA base pairing probability matrices. Bioinformatics 2004;20:2222-7.
  • Notredame et al.: RAGA: RNA sequence alignment by genetic algorithm. Nucleic Acids Res. 1997;25:4570-80.
• Detecting RNA structure in alignments
  • Washietl et al.: Fast and reliable prediction of noncoding RNAs. Proc. Natl. Acad. Sci. U.S.A. 2005;102:2454-9.
  • Coventry et al.: MSARI: multiple sequence alignments for statistical detection of RNA secondary structure. Proc. Natl. Acad. Sci. U.S.A. 2004;101:12102-7.
  • Juan & Wilson: RNA secondary structure prediction based on free energy and phylogenetic analysis. J. Mol. Biol. 1999;289:935-47.
• Pseudoknots, tree-adjoining grammars and similar formalisms
  • Rivas & Eddy: A dynamic programming algorithm for RNA structure prediction including pseudoknots. J. Mol. Biol. 1999;285:2053-68.
    • Rivas & Eddy: The language of RNA: a formal grammar that includes pseudoknots. Bioinformatics 2000;16:334-40.
    • Reeder & Giegerich: Design, implementation and evaluation of a practical pseudoknot folding algorithm based on thermodynamics. BMC Bioinformatics 2004;5:104.
  • Matsui et al.: Pair stochastic tree adjoining grammars for aligning and predicting pseudoknot RNA structures. Bioinformatics 2005;21:2611-7.
    • Sakakibara &: Grammatical inference in bioinformatics. IEEE Trans Pattern Anal Mach Intell 2005;27:1051-62.
    • Sakakibara &: Pair hidden Markov models on tree structures. Bioinformatics 2003;19 Suppl 1:i232-40.
  • Witwer C, Hofacker IL, Stadler, PF. [http: //doi.ieeecomputersociety.org/10.1109/TCBB.2004.22 Prediction of consensus RNA secondary structures including pseudoknots.] IEEE Trans Comp Biol Bioinf. 2004 1(2):66-76.

-- Ian Holmes - 23 Nov 2010