九州大學集中講義

1、九州大學大學院　情報學専攻特別講義（３） 配列解析,阿久津　達也京都大學　化學研究所バイオインフォマティクスセンター,講義內容,バイオインフォマティクス概論（資料なし）配列アラインメント配列解析RNA二次構造予測タンパク質立體構造の比較と予測固定パラメータアルゴリズムと部分k木グラフの比較と列挙ニューラルネットワークの離散モデルブーリアンネットワークの解析と制御,講義の進展狀況によっては內容に変更の可能性あり,

2、最短共通拡大文字列,最短共通拡大文字列問題 (Shortest Superstring),入力: 文字列集合：出力: すべての si の拡大文字列となっており、かつ、長さが最短の文字列 sOPT,この問題の場合、解は必ず存在,s は t の拡大文字列 ? t は s の部分文字列ovlp(si,sj): si=sa?sb, sj=sb?sc を満たす最長の sbpref(si,sj): 上記定義の sa,例：　s1=ACGT

3、, s2=GTAC, s3=CAGT, s4=GTCAG最短共通拡大文字列は GTACGTCAGTovlp(s3,s4)=GT pref(s3,s4)=CAovlp(s4,s3)=CAG pref(s4,s3)=GT,,最短共通拡大文字列： 基本アイデア,アイデア：　巡回セールスマン問題に変換,命題： s1,s2,…,sn が sOPT 中でこの順番に並ぶと次の式が成立,最短共通拡大文字列：

4、 巡回セールスマンへの帰著,１． si を頂點 vi に対応させ、 vi から vj への有向辺に重み |pref(si,sj)| を割り　　　當てた接頭辭グラフ G(V,E) を構成2. すべての頂點の組 (vi ,vj) に対しステップ3を実行し，スコアが最小となる　　　閉路を計算し、その頂點の順番から最適解を構成し、終了３. vi から出発して最後にvj を通って vi にもどる重みの和が最小のハミルトン　　　閉

5、路の重みに、重み |ovlp(sj,si)| を加えたものをスコアとする,アイデア： ハミルトン閉路問題はNP困難?最小閉路被覆で代用,最小閉路被覆問題入力: 重みつき有向グラフ G(V,E)出力： すべての頂點がちょうど１つの閉路に１回だけ含まれ、かつ、重みの和が最小となる閉路の集合,ハミルトン閉路との違い：　　複數(shù)の閉路の集合 ? 二部グラフマッチングで最適解,最小閉路被覆問題： アルゴリズム,１．頂點集合 U={u1,…,

6、un}, W={w1,…,wn } からなる完全二部　　　　グラフを構成し、(ui,wj) の重みを |pref(si,sj)| とする2. 最小重み完全二部グラフマッチングを計算３. マッチング中の (ui,wj) を、G(V,E) の (vi,vj) に対応させ、解とする,に対し、と定義し、　　を c の代表文字列とよぶ,最短共通拡大文字列： アルゴリズム,１．文字列集合 S から G(V,E) を構成2. G

7、(V,E) の最小閉路被覆 C={c1,…,ck} を最小重み完全二部　　　グラフマッチングを用いて計算３. 各閉路 ci から文字列 σ(ci ) を作り、それをすべてつなげ　　　た文字列 σ(C)=σ(c1)? σ(c2)???σ(ck) を近似解 とする,上記アルゴリズムが多項式時間で動作するのは明らか閉路に含まれる各文字列の長さが閉路の重み以下であれば、　　 |σ(c)|≦2?w(c) が成立し、Σw(ci )

8、≦ | sOPT| より、 |σ(C)|≦2?| sOPT | が成立 しかし、その仮定は成立しないので、より詳細に解析し|σ(C)|≦4?|sOPT| を示す,,近似率の解析 （１）,t∞上は t を無限回つなげた文字列（実際には有限でOK）,補題1： Sの部分集合 S’ に対し、ある文字列 t が存在し、S’ 中の各文字列は t∞の部分文字列であるとする。すると、G(V,E)中に重みが |t| 以下で、かつ、S’ に対応するすべ

9、ての頂點を通る閉路が存在,証明： S’ 中の各文字列 si の最初の文字は、 t∞の最初の t 中に出現(xiàn)するようにできる。その順番に頂點を並べれば、題意を満たす閉路が得られる,例：　下図の場合、S’={s1,s3,s5}であり、v3→v5→v1→v3 が閉路,,近似率の解析 （２）,補題2： c1,c2 を C 中の閉路とし、r1, r2 をそれぞれ代表文字列とすると　|ovlp(r1,r2)| < w(c1) + w(c2)

