# Chapter6.5

#### RNA Secondary Structure: Dynamic Programming over Intervals

## 定式

文字列: $B = b_1 b_2 \dots bn, b_i \in \{A,C,G,U \}$

RNAという遺伝子をモデル化したもの。RNAは塩基ごとにペアを作る。
以下の4つのルールを守った上で、文字列$B$に対してペアを生成する。このペアの集合を$S$とし、RNAの構造と呼ぶ。

- $b_i,b_j \ (i < j)$がペアであるとき$i < j - 4$
- かならず$(A,U), (C,G)$のどちらかのペアとなる
- $b_i$は2つ以上のペアを作らない
- ペアはそれぞれ線で繋がれると考えた時に、線が交差しない。言い換えると$(i,j),(k,l)$が存在し$i < k$ならば$i < k < j< l$とはならない。

ただし注意して欲しいのは$b_i$はかならずペアになるわけではない。ぼっちもいる。

## 目的

ペアの数を最大化する。

## アルゴリズム

### 最初のアプローチ

$OPT(j) := b_1 \cdots b_jでの最適解$

$j$に対して2つの操作が考えられる.

1. j番目はペアにならない.このとき$OPT(j) := OPT(j-1)$
2. j番目は$t < j - 4$ペアになるのいずれかとペアになる.

#### 2番について

$t$と$j$がペアとなるとき、$1,\cdots ,t -1$の任意の要素と$t+1, \cdots j -1$とペアになることはできない。
なので$OPT(j) = OPT(t -1) + [t + 1 からj -1での最大値]$。2つ目の項は定義されていない。

### 改善案

$OPT(i,j) := b_i , \cdots , b_j$での最大ペア数

### ベルマン方程式

$OPT(i,j) := max(OPT(i,j-1),1 + OPT(i,t - 1) + OPT(t + 1,j - 1)), for \ any \ t \in \{i, \cdots ,j-1\}$

### アルゴリズム

はい。やるだけ。algorithm designをみろ。

### ねこ

ねこ〜〜

### 計算量

$O(n^3)$