Stem Loc
From Biowiki
Contents
stem loc
[stem loc 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
- Evol Deeds for our software for statistical alignment and reconstruction of ancient structured RNA.
- Stemloc-AMA --- stemloc's sequence annealing mode
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
- Progressive Mode 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...
- Global Mode (aligns entire sequences) vs Local Mode (aligns highest-scoring subsequences)
- Conservative Mode (does not extend initial pairwise seed) vs Liberal Mode (attempts to extend pairwise seed where possible)
Tutorials
Download
Stem Loc may be built from source by downloading and compiling DART. See Downloading Dart and Building Dart.
References
Stemloc:
- Bradley et al.: Specific alignment of structured RNA: stochastic grammars and sequence annealing. Bioinformatics 2008;24:2677-83.
- Holmes &: Accelerated probabilistic inference of RNA structure evolution. BMC Bioinformatics 2005;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 & Rubin: Pairwise RNA structure comparison with stochastic context-free grammars. Pac Symp Biocomput 2002;:163-74. (pdf)