10、 が成立,証明： |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 ∞ が成立。また

11、、r2 は c2 の代表文字列であり、 r2≧|ovlp(r1,r2)| ≧ w(c1) + w(c2) ≧ w(c2)より、c2 中のすべての文字列は p1 ∞ の部分文字列。また、 c1 中のすべての文字列も p1 ∞ の部分文字列。よって、補題1から、 c1,c2 中のすべての頂點を含む重み |p1| 以下の閉路が存在することになり矛盾。,,近似率の解析 （３）,定理： 最短共通拡大文字列問題に対して、最適解の4倍以內の長さの

12、共通拡大文字列を多項式時間で計算可能,証明： w(C)=Σi=1…kw(ci) とすると次式が成立。一般性を失うことなく r1, …, rk はSOPTにこの順番で出現(xiàn)すると仮定。r1, …, rkのSCSの長さは|SOPT|以下なので、補題2より次式が成立。よって、この式と w(C)≦|SOPT| から次式が成立。,逆位によるソーティング,逆位によるソーティング（符號なし）　Sorting by Reversal,入力:

13、 置換 π=(π1,π2,???,πn)出力: π を id=(1,2,???,n)に変換するために必要な最小　　　　回數(shù)（d(π)）の逆位系列,ゲノム再編成による進化履歴の推定に有用置換 π： (1,2,…,n) を並び替えたもの以降では、π0,πn+1を加えた　　　π=(π0,π1,…,πn,πn+1)　　を考える。ただし、 π0,　　 πn+1は動かさないも　　のとする左図の場合、d(π)=3,切斷點,切斷點：

14、 |πi-πi-1|≠1 となる πi, πi-1 の境界b(π): π における切斷點の個數(shù)減少斷片: π における、値が１ずつ減少する長さ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,

15、8) は極大な減少斷片,補題1　 b(π)/2 ≦ d(π) ≦ n証明1回の逆位操作により切斷點の個數(shù)は高々2個しか減らないので b(π)/2 ≦ d(π) ?！(π) ≦ n　の証明は宿題,逆位操作の検出,補題2 π が減少斷片を含む時、b(π) を減らす逆位操作が存在証明　以下のアルゴリズムにより逆位操作を検出1. 右端が最小である極大減少斷片 s を見つけ、右端の値を k とする2. π における k-1 の位置を見

16、つける３．k-1 が k の右にあれば、s の右隣から k-1 までを逆位 (i)　　左にあれば、k-1 の右隣から s の右端までを逆位 (ii),近似アルゴリズムとその解析,アルゴリズム : 以下の π=id となるまで操作を繰り返す1. 減少斷片が存在すれば補題2を適用2. 存在しなければ、極大な増加斷片で π0, πn+1 のいずれも含まないものを　　見つけ逆位操作を適用。それも存在しなけ

17、れば、πj=πi-1 を満たす j > i で、　　かつ、 π0 もしくは πn+1 を含む増加斷片にπi, πj が含まれないもの を見つけ、　　(πi, πi+1,…, πj-1) に逆位操作を適用,定理 符號なしの逆位によるソーティング問題に対し、4d(π)回以內の逆位操作系列を多項式時間で計算可能証明上記アルゴリズムで ステップ1 が実行されれば、b(π)は１以上減少。ステップ2が実行されれば、 b(π)は増加

18、せず、次回はステップ1が実行可能。よって、高々 2?b(π) 回の逆位操作により id へ至ることができる。補題1より、 2?b(π) ≦4?d(π),逆位によるソーティング（符號あり）,遺伝子には方向性があるので、方向（符號：+－)を考えた逆位系列を考えるのは妥當逆位操作により、符號も反転符號なしのソーティングはNP困難だが、符號ありのソーティングは多項式時間で解ける,まとめ,最短共通拡大文字列: ハミルトン閉路問題に帰著し、

19、近似逆位によるソーティング: 符號ありは多項式時間で解けるが、符號なしはNP困難（切斷點の導入により近似精度を保証）補足最短共通拡大文字列の近似は 2.5 まで改良 [Haim Kaplan, Shafrir: Inf. Proc. Lett. 2005]　? 2012年に 2+11/23 まで改良[Mucha, Proc. SODA, 2012]最短共通拡大文字列に関連した問題として、Shortest Common Supe