阿久津 達也 京都大学 化学研究所 バイオインフォマティクスセンター 生物情報ソフトウェア特論 （4）配列解析I 阿久津　達也 京都大学　化学研究所 バイオインフォマティクスセンター

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

配列アラインメント

… ペアワイズ・アラインメント ２本の配列に対するアラインメント 大域アラインメント： 配列全体にわたるアラインメント 列ごとにスコアが定義され、各列のスコアの和が最大となる最適アラインメントを計算 入力配列 ACGT ATCCT アラインメント … A C G T ー A ー C G T A C ー G T A T C C T A T C C T －6 1 －1 スコア スコアの定義 同じ文字： １ 違う文字： －１ ギャップ： －１

動的計画法による最適アラインメントの計算 アラインメントの個数：指数関数のオーダー 動的計画法を用いれば O(mn) 時間 D[i,j] は始点(0,0)から(i,j)までの最適パスのスコア アラインメントの復元（トレースバック） D[m,n] から再帰式で＝となっている頂点を逆にたどる D[i,j] D[i-1,j] D[i-1,j-1] D[i,j-1] -d w(s[i],t[j]) s,t: 入力配列 　s[i]: 配列 s の i 番目の文字　 m=|s|, n=|t| w(x,y): 文字 x,y 間のスコア　 -d: ギャップ記号のスコア

マルチプル・アラインメント：定式化 S(mi) = -∑cia log pia （cia= i列におけるaの出現回数, ３本以上の配列が与えられた時、長さが同じで、かつ、スコアが最適となるように各配列にギャップを挿入したもの スコアづけ　（全体スコアは基本的に各列のスコアの和:∑S(mi)） 最小エントロピースコア S(mi) = -∑cia log pia　　　（cia= i列におけるaの出現回数, pia = i列におけるaの生起確率） SPスコア(Sum-of-Pairs) S(mi)=∑k＜lw(mk[i],ml[i]) 　　　　　　　　　　　　　　　　　　（ mk[i]= アラインメント後のi列, k行目の文字）

多次元DPによるマルチプル・アラインメント N個の配列に対するマルチプル・アラインメント N次元DPによりO(2NnN)時間 （各配列の長さはO(n)を仮定） 例：N=3 一般の N に対しては NP困難 (i,j,k) (i-1,j,k) (i,j-1,k) (i,j-1,k-1)

マルチプル・アラインメントの実用的計算手法 プログレッシブ・アラインメント CLUSTAL-W（広く利用されているソフト）などで採用 逐次改善法との組み合わせが、より有効 逐次改善法 シミュレーテッドアニーリング 遺伝的アルゴリズム HMMによるアラインメント 分枝限定法 １０配列程度なら最適解が計算可能

近似アルゴリズム NP困難問題への対処法 近似アルゴリズム 固定パラメータアルゴリズム 指数時間アルゴリズム（O(an)で底aを小さくする） 平均的に高速なアルゴリズム ヒューリスティックなアルゴリズム 最適解との比率の最悪の場合の上限を理論的に保証 最適解がわからないのにどうやって保証するか？ 最適解の下限を理論的に見積もる（最小化問題の場合） 近似解の上限を理論的に見積もる 「近似解の上限／最適解の下限」が比率になる

近似アルゴリズム： センタースター法 アルゴリズム ∑k≠iS(sk,si)が最小となる sk を計算 スコアに三角不等式を仮定し、最小化問題として定義 SPスコアを使用 アイデア： 中心となる配列を定め、それと各配列とのアラインメント結果をまとめる アルゴリズム ∑k≠iS(sk,si)が最小となる sk を計算 S(sk,si)をもとにギャップを適切に挿入し、マルチプルアラインメントA を構成 図中の xi はsi を表す

センタースター法の解析 定理 A のSPスコア ≦ (2-2/N)・最適解の SPスコア 証明 N・Starのスコア ≦2・最適解のスコア 　 (図2でx1に（=s1）接続しない辺のスコアの合計はスター(N-2)個分以下) 図中の xi はsi を表す

