## 6 ICOREs for RNA Secondary Structure Analysis
### Sequence-to-Structure Alignment and RNA Family Modeling
#### 6.6.5 A Structural Matcher for Covariance Models  
Covariance models (CMs) [20; 30; 31] describe families of RNA sequences, based on sequence similarity and structure conservation. A group of related sequences is aligned, a consensus structure is determined, and a model is built with a particular choice of architecture. Stochastic parameters are trained from the data. Model and parameters are applied to short query sequences, or in local search mode to scan whole genomes, to find additional family members. New members can be included into the set that defines the model, and parameters re-trained. Included sequences constitute the core of the model, called the \"seed alignment\" in Rfam terminology [32], while all known sequences that match the model above a certain threshold score constitute the \"full alignment\". So, there it a lot more going on than just solving a straighforward combinatorial optimization problem-but at the heart of the approach, there is the task of aligning a plain RNA sequence \(s\) to a target structure \(r\). In contrast to the exact matcher Match_S2S_R, a covariance model allows for deletions from the target structure, as well as for insertions in the RNA sequence. However, it does not allow for all possible operations from the core signature _STRAL_. Insertions in the RNA sequence are always considered unpaired (because for features not present in the model, one cannot train parameters). Hence, we will make no use of pair_ins, pairLR_ins, pairL_ins, and pairR_ins. The operator pairLR_del also goes away: It stands for a case where two unpaired bases are aligned to a base pair in the target. In covariance models, these bases are always considered paired, and scored with a low probability if they cannot legally form a pair. So operator pair already takes care of this case. Inlining non-terminal \(P\) as before, this reduces grammar StructAli to the following productions. \[S^{*} \rightarrow \texttt{single}(a,c,S)\] \[|\texttt{mty}\] \[|\texttt{del}(a,S)\] \[|\texttt{ins}(c,S)\] \[|\texttt{split}(\texttt{pair}(a,c,S,b,d),S)\] \[|\texttt{split}(\texttt{pair\_del}(a,S,b),S)\] \[|\texttt{split}(\texttt{pairL\_del}(a,c,S,b),S)\] \[|\texttt{split}(\texttt{pairR\_del}(a,S,b,d),S)\]  
For the moment, this is a generic matcher, with some edit operations disabled. To proceed to a covariance model, the target structure must be internalized. All variables (\(a\) and \(b\) in the grammar above) refering to the structure input will disappear. Applying the same internalization construction as with Match_S2S_R, we obtain from ICORE S2 Scgeneric a specific matcher CovarianceModel_r. We use the same target structure \(r\) as in the previous example. **Example 10**. : Consider sequence \(s=\texttt{\"GUCUCAGUG\"}\). It can be aligned to structure \(r=``<<\bullet>\bullet>>\bullet\"\) in manifold ways such as  
\[\texttt{G-UCUCAGUG} \texttt{GUC--UCAGUG} \texttt{GUCUCA-GUG-}\] \[<<\bullet>\bullet><->\bullet\ \ \ <<\bullet>\bullet>\ \ \ ->\bullet\ \ \ -<\bullet>\bullet><>\bullet\]The core term expressing the leftmost alignment of the query \(s\) to the covariance model CovarianceModel_r derived from \(r\) is  
\[|\texttt{mty}\]0  
where  
\[|\texttt{mty}\]1  
The above ICORE describes the search space of a specific covariance model. Now let us turn to scoring core terms. Note that even after all sequence information from \(r\) is eliminated, the grammar still \"knows\" (by the subscripted non-terminal symbols) the positions in the target structure to which a part of the query is aligned. For position specific scores, this information should be passed on to the scoring functions. The operator pair, for example, is implemented in a stochastic algebra (cf. Section 6.3) as  
\[|\texttt{mty}\]2  
It is used with \(S_{1},S_{2}\), and \(S_{7}\) in the specialized grammar. From the parameter estimation, we obtain (potentially) different probabilities \(\pi^{1}_{ab},\pi^{2}_{ab}\), and \(\pi^{7}_{ab}\) for these residues. Different uses of pair must be able to resort to these different parameters.