RNA二次構造予測RNA二次構造予測RNA二次構造の二種類の表現RNA二次構造の例Nussinovアルゴリズム予測アルゴリズム（Nussinovアルゴリズム）アルゴリズムの説明Nussinovアルゴリズムの解析RNA二次構造予測と確率文脈自由文法RNA二次構造予測と確率文脈自由文法（１）RNA二次構造予測と確率文脈自由文法（２）Valiantアルゴリズムの利用二次構造予測の計算量の改良Valiantアルゴリズムの概略（１）Valiantアルゴリズムの概略（２）Valiantアルゴリズムの概略（３）メインルーチン：下図のとおり時間計算量：まとめRNA二次構造予測のO(n2.8…polylog(n))時間アルゴリズム背景アルゴリズムの概略Phase２：解析Phase３：正当性時間計算量の解析補題３：証明（１）補題３：証明（２）まとめ