配列解析-京都大学.pptVIP

* * * * * * * * 情報生命科学特別講義III（6）配列解析 阿久津　達也 京都大学　化学研究所 バイオインフォマティクスセンター 講義予定 第１回:　文字列マッチング 第２回：　文字列データ構造 第３回：　たたみ込みとハッシュに基づくマッチング 第４回：　近似文字列マッチング 第５回：　配列アラインメント 第６回：　配列解析 第７回：　進化系統樹推定 第８回：　木構造の比較：順序木 第９回：　木構造の比較：無順序木 第１０回：　文法圧縮 第１１回：　RNA二次構造予測 第１２回：　タンパク質立体構造の予測と比較 第１３回：　固定パラメータアルゴリズムと部分k木 第１４回：　グラフの比較と列挙 第１５回：　まとめ オイラー閉路による配列決定 ゲノム配列決定 （現在のところ）一度に決めるのは無理 （制限酵素などを使って）短く切って、つなぎ合わせる つなぎ合わせ：　配列アセンブリ（様々な定式化?方法が提案） CTCACTCAAAGGCGGTAATACGGTTATCCACAGAATCAGGGGATAA 元の配列 酵素を使って切断 CTCACTCAAAGGCGGTAA GGTAATACGGTTATCCAC TATCCACAGAATCAGGGGATAA つなぎあわせ CTCACTCAAAGGCGGTAATACGGTTATCCACAGAATCAGGGGATAA SBH（Sequencing by Hybridization）による配列決定 入力 長さ k の文字列の集合： 出力 S のすべての要素を部分列としてちょうど1回含み、長さ k の他の文字列を部分列として含まない文字列 注意：　定義において、解なしの場合にはそのことを出力。今後も同様 ACA CAC ACT CTG ACACTG 解なし ACA CAC ACT CAG 一筆書きとオイラー オイラーの定理（有向グラフ版） 次のどちらかの条件を満たす時、一筆書きができる (a) どの点についても 入って来る矢印の数 ＝ 出て行く矢印の数 (b) ２点以外は上と同じで、残りの点は、それぞれ以下を満たす 入って来る矢印の数 ＝ 出て行く矢印の数－１ 入って来る矢印の数－１ ＝ 出て行く矢印の数 (a) (b) （グラフは強連結であると仮定） 問題の変換 アイデア： オイラー閉路問題への変換 各文字列について最初の(k-1)文字に対応する頂点から、最後の(k-1)文字に対応する頂点に辺を引く。一筆書き可なら解あり CAAACCCAC S={ AAA, AAC, ACC, CAA, CAC, CCA, CCC } A C A A AAA CAC CAA ACC CCA CCC C C C A AAC 定理： SBH問題は線形時間で解ける 最短共通拡大文字列 最短共通拡大文字列問題 (Shortest Superstring) 入力: 文字列集合： 出力: すべての si の拡大文字列となっており、かつ、 長さが最短の文字列 sOPT この問題の場合、解は必ず存在 s は t の拡大文字列 ? t は s の部分文字列 ovlp(si,sj): si=sa?sb, sj=sb?sc を満たす最長の sb pref(si,sj): 上記定義の sa 例：　s1=ACGT, s2=GTAC, s3=CAGT, s4=GTCAG 最短共通拡大文字列は GTACGTCAGT ovlp(s3,s4)=GT pref(s3,s4)=CA 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 を通って vi にもどる重みの和が最小のハミルトン 　　　閉路の重みに、重み |ovlp(sj,si)| を加えたものをスコアとする アイデア： ハミルトン閉路問題はNP困難?最小閉路被覆で代用 最小閉路被覆問題 入力: 重みつき有向グラフ G(V,E) 出力： すべての頂点がちょうど１つの閉路に１回だけ含まれ、かつ、重みの和が最小となる閉路の集合 ハミルトン閉路との違い： 　　複数の閉路の集合