Stemloc

• Fold: RNA folding is the process by which an RNA molecule acquires secondary structure through intra-molecular interactions.
• Fold envelope: The set of candidate folds to be considered in the algorithm
• Alignment envelope: The set of candidate alignments to be considered in the algorithm

A previously developed algorithm by David Sankoff in 1985 uses dynamic programming to simultaneously align and predict multiple RNA structures. The Sankoff Algorithm takes time and space in big O notation ${\displaystyle O(L^{3N})}$ and ${\displaystyle O(L^{2N})}$respectively for ${\displaystyle N}$ sequences of length ${\displaystyle L}$. This is observantly expensive, and thus is the motivation to create better RNA analysis tools like Stemloc. The initial goal of Stemloc was to reduce the time and space cost of simultaneous alignment and structure prediction of two RNA sequences by using a stochastic context-free grammar (SCFG) scoring scheme and by implementing constrained versions of the Sankoff Algorithm.

Stemloc uses alignment envelopes and fold envelopes to simultaneously constrain both the alignment and the secondary structures of the sequences being compared. Fold envelopes can be used to "prune" the search over secondary structures and determine the subsequences of two RNA sequences that can be considered in the algorithm. For example, including or excluding specific nitrogen-bonded base pairings. Alignment envelopes can be used to "prune" the search over the alignments and determine possible "cutpoints" in the alignment of the two sequences. For example, including or excluding specific residue-level homologies. Fold envelopes are pre-calculated for each sequence individually, and alignment envelopes are pre-calculated by comparing the two sequences while ignoring secondary structures. Both global and local alignment is supported.

stemloc --local dynalign.trna

# STOCKHOLM 1.0
#=GR RD0260/26-67 SS ..<<<<<.......>>>>>.....(<<<<.......>>>>).
RD0260/26-67			UACUCCCCUGUCACGGGAGAGAAUGUGGGUUCAAAUCCCAUC
#=GC PS_cons			UAC..CCCUGUCACGG..G.GA..G.GGGUUC.AAUCCC..C
RD0500/26-66			UACGACCCUGUCACGGUCGUGA-CGCGGGUUCgAAUCCCGCC
#=GR RD0500/26-66 SS ..<<<<<.......>>>>>...-.<<<<<.......>>>>>.
#=GC SS_cons			..<<<<<.......>>>>>.....<<<<<.......>>>>>.
#=GF SC				  31.872
//

Stemloc relies heavily on stochastic context-free grammars, which can be seen as a scoring scheme for the algorithm. Because Sankoff's algorithm considers all possible folds and all possible alignments it is quite accurate and thorough, but it takes a measurable amount of time to obtain any results or output. To better this, Stemloc allows the user to constrain the total number of folds and alignments to be considered. More specifically, each sequence can be pre-folded individually in ${\displaystyle O(L^{3})}$ time and pre-aligned, ignoring secondary structure in ${\displaystyle O(L^{2})}$ time. For example, the using the "-fast" command below will only consider the 100 best RNA structures rather than analyzing all possible folds. Using the "-log DOTPLOT" command will output a visual representation of the fold and alignment envelopes.

stemloc nanos-tiny.rna -fast -log DOTPLOT

stemloc nanos-tiny.rna -nf -1 -na -1

Stemloc has since been used in a variety of research publications in RNA structure analysis. Most notably in the study of optimal multiple sequence alignment.

• Holmes I. (2005) Accelerated probabilistic inference of RNA structure evolution. BMC Bioinformatics. 2005 Mar 24;6:73.
• Sankoff D. (1985) Simultaneous Solution of the RNA Folding, Alignment and Protosequence Problems. SIAM Journal on Applied Mathematics. 1985 Oct;45:5.Sankoff D. (1985) Simultaneous Solution of the RNA Folding, Alignment and Protosequence Problems. SIAM Journal on Applied Mathematics. 1985 Oct;45:5.

• Stemloc homepage and tutorial