1、九州大学大学院 情報学 専攻 特別講義（） 配列解析阿久津 達也京都大学 化学研究所講義内容n 概論（資料）n 配列n 配列解析n RNA二次構造予測n 質立体構造比較予測n 固定 部分 k木n 比較 列挙n 離散n 解析制御講義進展状況内容変更可能性最短共通拡大文字列最短共通拡大文字列問題 (Shortest Superstring)入力 : 文字列集合：出力 : si 拡大文字列 、長最短 文字列 sOPT問題場合、解必存在s t 拡大文字列 t s 部分文字列ovlp(si,sj): si=sa sb, sj=sb sc 満最長 sbpref(si,sj): 上記定義 sa例： s1=A
2、CGT, s2=GTAC, s3=CAGT, s4=GTCAGn 最短共通拡大文字列 GTACGTCAGTn ovlp(s3,s4)=GT pref(s3,s4)=CAn ovlp(s4,s3)=CAG pref(s4,s3)=GT最短共通拡大文字列： 基本： 巡回問題変換命題 ： s1,s2, sn sOPT 中順番並次式成立最短共通拡大文字列： 巡回帰着 si 頂点 vi 対応 、 vi vj 有向辺 重 |pref(si,sj)| 割当 接頭辞 G(V,E) 構成2. 頂点 組 (vi ,vj) 対 3実行 ，最小 閉 路計算 、 頂点順番 最適 解構成 、終了. vi 出発最後 vj
3、通 vi 重 和 最小 閉路重 、重 |ovlp(sj,si)| 加 ： 閉路問題 NP困難 最小閉路被覆 代用最小閉路被覆問題入力 : 重有向 G(V,E)出力 ： 頂点閉路回含、重和最小閉路集合閉路違 ：複数閉路集合 二部最適解最小閉路被覆問題： 頂点集合 U=u1, un, W=w1, wn 完全二部構成、 (ui,wj) 重 |pref(si,sj)| 2. 最小重完全二部 計算. 中 (ui,wj) 、G(V,E) (vi,vj) 対応、解対、定義、 c 代表文字列最短共通拡大文字列： 文字列集合 S G(V,E) 構成2. G(V,E) 最小閉路被覆 C=c1, ck 最小重完全二
4、部用計算. 各閉路 ci 文字列 (ci ) 作、文字列 (C)=(c1) (c2) (ck) 近似解 n 上記 多項式時間 動作明n 閉路含 各文字列長閉路重以下 、|(c)| 2 w(c) 成立、 w(ci ) | sOPT| 、 |(C)| 2 | sOPT | 成立 n 、仮定成立、 詳細解析 |(C)| 4 |sOPT| 示近似率解析 （）t上 t 無限回文字列（実際有限 OK）補題 1： S部分集合 S 対、文字列 t 存在、 S 中各文字列 t部分文字列。、 G(V,E)中重 |t| 以下、 S 対応頂点通閉路存在証明： S 中各文字列 si 最初文字、 t最初 t 中出現。順番
5、頂点並、題意満閉路得例 ： 下図場合 、 S=s1,s3,s5、 v3 v5 v1 v3 閉路近似率解析 （）補題 2： c1,c2 C 中閉路、 r1, r2 代表文字列|ovlp(r1,r2)| w(c1) + w(c2) 成立証明： |ovlp(r1,r2)| w(c1) + w(c2) 仮定、矛盾導。 p1 長 w(c1) ovlp(r1,r2) 接頭辞 ovlp(r1,r2) p1 接頭辞。p2 長 w(c2) ovlp(r1,r2) 接頭辞 ovlp(r1,r2) p2 接頭辞。、仮定 p1 p2 = p2 p1 p1 =p2 成立。、 r2 c2 代表文字列、 r2 |ovlp(r1,r2)| w(c1) + w(c2) w(c2)、c2 中文字列 p1 部分文字列。、 c1 中 文字列p1 部分 文字列。、補題 1、 c1,c2 中頂点含重 |p1| 以下閉路存在矛盾。
