阿久津 達也 京都大学 化学研究所 バイオインフォマティクスセンター

Presentation on theme: "阿久津 達也 京都大学 化学研究所 バイオインフォマティクスセンター"— Presentation transcript:

1 阿久津 達也 京都大学 化学研究所 バイオインフォマティクスセンター
情報生命科学特別講義III （6）配列解析 阿久津　達也 京都大学　化学研究所 バイオインフォマティクスセンター

2 講義予定 第１回: 文字列マッチング 第２回： 文字列データ構造 第３回： たたみ込みとハッシュに基づくマッチング
第１回:　文字列マッチング 第２回：　文字列データ構造 第３回：　たたみ込みとハッシュに基づくマッチング 第４回：　近似文字列マッチング 第５回：　配列アラインメント 第６回：　配列解析 第７回：　進化系統樹推定 第８回：　木構造の比較：順序木 第９回：　木構造の比較：無順序木 第１０回：　文法圧縮 第１１回：　RNA二次構造予測 第１２回：　タンパク質立体構造の予測と比較 第１３回：　固定パラメータアルゴリズムと部分k木 第１４回：　グラフの比較と列挙 第１５回：　まとめ

3 オイラー閉路による配列決定

4 ゲノム配列決定 （現在のところ）一度に決めるのは無理 （制限酵素などを使って）短く切って、つなぎ合わせる
つなぎ合わせ：　配列アセンブリ（様々な定式化・方法が提案） CTCACTCAAAGGCGGTAATACGGTTATCCACAGAATCAGGGGATAA 元の配列 酵素を使って切断 CTCACTCAAAGGCGGTAA GGTAATACGGTTATCCAC TATCCACAGAATCAGGGGATAA つなぎあわせ CTCACTCAAAGGCGGTAATACGGTTATCCACAGAATCAGGGGATAA

5 SBH（Sequencing by Hybridization）による配列決定
入力 長さ k の文字列の集合： 出力 S のすべての要素を部分列としてちょうど1回含み、長さ k の他の文字列を部分列として含まない文字列 ACA CAC ACT CTG ACACTG 解なし CAG 注意：　定義において、解なしの場合にはそのことを出力。今後も同様

6 一筆書きとオイラー オイラーの定理（有向グラフ版） 次のどちらかの条件を満たす時、一筆書きができる (a) (b) (a) どの点についても
入って来る矢印の数 ＝ 出て行く矢印の数 (b) ２点以外は上と同じで、残りの点は、それぞれ以下を満たす 入って来る矢印の数 ＝ 出て行く矢印の数－１ 入って来る矢印の数－１ ＝ 出て行く矢印の数 （グラフは強連結であると仮定） (a) (b)