アラインメントに関するまとめ ペアワイズ・アラインメント マルチプル・アラインメント 補足 動的計画法で O(n2) 時間、線形領域も可能 局所アラインメント、線形ギャップスコアでも同様 マルチプル・アラインメント NP困難だが、距離で定義した場合、2近似が可能 補足 ペアワイズ・アラインメントは O(n2/log n) 時間で可能 [Crochemore et al.: Proc. SODA 2002]。でも、SETHのもとで、　 O(n2-ε）時間は不可能。 様々なギャップスコアや疎行列の場合の動的計画法についても多くの研究 [Galil, Park: Theoret. Comp. Sci. 1992] マルチプル・アラインメントの近似率は 2-K/N まで改善（K は 任意の定数） [Bafna et al.: Theoret. Comp. Sci. 1997] N に関係なく 2 より良くできるかは研究課題

編集距離計算量の下限

編集距離 入力： 出力： x を y に変換するのに必要な最小の編集操作数 （ペアワイズの全域配列アラインメントと本質的に等価） 編集操作: (A) 文字の置換 (B) 1文字挿入 (C) 1文字削除 ED(x,y): 文字列 x, y 間の編集距離 x=ATGAT A T G C ー ED(x,y)=3 y=ACTCT 挿入 置換 削除 定理：編集距離はSETHのもとでO(n2-ε)時間で計算不可 [Backurs & Indyk, STOC 2015] PT(x,y): 文字列 x と、 y の連続部分文字列との最小編集距離 （近似文字列マッチングの誤差と本質的に等価）

SAT(充足可能性問題) 用語 ＳＡＴ k-SAT: すべての節が k 個以下のリテラルの論理和 リテラル： 変数もしくは変数の否定(NOT) 節： リテラルの論理和(OR) 充足可能： 節(集合)を真とする変数への 0-1 割り当てが存在 ＳＡＴ 入力： 節集合　S 問題： S は充足可能(すべての節を真とする割り当てが存在する)か? k-SAT: すべての節が k 個以下のリテラルの論理和

SETH（Strong Exponential Time Hypothesis） SATに関する結果（乱拓アルゴリズムを含む） 3-SAT: O(20.388n) [Hertli, SCICOMP, 2014] 4-SAT: O(20.555n) [Hertli, SCICOMP, 2014] k-SAT： 2(1-1/O(k))n時間 [Paturi et al., JACM, 2005] 一般の場合： 2(1-1/O(log(m/n)))n 時間 （m：節の個数）[Calabro et al., Proc. CCC, 2006] SETH n 変数のSATは、どの定数 ε>0 に関しても、2(1-ε)n時間では解けない（という仮説） 直交ベクトル問題 入力：　d次元0-1ベクトルの集合A, B　(|A|=|B|=N) 出力: x・y=0（内積が0）となる (x,y)∊A×B はあるか？ SETHが成立⇒この問題は O(N2-εd) 時間では解けない

SATから直交ベクトル問題への還元 解析 SATの変数を XA={x1,…, xn/2}と XB={xn/2+1,…,xn}に２分割 XA（resp., XB）へのすべての0-1割り当てについて この割り当てで充足される節を０、充足されない節を１として、それらを並べた0-1ベクトルを作成し、 そのベクトルの集合をA（resp., B）とする (|A|=|B|=N=2n/2) 解析

証明の方針 直交ベクトル問題を編集距離問題に還元 直交ベクトルが存在 ⇔ P1 が P2 中で閾値以下でマッチ 直交ベクトルが存在 ⇔ 編集距離が閾値以下 A, B の要素（d次元0-1ベクトル）を文字列に変換 P1 = Aから変換した文字列をつなげたもの P2 = Bから変換した文字列をつなげたもの＋α 直交ベクトルが存在 ⇔ P1 が P2　中で閾値以下でマッチ 直交ベクトル（から変換した文字列）でちょうど重なるように、ずらしてマッチ

証明の概略（１）： 0-1の文字列化 Aのベクトル中の0,1 ⇒ CG1(0), CG1(1), g Bのベクトル中の0,1 ⇒ CG2(0), CG2(1) 1-1 間の距離は大きく（3l0)、他のビット間の距離は小さい（l0 ） g と、B の0,1 間の距離はほんの少し大きい（ l0 +1）

証明の概略（２）： ベクトルの文字列化 a∊A, b∊B に対し、VG1(a), VG2(b) を以下のように構成 証明の概略（２）：　ベクトルの文字列化 a∊A, b∊B に対し、VG1(a), VG2(b) を以下のように構成 a,bが直交すれば、ED(VG1(a),VG2(b))=l+2l2+dl0 :=Es 直交しなければ、 ED(VG1(a),VG2(b))=Es+d :=Eu 　　（直交すれば CG どうしがマッチ、それ以外は g…g とマッチ）

証明の概略（３）：ベクトル集合の文字列化 A, B に対し、P1, P2 を下図のように構成 （|A|≦|B|） 直交する (a,b) があれば、PT(P1,P2)≦(|A|-1) Eu + Es なければ、 PT(P1,P2) = |A| Eu ⇒ P’1=3 |P’2| P13 |P’2| , P’2= P2 として ED(P’1,P’2) を計算

編集距離計算下限に関するまとめ 編集距離計算、ペアワイズアラインメント 補足 多くの結果（下限）が前後して出現 SETHが成立 ⇒ （任意のε>0に対し）O(n2-ε） 時間では不可能 補足 多くの結果（下限）が前後して出現 局所アラインメント: O(n2-ε) [Abboud et al., ICALP 2014] Dynamic Time Warping Distance: O(n2-ε ) [Abboud et al., FOCS 2015] Longest Common Subsequence (for k strings): O(nk-ε ) [上と同じ] 部分木同型性： O(n2-ε） [Abboud et al., SODA 2016] 文脈自由文法解析, RNA二次構造予測： O(nω-ε ) [Abboud et al., FOCS 2015] クリーク問題を還元（ωは行列乗算に関する係数） 確率文脈自由文法解析： O(n3-ε ) [Saha, FOCS 2015] （all pairs）最短経路問題を還元 SETH を（妥当な仮定のもとで）証明する、もしくは、否定するのは重要な研究課題