## 3 Estimating the Rule Probabilities
### Grammars  
We used 4 different grammars for our experiments:
In each of the grammars \(S\) is the start symbol, other capital letters denote nonterminal symbols and \(A\rightarrow\quad|\quad\) is used as a shorthand for \(A\rightarrow\quad\in R\) and \(A\rightarrow\quad\in R\). As we have stated before, the grammars are to generate the primary structures as words and encode the secondary structures in the derivation. Thus we have to distinguish (in the grammar) between terminal symbols representing unpaired bases and terminal symbols being part of a base pair. In the above grammars the former are denoted by the symbol \(b\) while the latter are denoted by pairs \(\partial\colon\partial\). Now simply introducing a rule for each combination of how the symbols \(\partial\colon\partial\) and \(b\) can be replaced by the terminal symbols would--especially in the case of G4--lead to a significant increase in the number of productions. To counter this the authors of [13] translated the concept of transition and emission probabilities from hidden Markov models to SCFGs. The transition probability then is the probability of choosing e.g. the rule scheme \(S\rightarrow\partial S\) independent of which terminal symbol is used in place of \(b\). The emission probability then is the probability that a given \(b\) is a placeholder, e.g. \(\iota\) independent of the rule which introduced the \(b\). In order to include this idea without having to extend the theory in Section 3 we left \(b\) in the grammar as a nonterminal and replaced all occurrences of \(\partial\bot\partial\) in G4 (or the corresponding substrings in the other grammars) with \(A\), adding rules that generate all (combinations of) terminal symbols \(\partial\colon C\colon g\) and \(\iota\) from these nonterminals. G1 and G2 have been taken from [13], G1 being the simplest grammar in the comparison and G2, which originates from [3], being the grammar which achieved the best results. G2 and G3 both extend G1 based on the observation that a secondary structure will be more stable if it contains longer runs of immediately nested base pairs. They differ in the approach taken to get this into the model. G4 has been taken from [15]. It models the decomposition that is used for minimum free energy prediction. Since a run of unpaired bases contributes differently to the free energy depending on the context it appears in, these runs are derived from a separate intermediate symbol (\(B\colon C\colon H\colon J\) or \(U\)) depending on the context with the intention of capturing these different contributions in the rule probabilities. As we stated in Section 2 we implemented length-dependency such that we grouped the lengths into intervals, the rule probabilities changing only from one interval to the other but not within them. Since the influence a change in length has on the probabilities most likely depends on the relative change rather than the absolute one, we decided to make the intervals longer as the subwords considered get longer. This also helps to keep the estimated probabilities accurate since naturally any training set will contain fewer data points per length as the length increases. Aside from this consideration and the restrictions implied by Definition 5 (consistency of a set of intervals) there is no obvious criterion that helps with deciding on a set of intervals. Thus we created several different sets ranging from approximately 10 to approximately 100 intervals, evaluating a subset of the prediction data with each of them. The results corresponded to our expectation that finer intervals would tend to improve the quality of prediction until at some point the amount of data available to estimate each probability would be too sparse and thus the quality would degrade.