Exercise sheet 4: McCaskill

---

Exercise 1

You are given the following matrix \(C\) for sequence \(S\) = AUCCAU:

It was calculated using the following recursion:

\[ C_{i,j} = \textbf{1}(i,j) \cdot C_{i+1,j-1} \cdot 1 + \sum_{i\leq k < j} C_{i,k} \cdot C_{k+1,j}, \text{ with } \textbf{1}(i,j) = \begin{cases} 1 & \text{if } S_{i} S_{j} \text{ compl.} \\ 0 & \text{else} \end{cases} \]

We assume a minimum loop length of 0.

1.1

Calculate the value of \(C_{1,6}\). What does it represent?

Hide

Solution

\(C_{1,6}\) is the number of possible secondary structures for the sequence \(S\).

1.2

Does this result make sense? Justify your answer!

Hide

Solution

No, this result does not make sense. The number of possible secondary structures for the sequence \(S\) is much lower than 83. Several structures are counted multiple times.

1.3

Recalculate the matrix \(C\) using the following recursion:

\[ C_{i,j} = C_{i,j-1} + \sum\limits_{\substack{i \leq k < j \\ S_{k}, S_{j} \text{ compl.}}} C_{i,k-1} \cdot C_{k+1,j-1} \]

Hide

Solution

1.4

Why does the result of this recursion differ from the result of the first recursion?

Hide

Solution

There is no ambiguity, the first part of the recursion only counts cases where \(j\) is unpaired and the second part only counts cases where \(j\) is paired. Both parts of the recursion are disjoint. Whereas the recursion from exercise 1.1 is ambiguous in the second part of the recursion.