stem loc

• stem loc
  • Related programs
  • Multiple alignment modes
  • Tutorials
  • Download
  • References

stemloc is a program for multiple alignment of RNA using Stochastic Context Free Grammars.

Stemloc uses "alignment envelopes" and "fold envelopes" to simultaneously constrain both the alignment and the secondary structures of the sequences being compared, rendering the RNA comparison problem tractable on commodity hardware.

Related programs

• EvolDeeds for our software for statistical alignment and reconstruction of ancient structured RNA.
• Stemloc-AMA --- stemloc's new sequence annealing mode. The best RNA alignment tool of 2008!

Multiple alignment modes

The first step performed by stemloc is always an "all vs all" pairwise alignment. This uses a constrained version of Sankoff's algorithm for pair SCFGs.

The next step depends on the mode:

• Sequence annealing, implemented as StemLoc AMA, is the primary mode

• ProgressiveMode is an alternative, single-linkage clustering mode for multiple alignment. Unlike sequence annealing mode, progressive mode tries to give a good consensus alignment and structure, but the resultant alignment is consequently not as good. Progressive mode has the following sub-modes...
  • GlobalMode (aligns entire sequences) vs LocalMode (aligns highest-scoring subsequences)
  • ConservativeMode (does not extend initial pairwise seed) vs LiberalMode (attempts to extend pairwise seed where possible)

Tutorials

• stemloc tutorial

Download

Stem Loc may be built from source by downloading and compiling DART. See DownloadingDart and Building Dart.

References

Stemloc:

• Bradley RK, Pachter L, Holmes I.  Specific Alignment of Structured RNA: Stochastic Grammars and Sequence Annealing.  Bioinformatics. 2008 Sep 16.
• Holmes I.  Accelerated probabilistic inference of RNA structure evolution.  BMC Bioinformatics. 2005 Mar 24;6:73.

Alignment envelopes:

• Holmes, I. PhD thesis. Dept of Genetics, University of Cambridge; Wellcome Trust Sanger Institute. 1998. (pdf) (ps.gz)

Fold envelopes:

• Holmes I, Rubin GM.  Pairwise RNA structure comparison with stochastic context-free grammars.  Pac Symp Biocomput. 2002;:163-74. (pdf)