II - 京都大学

生物情報ソフトウェア特論
（4）配列解析II
阿久津達也
京都大学化学研究所
バイオインフォマティクスセンター
講義予定












第１回: 文字列マッチング・データ構造
第２回：たたみ込みとハッシュに基づくマッチング
第３回：近似文字列マッチング
第４回：配列解析
第５回：木構造の比較：順序木
第６回：木構造の比較：無順序木
第７回：文法圧縮
第８回： RNA二次構造予測
第９回：タンパク質立体構造の予測と比較
第１０回：固定パラメータアルゴリズムと部分k木
第１１回：グラフの比較と列挙
第１２回：ニューラルネットワークの離散モデル
最短共通拡大文字列
最短共通拡大文字列問題 (Shortest Superstring)
入力: 文字列集合： S  {s1 , s2 ,, sn }
出力: すべての 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 中でこの順番に並ぶと次の式が成立
| sOPT || pref ( s1 , s2 ) |  | pref ( s2 , s3 ) |  
 | pref ( sn , s1 ) |  | ovlp ( sn , s1 ) |
最短共通拡大文字列：巡回セールスマンへの帰着
１． 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  (vi1  vi2    vil  vi1 ) に対し、
a (c) = pref(si , si )× pref(si , si ) pref(si , si )× pref(si , si )
s (c) = a (c)× si
1
2
2
3
l-1
l
l
1
1
と定義し、 si1 を 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) ≧ w(c2)より、
c2 中のすべての文字列は p1 ∞ の部分文字列。また、 c1 中のすべての文字列も
p1 ∞ の部分文字列。よって、補題1から、 c1,c2 中のすべての頂点を含む重み |p1|
以下の閉路が存在することになり矛盾。
近似率の解析（３）
定理：最短共通拡大文字列問題に対して、最適解の4倍以内
の長さの共通拡大文字列を多項式時間で計算可能
証明： w(C)=Σi=1…kw(ci) とすると次式が成立。
k
|  (C ) | w(C )   | ri |
i 1
一般性を失うことなく r1, …, rk はSOPTにこの順番で出現すると仮定。
r1, …, rkのSCSの長さは|SOPT|以下なので、補題2より次式が成立。
k
k 1
k
k
i 1
i 1
i 1
i 1
| S OPT |   | ri |   | ovlp (ri , ri 1 ) |   | ri |  2 w(ci )
よって、この式と w(C)≦|SOPT| から次式が成立。
k


|  (C ) |  w(C )   | ri |  | SOPT |   | SOPT | 2 w(ci )   4 | SOPT |
i 1
i 1


k
逆位によるソーティング
逆位によるソーティング（符号なし）
Sorting by Reversal
入力: 置換 π=(π1,π2,・・・,πn)
出力: π を 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]
ソーティング問題はコピーや移動を許したものなど、様々な拡張がある

Download Report