九州大學(xué)集中講義

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

2、最短共通拡大文字列,最短共通拡大文字列問(wèn)題 (Shortest Superstring),入力: 文字列集合：出力: すべての si の拡大文字列となっており、かつ、長(zhǎng)さが最短の文字列 sOPT,この問(wèn)題の場(chǎng)合、解は必ず存在,s は t の拡大文字列 ? t は s の部分文字列ovlp(si,sj): si=sa?sb, sj=sb?sc を満たす最長(zhǎng)の 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,,最短共通拡大文字列： 基本アイデア,アイデア：　巡回セールスマン問(wèn)題に変換,命題： s1,s2,…,sn が sOPT 中でこの順?lè)藖Kぶと次の式が成立,最短共通拡大文字列：

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

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

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

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

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

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

10、 が成立,証明： |ovlp(r1,r2)| ≧ w(c1) + w(c2) を仮定し、矛盾を?qū)Г?p1 を長(zhǎng)さ w(c1) の ovlp(r1,r2) の接頭辭とすると　ovlp(r1,r2)は p1 ∞の接頭辭。p2 を長(zhǎng)さ 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 ∞ の部分文字列。よって、補(bǔ)題1から、 c1,c2 中のすべての頂點(diǎn)を含む重み |p1| 以下の閉路が存在することになり矛盾。,,近似率の解析 （３）,定理： 最短共通拡大文字列問(wèn)題に対して、最適解の4倍以?xún)?nèi)の長(zhǎng)さの

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

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

14、 |πi-πi-1|≠1 となる πi, πi-1 の境界b(π): π における切斷點(diǎn)の個(gè)數(shù)減少斷片: π における、値が１ずつ減少する長(zhǎng)さ2以上の部分列,例π=(0,1,4,6,5,2,3,7) の切斷點(diǎn)は (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) は極大な減少斷片,補(bǔ)題1　 b(π)/2 ≦ d(π) ≦ n証明1回の逆位操作により切斷點(diǎn)の個(gè)數(shù)は高々2個(gè)しか減らないので b(π)/2 ≦ d(π) ?！(π) ≦ n　の証明は宿題,逆位操作の検出,補(bǔ)題2 π が減少斷片を含む時(shí)、b(π) を減らす逆位操作が存在証明　以下のアルゴリズムにより逆位操作を検出1. 右端が最小である極大減少斷片 s を見(jiàn)つけ、右端の値を k とする2. π における k-1 の位置を見(jiàn)

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

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

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

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