1. The RNA Folding Problem
Given a sequence of nucleotides, we want to "fold" it by introducing pairings that result in a stable structure (minimizing free energy).
Constraints
A common constraint is that pairings should not "cross".
If \( (i_1, i_2) \) is a pair, there should be no pair \( (i_3, i_4) \) such that \( i_1 < i_3 < i_2 < i_4 \).
RNA Structure Representation
Dashed lines represent pairings (Hydrogen bonds).
2. Optimization Formulation
We can model this as a sequential decision problem. At each nucleotide, we have at most 3 choices:
Open
Start a new pairing.
Close
Complete an existing pairing.
Do Nothing
Leave unpaired.
Rollout Application
- State: Partial folding of the sequence.
- Base Heuristic: Existing software that generates a "reasonable" complete folding from a partial one.
- Expert Software: Evaluates the quality (energy) of complete foldings.
3. Multistep Lookahead
Since the branching factor is small (at most 3), this problem is ideal for multistep lookahead.
Complexity
With \( \ell \)-step lookahead, the number of Q-factors to compute is at most \( 3^\ell \).
This allows for deeper exploration of the folding space compared to simple one-step lookahead.