7 A C A A C C C A 問題の変換 AAC AAA CAC ACC CAA CCC CCA CAAACCCAC
アイデア： オイラー閉路問題への変換 各文字列について最初の(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問題は線形時間で解ける

8 最短共通拡大文字列

9 最短共通拡大文字列問題 (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 この問題の場合、解は必ず存在

10 最短共通拡大文字列： 基本アイデア アイデア： 巡回セールスマン問題に変換
アイデア：　巡回セールスマン問題に変換 命題： s1,s2,…,sn が sOPT 中でこの順番に並ぶと次の式が成立

11 最短共通拡大文字列： 巡回セールスマンへの帰着
１． si を頂点 vi に対応させ、 vi から vj への有向辺に重み |pref(si,sj)| を割り 当てた接頭辞グラフ G(V,E) を構成 2. すべての頂点の組 (vi ,vj) に対しステップ3を実行し，スコアが最小となる 閉路を計算し、その頂点の順番から最適解を構成し、終了 ３. vi から出発して最後にvj を通って vi にもどる重みの和が最小のハミルトン 閉路の重みに、重み |ovlp(sj,si)| を加えたものをスコアとする アイデア： ハミルトン閉路問題はNP困難⇒最小閉路被覆で代用 最小閉路被覆問題 入力: 重みつき有向グラフ G(V,E) 出力： すべての頂点がちょうど１つの閉路に１回だけ含まれ、かつ、重みの和が最小となる閉路の集合 ハミルトン閉路との違い： 　　複数の閉路の集合 ⇒ 二部グラフマッチングで最適解

12 最小閉路被覆問題： アルゴリズム １．頂点集合 U={u1,…,un}, W={w1,…,wn } からなる完全二部 グラフを構成し、(ui,wj) の重みを |pref(si,sj)| とする 2. 最小重み完全二部グラフマッチングを計算 ３. マッチング中の (ui,wj) を、G(V,E) の (vi,vj) に対応させ、解とする

13 最短共通拡大文字列： アルゴリズム １．文字列集合 S から G(V,E) を構成 2. G(V,E) の最小閉路被覆 C={c1,…,ck} を最小重み完全二部 グラフマッチングを用いて計算 ３. 各閉路 ci から文字列 σ(ci ) を作り、それをすべてつなげ た文字列 σ(C)=σ(c1)・ σ(c2)・・・σ(ck) を近似解 とする 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　に対し、 と定義し、　　を c の代表文字列とよぶ 上記アルゴリズムが多項式時間で動作するのは明らか 閉路に含まれる各文字列の長さが閉路の重み以下であれば、 　　 |σ(c)|≦2・w(c) が成立し、Σw(ci ) ≦ | sOPT| より、 |σ(C)|≦2・| sOPT | が成立 しかし、その仮定は成立しないので、より詳細に解析し|σ(C)|≦4・|sOPT| を示す

14 近似率の解析 （１） 補題1： Sの部分集合 S’ に対し、ある文字列 t が存在し、S’ 中の各文字列は t∞の部分文字列であるとする。すると、G(V,E)中に重みが |t| 以下で、かつ、S’ に対応するすべての頂点を通る閉路が存在 証明： S’ 中の各文字列 si の最初の文字は、 t∞の最初の t 中に出現するようにできる。その順番に頂点を並べれば、題意を満たす閉路が得られる 例：　下図の場合、S’={s1,s3,s5}であり、v3→v5→v1→v3 が閉路 t∞上は t を無限回つなげた文字列（実際には有限でOK）

15 近似率の解析 （２） 補題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) より、 c2 中もすべての文字列は p1 ∞ の部分文字列。よって、補題1から、 c1,c2 中のすべての頂点を含む重み |p1| 以下の閉路が存在することになり矛盾。

16 近似率の解析 （３） 定理： 最短共通拡大文字列問題に対して、最適解の4倍以内の長さの共通拡大文字列を多項式時間で計算可能
証明： w(C)=Σi=1…kw(ci) とすると次式が成立。 一般性を失うことなく r1, …, rk はSOPTにこの順番で出現すると仮定。 r1, …, rkのSCSの長さは|SOPT|以下なので、補題2より次式が成立。 よって、この式と |w(C)|≦|SOPT| から次式が成立。

17 逆位によるソーティング

18 逆位によるソーティング（符号なし） Sorting by Reversal
出力: π を id=(1,2,・・・,n)に変換するために必要な最小 　　　　回数（d(π)）の逆位系列 ゲノム再編成による進化履歴の推定に有用 置換 π： (1,2,…,n) を並び替えたもの 以降では、π0,πn+1を加えた 　　　π=(π0,π1,…,πn,πn+1) 　　を考える。ただし、 π0, 　　 πn+1は動かさないも 　　のとする 左図の場合、d(π)=3

19 切断点 切断点： |πi-πi-1|≠1 となる πi, πi-1 の境界 b(π): π における切断点の個数 減少断片: π における、値が１ずつ減少する長さ2以上の部分列 例 π=(0,1,4,6,5,2,3,7) の切断点は (1,4), (4,6), (5,2), (3,7) で、b(π)=4 π=(0,7,6,5,4,1,3,9,8,2,10) において、(7,6,5), (6,5,4) は極大でない減少断片で、(7,6,5,4), (9,8) は極大な減少断片 補題1　 b(π)/2 ≦ d(π) ≦ n 証明 1回の逆位操作により切断点の個数は高々2個しか減らないので b(π)/2 ≦ d(π) 。　d(π) ≦ n　の証明は宿題

20 逆位操作の検出 補題2 π が減少断片を含む時、b(π) を減らす逆位操作が存在 証明 以下のアルゴリズムにより逆位操作を検出 1. 右端が最小である極大減少断片 s を見つけ、右端の値を k とする 2. π における k-1 の位置を見つける ３．k-1 が k の右にあれば、s の右隣から k-1 までを逆位 (i) 左にあれば、k-1 の右隣から s の右端までを逆位 (ii)

21 近似アルゴリズムとその解析 アルゴリズム : 以下の π=id となるまで操作を繰り返す 1. 減少断片が存在すれば補題2を適用 2. 存在しなければ、極大な増加断片で π0, πn+1 のいずれも含まないものを 見つけ逆位操作を適用。それも存在しなければ、πj=πi-1 を満たす j > i で、 かつ、 π0 もしくは πn+1 を含む増加断片にπi, πj が含まれないもの を見つけ、 (πi, πi+1,…, πj-1) に逆位操作を適用 定理 符号なしの逆位によるソーティング問題に対し、4d(π)回以内の逆位操作系列を多項式時間で計算可能 証明 上記アルゴリズムで ステップ1 が実行されれば、b(π)は１以上減少。 ステップ2が実行されれば、 b(π)は増加せず、次回はステップ1が実行可能。 よって、高々 2・b(π) 回の逆位操作により id へ至ることができる。 補題1より、 2・b(π) ≦4・d(n)

22 逆位によるソーティング（符号あり） 遺伝子には方向性があるので、方向（符号：+－)を考えた逆位系列を考えるのは妥当
逆位操作により、符号も反転 符号なしのソーティングはNP困難だが、符号ありのソーティングは多項式時間で解ける

23 まとめ オイラー閉路による配列決定： オイラー閉路問題に帰着 最短共通拡大文字列: ハミルトン閉路問題に帰着し、近似
逆位によるソーティング: 符号ありは多項式時間で解けるが、符号なしはNP困難（切断点の導入により近似精度を保証） 補足 オイラー閉路による配列推定は近年数多くの実用的な拡張 最短共通拡大文字列の近似は 2.5 まで改良 [Haim Kaplan, Shafrir: Inf. Proc. Lett. 2005]　⇒ 2012年に 2+11/23 まで改良[Mucha, Proc. SODA, 2012] 最短共通拡大文字列に関連した問題として、Shortest Common Supersequence, Longest Common Subsequence という問題があるが、近似率に関して [Jiang, Li: SIAM J. Comput. 1995] 以来、本質的な進歩がないと思われる 逆位によるソーティングの近似は まで改良 [Berman et al.: Proc. ESA 2002] ソーティング問題はコピーや移動を許したものなど、様々な拡張がある