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

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

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

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

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

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

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問題は線形時間で解ける

最短共通拡大文字列

最短共通拡大文字列問題 (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) 出力： すべての頂点がちょうど１つの閉路に１回だけ含まれ、かつ、重みの和が最小となる閉路の集合 ハミルトン閉路との違い： 　　複数の閉路の集合 ⇒ 二部グラフマッチングで最適解

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

最短共通拡大文字列： アルゴリズム １．文字列集合 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| を示す

近似率の解析 （１） 補題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）

近似率の解析 （２） 補題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| 以下の閉路が存在することになり矛盾。

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

逆位によるソーティング

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

切断点 切断点： |π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　の証明は宿題

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

近似アルゴリズムとその解析 アルゴリズム : 以下の π=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)

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

まとめ オイラー閉路による配列決定： オイラー閉路問題に帰着 最短共通拡大文字列: ハミルトン閉路問題に帰着し、近似 逆位によるソーティング: 符号ありは多項式時間で解けるが、符号なしは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] 以来、本質的な進歩がないと思われる 逆位によるソーティングの近似は 1.375 まで改良 [Berman et al.: Proc. ESA 2002] ソーティング問題はコピーや移動を許したものなど、様々な拡張がある