DEIM Forum 2016 G5-3

ランダム仮説下での出現回数分布を利用した散在反復配列の発見
中村 武憲†

中村 篤祥†

工藤 峰一†† 北海道大学大学院情報科学研究科 〒 060–0814 北海道札幌市北区北 14 条西 9 丁目
E-mail: †{takenori,atsu,mine}@main.ist.hokudai.ac.jp
あらまし 生物の DNA の塩基配列には散在して現れる類似配列が多く存在し，それら散在反復配列は遺伝子の発現制御，さらには進化における機能発現に密接に関連しているとされている．散在反復配列の発見に頻出パターンマイ
ニングを用いることは可能であるが，オカレンスの出現確率がパターン長に依存するため、最小サポートを指定する
方法では偶然では起こりえない散在反復配列のパターンを一度に抽出することはできない．本研究では，類似性をア
ライメントスコアにより測り，パターンの出現として局所最適なもののみカウントする頻出パターンマイニング手法
において，最小サポートをランダムシーケンスにおけるパターンの出現回数分布に依存して決める方法を提案し，ヒトゲノムのシーケンスを用いた実験により有効性を示す.
キーワード

頻出パターン, ローカルアラインメント, データマイニング, 最小サポート, ランダムウォーク

1. は じ め に

2. 関 連 研 究

近年，メール文書のようなテキストデータや HTML・XML

反復配列発見手法は大きく”クラスタリングを利用する手法”のような半構造化データ，生物のゲノム配列のような大規模なと”頻出パターンマイニングを利用する手法”に分けられる．

データなど，様々な情報がデータとして蓄積されている．それ

クラスタリングを利用する手法として，シーケンスに対し頻らのデータより有用な知識を得るための分析技術であるデータ

度の高い k-mer(長さ k の文字列) の切り出し，不一致やギャッ

マイニング技術も大幅に進歩しており，中でも頻出するパタープを考慮しつなぎ合わせたものを反復配列候補とし，それら反ンを抽出する頻出パターンマイニングは中心的に扱われている

復配列候補をクラスタリングすることで類似する反復配列候補

手法の 1 つである．本稿では，1 つの文字列に頻出する類似しをまとめて反復配列とする手法が存在する [3]．この手法では，た部分文字列を発見する手法を考える.

k 長の切り出しをつなぎ合わせる際に経験的な知見を利用した生物の DNA の塩基配列には多くの反復配列が存在している．

ヒューリスティクな手法を使用することや，発見される反復配

反復配列には，連続した繰返しである縦列反復配列 (タンデム列がクラスタリング性能に依存すること，反復配列と判断されリピート) と，レトロトランスポゾンと呼ばれる部分の転移にた基準がはっきりしないなどの問題がある．

よっておこる散在反復配列が存在し，それらは遺伝子の発現制

頻出パターンマイニングを利用する手法として，類似性を御に関係し，進化における機能発現に密接に関連しているとさハミング距離やアラインメントスコアを利用して測ることで，れている [2]．

類似反復配列パターンを抽出する手法が提案されている [7] [8]．

散在反復配列の発見手法の 1 つとして，指定した閾値 (最小しかし，反復配列パターンであると判断する上で固定の最小ササポート) 以上出現するシーケンスパターンを列挙するマイニ

ポートを使用しているため，統計的に重要と考えられる長い反ング手法を適用することが可能である [1], [6]．しかし，パター

復配列パターンが出現回数が少ないために検出されないといっン長が増加するにつれてオカレンスの出現確率は小さくなるた

た問題がある．

め，パターン長に合った最小サポートを出現回数の閾値としな

頻出パターンマイニングを利用する手法で，長さの異なるラければ，偶然では起こりえない散在反復配列をもれなく抽出す

ンダムシーケンスにおけるオカレンスの出現確率を考慮して固ることはできない．

定ではなく可変の最小サポートを導入した手法も存在する [6]．

そこで本稿では，パターンの最小長を指定せず，また固定の

しかし，複数のシークエンスに対して可変最小サポートを導入

閾値としての最小サポートを利用しない方法として，類似性をした頻出パターンマイニング法であり，本稿で提案するゲノム

アライメントスコアにより測り，パターンの出現として局所最のような一本の長大なシークエンスに対して可変最小サポート

適なもののみカウントする頻出パターンマイニング手法 [7] にを導入するものではない．与えられたサブシーケンスバターン

おいて，最小サポートをランダムシーケンスにおけるパターン

に対して，１本のシーケンス内におけるオカレンスの頻度分布の出現回数分布に依存して決める方法を提案し，比較実験によの近似値を計算する方法 [4] が提案されているが，頻出パターり有効性を示す.

ンを探す問題への拡張はされていない．

3. 準

備

3. 1 問 題 設 定
Σ を有限集合とし，Σ の要素を文字と呼ぶ．Σ の任意の２文字を発生する情報源の確率モデル S0 および実数 P ∈ (0, 1) に対し，s において極小局所最適なオカレンスが σ(S0 , n, s[h..j], P )回以上出現する s の部分文字列 s[h..j] を列挙せよ．
本稿では，s と同じ文字を発生する情報源の確率モデル S0 と字 x, y に対し，以下の条件を満たすスコア関数 w が定義されして，s における各文字の出現割合をその文字の出現確率とすているものとする．

る無記憶情報源を考える．

SF1 w(x, y) = w(y, x) for all x, y ∈ Σ
SF2 w(x, x) > 0 for all x ∈ Σ
SF3 w(x, y) < 0 for some x, y ∈ Σ

4. 提 案 手 法問題 2 において，パターン候補 s[h..j] 毎に σ(S0 , n, s[h..j], P )文字 s[1], s[2], . . . , s[n] ∈ Σ に対し，その列 s = s[1]s[2] · · · s[n]の値を正確に計算するのは難しいのでパターン長 m には依存を文字列と呼び，n を文字列 s の長さと呼ぶ．長さの等しい２

するがパターンの出現文字には依存しない，σ(S0 , n, p, P ) の最

つの文字列 s = s[1]s[2] · · · s[n]，t = t[1]t[2] · · · t[n] に対し，２

大値 maxp[1..m]∈Σm σ(S0 , n, p, P ) の近似値 σ̂(S0 , n, m, P ) を用

つの文字列の類似スコア S をいるものとする．以下の２ステップで問題 2 を近似的に解く．

S(s, t) =n∑（ 1 ） パターン長 m 毎の σ̂(S0 , n, m, P ) の値を計算する．

w(s[i], t[i])i=1と定義する．
文字列 s[1]s[2] · · · s[n] の i(>= 1) 番目から j(<= n) 番目まで（ 2 ） s において極小局所最適なオカレンスが σ̂(S0 , n, m, P )回以上出現する s の部分文字列 s[h..j] を列挙する．

4. 1 パターン長毎の最小サポートに使う値の計算
パターン長 m 毎の最小サポートに使う値 σ̂(S0 , n, m, P ) をの部分文字列 s[i]s[i + 1] · · · s[j] を s[i..j] と表記する．ただし，

以下のように計算する．

s[i + 1..i] は空文字列を表すものとする．文字列 s から文字列（ 1 ） スコア関数 w として以下のものを使う．

{

p[1..m] に似ている部分を抽出する際，本質的に同じ領域を重ねて抽出することを少なくするために以下に定義される極小局

w(x, y) =所最適なオカレンスのみを取り出すことを考える．

+a(x = y : match)

−b

(x =
| y : mismatch)(1)［定義 1］（ [7] のギャップを許さないバージョン） 以下の条件

ただし，a, b は a < b を満たす自然数 (正の整数) とする．こを満たす文字列 s[1..n] の部分文字列 s[j..j + m − 1] を，文字のスコア関数におけるパターン p[1..m] の (極小) 局所最適な列 p[1..m] の極小局所最適なオカレンスと呼ぶ．

オカレンス s[j..j + m − 1] は，任意の 1 <= h <= m に対し，

CS1 S(p[1..h], s[j..j + h − 1]) > 0 for all 0 < h <=m
CS2 S(p[1..m], s[j..j + m − 1]) > S(p[1..h], s[j..j + h − 1])for all 0 <=h<m
論文 [7] では，以下のような頻出パターンマイニング問題を

s[j..j + h − 1] が p[1..h] と，また，s[j + h − 1..j + m − 1] がp[h..m] と 100 × b/(a + b)%より多くの位置で一致していることを保証する．
（ 2 ） s[1..n] における各文字の出現割合をその文字の出現確扱っている．

率とする無記憶情報源 S0 から発生した１文字 x がパターンの［問題 1］ 与えられた文字列 s，スコア関数 w，自然数 σ に対ある位置の１文字 y と一致する確率 Py は，y の S0 における発し，s において極小局所最適なオカレンスが σ 回以上出現する

生確率に依存する．計算簡略化のためどの文字 y に対しても一s の部分文字列 s[h..j] を列挙せよ．

致確率を Pmax = maxy∈σ Py で計算する．これを使うと，S0 か

散在反復配列は長いものは出現回数が２回でも，偶然起こっら発生した文字列 t の任意の位置 j からの部分列 t[j..j + m − 1]

たとは考えにくいので抽出に意味があり，逆に短いものは出現が長さ m のパターンの極小局所最適なオカレンスとなってい

回数が 10000 回でも偶然に起こる確率が高い場合には抽出する

る確率の最大値 PLOOMax (m) を計算できる．この計算法に関価値はない．問題 1 のマイニングでは，最小サポート σ を固定

しては次小節で詳しく説明する．

するため，散在反復配列としてあまり意味のない短いものが多（ 3 ） PLOOMax (m) を 利 用 し て σ(S0 , n, p, P ) の 最 大 値

く抽出されたり，意味がある出現回数が σ より少ない長い配列

maxp[1..m]∈Σm σ(S0 , n, p, P ) の近似値 σ̂(S0 , n, m, P ) を計算が抽出されないという問題がある．

す る ．ま ず，S0 か ら 発 生 す る 長 さ n の 文 字 列 t に 対 し ，

そこで小さな確率 P を指定して，対象文字列 s と同じ長さ n

j = 1, 2, . . . , n − m + 1 に対し部分列 t[j..j + m − 1] が長さ m ののランダムシーケンスにおいて ℓ(p, P, n) 回以上起こる確率がパターンの極小局所最適なオカレンスとなる事象が独立であるとP 以下となるような最小サポート ℓ(p, P, n) をパターン p 毎に仮定すると出現回数 X は二項分布 B(n − m + 1, PLOOMax (m))

設定する頻出パターンマイニング問題を考える．情報源 S0 かに従う．m は n に比べて非常に小さい (m ≪ n) という仮ら発生した長さ n の文字列に対し，文字列 p の極小局所最適な定の下に B(n − m + 1, PLOOMax (m)) は B(n, PLOOMax (m))

オカレンスが m 回以上生起する確率が P 以下であるような最で近似できる．更に n が大きいときには B(n, PLOOMax (m))

小の m を σ(S0 , n, p, P ) と表記すると，本稿で考えるマイニン

は ポ ア ソ ン 分 布 P o(nPLOOMax (m)) で 近 似 で き る ．そ こ でグ問題は以下のように述べることができる．

X ∼ P o(nPLOOMax (m)) とし，［問題 2］ 与えられた文字列 s[1..n]，スコア関数 w，s と同じ文

σ̂(S0 , n, m, P ) = min{h : P (X >= h | X > 0) <
= P}
h∈N

で計算する．

(証明) 任意の p ∈ Σm に対して
∑ ∏
∏
Pp[h]
(1 − Pp[h] )F ∈F (p) h̸∈F

<
=

∑

h∈F

∏

∏

Pmax

F ∈F (p) h̸∈F

(1 − Pmax )

(2)

h∈F

が成り立つことを示す．Pp[1] = · · · = Pp[m] = Pmax の場合(2) は等号で成立する．|{i : Pp[i] < Pmax }| = k を満たす任意の文字列 p[1..m] に関して不等式 (2) が成立していると仮定す
る．このとき，|{i : Pp[i] < Pmax }| = k + 1 を満たす任意の文
字列を p[1..m] とする．Pp[i] < Pmax を満たす i 番目の文字を
図1

最小サポートの計算

σ̂(S0 , n, m, P ) は PLOOMax (m)) が小さいほど小さくなる．こ
こで条件付き確率 P (X >= h|X > 0) を考えたのは，パターンの候補を s の部分列に限っているため，s においてどの候補もPy = Pmax を満たす文字 y に置き換えた文字列を p′ とする．
|{i : Pp′ [i] < Pmax }| = k が成り立つので仮定より∏∑ ∏(1 − Pp′ [h] )Pp′ [h]F ∈F (p′ ) h̸∈F<=

P (X >= h)
P (X > 0)e−λ ∑ λi1 − e−λ
i!
i=h
(
)
h−1
∑ λi
1
−λ
=
1
−
e
1 − e−λi!
i=0∞

PLOOMax (m)) が減少し，その結果 σ̂(S0 , n, m, P ) の値が小さくなる．したがって σ̂(S0 , n, m, P ) >= 3 となる最大の m まで
σ̂(S0 , n, m, P ) を計算し，それより大きな m に関しては最小サ

h∈F

Pmax

∑

<
=

h∈F

∏

F ∈F (p′ ) h̸∈F含まれる任意の集合 G(⊂=F ) に関して G ∈ F (p) が成り立つ．
したがって
∑ ∏

∑

=

Pp[h]

∏

∏

Pp[h]

∏

∑

+

場合，t の部分列 t[j..j + m − 1] がパターン p[1..m] の極小局所

∑

=

∏

i∈F ∈F (p) h̸∈Fp[1..m] の極小局所最適なオカレンスとなる場合の不一致位置+の集合の集合族を F (p) とすれば，t[j..j + m − 1] がパターン

∏

∏

Pp[h]

∑

∑

<
=

∏

と書ける．このとき，以下の定理が成り立つ．

∑

=

∏

∑

+
max PLOO (S0 , p)

∑

+
m−k
|{F ∈ F (p) | |F | = k}|Pmax(1 − Pmax )kk=0

ただし，|{·}| は集合 {·} の要素数を表すものとする．

h∈F

∏

∑

∏

F ∈F (p′ ) h̸∈FPp′ [h]h∈F(1 − Pp[h] )Pp′ [h]∏(1 − Pp′ [h] )h∈F(1 − Pp′ [h] )
∏
∏

∏

∏
h∈F

h̸∈F ∪{i}Pp′ [h]∏(1 − Pp′ [h] )h∈FPp′ [h]i̸∈F ∈F (p′ ),F ∪{i}̸∈F (p′ ) h̸∈F

=

Pp[h]

(1 − Pp′ [h] )i̸∈F ∈F (p′ ),F ∪{i}∈F (p′ ) h̸∈F

p∈Σm

=

∏

∏

(1 − Pp[h] )h̸∈F ∪{i}Pp′ [i]Pp′ [h]i∈F ∈F (p′ ) h̸∈F

［定理 1］

m∑∏i̸∈F ∈F (p′ ),F ∪{i}̸∈F (p′ )h∈F∏(1 − Pp[h] )h∈F \{i}∑+(1 − Pp[h] )(1 − Pp[h] )

h∈F

Pp[i]

i∈F ∈F (p′ ) h̸∈F

F ∈F (p) h̸∈FPp[h]h∈F \{i}Pp′ [h]∏h∈Fi̸∈F ∈F (p),F ∪{i}̸∈F (p)

は

∏

Pp[h]

i̸∈F ∈F (p),F ∪{i}̸∈F (p) h̸∈Fする位置 h ∈ {1, . . . , m} のみで決まるので，t[j..j + m − 1] が

Pp[h]

∏

i̸∈F ∈F (p),F ∪{i}∈F (p) h̸∈F

計算する方法を示す．(1) で定義されるスコア関数 w を用いる∏

(1 − Pp[h] )

h∈F

∑

+

(1 − Pp[h] )h∈Fi∈F ∈F (p) h̸∈F

最適なオカレンスとなっている確率の最大値 PLOOMax (m) を∑(3)

小局所最適なオカレンスの性質より，F ∈ F (p) であれば F にからの部分列 t[j..j + m − 1] が長さ m のパターンの極小局所

PLOO (S0 , p) =(1 − Pp′ [h] )h∈Fを証明すれば，p に関しても (2) が成り立つことが示せる．極S0 から発生した文字列を t とする．文字列 t の任意の位置 j

p[1..m] の極小局所最適なオカレンスとなる確率 PLOO (S0 , p)∏Pp′ [h]F ∈F (p) h̸∈F

最適なオカレンスとなっているか否かは一致 (t[j + h] = p[h])(1 − Pmax )h∈FF ∈F (p) h̸∈F

ポートを 2 に設定する．

4. 2 極小局所最適なオカレンスとなる確率の最大値の計算∏が成立する．よって∏∑ ∏(1 − Pp[h] )
Pp[h]

=

で 計 算 で き る ．一 般 に ，パ タ ー ン 長 m が 長 く な る と 確 率∏F ∈F (p′ ) h̸∈F

１回は出現するからである．実際の P (X >= h|X > 0) の値はP (X >= h|X > 0) =∑(1 − Pp′ [h] )∏h∈F(1 − Pp′ [h] )が成り立つ，つまり不等式 (3) が示された．よって |{i : Pp[i] <得ない. 求める場合の数は，次が不一致だと「位置 i − b から

Pmax }| = k + 1 を満たす任意の文字列を p[1..m] に対して不残り (h − (i + a))/a = (h − i)/a − 1 回のランダムウォークで，

等式 (2) が成り立つ．したがって数学的帰納法により任意の

途中で (0, h − (a + b)k) の範囲から出ずに (h − (i + a))/a =p ∈ Σm に関して不等式 (2) が成り立つことが示された．

(h − i)/a − 1 回目に h − (a + b)k に到達する場合の数」と等し□くなるが，これは αh−(a+b),i−b,k−1 (「位置が i − b のとき，残り((h − (a+b)) − (i − b))/a = (h−i)/a−1 回のランダムウォーク

定理 1 より

PLOOMax (m) =m∑

で，途中で (0, (h − (a+b)) − (a+b)(k − 1)) = (0, h−(a+b)k)m−k|{F ∈ F (p) | |F | = k}|Pmax(1−Pmax )kk=0の範囲から出ずに ((h − (a + b)) − (i − b))/a = (h − i)/a − 1
回目に (h − (a + b)) − (a + b)(k − 1) = h − (a + b)k に到達で計算できる．|{F ∈ F (p) | |F | = k}| の値の計算法を考える．

|{F ∈ F (p) | |F | = k}| は，ある長さ m の文字列 t[1..m] が文字列 p[1..m] の極小局所最適なオカレンスになっている場合する場合の数」) に等しい．よって αh,i,k = αh−(a+b),i−b,k−1が成り立つ．

b+1 <=i<= h − (a + b)k − a − 1 の場合は，次が一致でも不の各位置 i の文字 t[i], p[i] の一致 (C)，不一致 (M ) のシーケ

一致でも問題がないため，一致した場合の場合の数 αh,i+a,k とンスパターンで不一致がちょうど k 回になるものの数である．

不一致である場合の数 αh−(a+b),i−b,k−1 の和となる．

不一致の位置の集合 F ∈ F(p) はそのようなシーケンスパター

よって αh,i,k = αh,i+a,k + αh−(a+b),i−b,k−1 が成り立つ. □ンの１つの表現であるが，ここでは文字 C と U の長さ m のシーケンスでパターンを表現する．スコア関数 (1) を使う場
合，一致・不一致のシーケンスパターンが同じで文字列 t[1..m]，′′t [1..m] の p との類似スコアは同じ (S(t, p) = S(t , p)) になる．

定理 2 の漸化式を用いて，以下のような動的計画法によりあ3maる範囲の 1 <=m<= M, 0 <=k<= a+b に対して O(M ) の計算量

刻 i の位置は類似スコア S(p[1..i], t[1..i]) と一致する．時刻 i にで αma,0,k の値を求めることが可能である．
Step 1 1 <=h<= M a，0 <=i<= h を満たす整数のペア (h, i) に対し αh,i,0 を定理 2 の漸化式を用いて設定する．k = 1 とする．
Step 2 (a + b)k + 1 <= h <= M a の各々の h に対し, i =おいては，t[i] が p[i] と一致していたら +a 不一致であれば −bh − (a + b)k − a を満たす i に対して定理 2 の漸化式を使って数直線上を時刻 0 に位置 0 におり，時刻 i + 1 に時刻 i の位置
から w(p[i + 1], t[i + 1]) だけ移動するウォークを考えると，時移動する．

αh,i,k = αh−(a+b),i−b,k−1 に設定する．

不一致の数が k のとき，最終的な類似スコアは (m−k)a−kb =Step 3 (a + b)k + 1 <= h <= M a の各々の h に対し, i =ma − (a + b)k である．今，αh,i,k を現在の位置が i(<= h) のとh − (a + b)k − a − 1, h − (a + b)k − a − 2, . . . , b + 1 のき，残り (h − i)/a 回の移動で，途中で (0, h − (a + b)k) の範

各々の i に 対 し て 大 き い 方 か ら 定 理 2 の 漸 化 式 を 使って囲から出ずに (h − i)/a 回目に h − (a + b)k に到達する一致・

αh,i,k = αh,i+a,k + αh−(a+b),i−b,k−1 に設定する．
Step 4 (a + b)k + 1 <= h <= M a の各々の h に対し, i =不一致のシーケンスパターンの数を表すものとする. このとき

αma,0,k = |{F ∈ F (p) | |F | = k}|が成り立つ．αh,i,k に関して，以下の定理が成り立つ．
［定理 2］ 以下の漸化式が成り立つ．

b, b − 1, . . . , 0 の各々の i に対して大きい方から定理 2 の漸化式を使って αh,i,k = αh,i+a,k に設定する．
Ma
Step 5 k + 1 > a+b
であれば停止．そうでなければ k = k + 1

として Step 2 へとぶ．

4. 3 頻出近似パターンの列挙
αh,i,k =
k = 0 の場合





1
((h − i) は a の倍数)





0
((h − i) は a の非倍数) k > 1 の場合
=

α
(i <

h,i+a,k
= b)




 αh,i+a,k + αh−(a+b),i−b,k−1





(b + 1 <= h − (a + b)k − a − 1)
=i<



αh−(a+b),i−b,k−1(i >= h − (a + b)k − a)

与えられた文字列 s において，任意の長さ m > 0 に対し
極小局所最適なオカレンスが σ̂(S0 , n, m, P ) 回以上出現する sの部分文字列 s[j..j + m − 1] を列挙する．O(n3 ) 時間 O(n2 )空間のアルゴリズム ESFLOO-0G.C [7] を用いて列挙する．ただし，最小サポートは固定ではなくパターン長 m に依存する

σ̂(S0 , n, m, P ) を用いる．極小局所最適なオカレンスが頻出するパターンは逆単調性をもたないが，CS1 のみを満たす部分列の数でカウントすると逆単調性をもつので，CS1 を満たす部分列の数が２以上ある場合は探索を打ち切らずより長いパターンのチェックを続けることにより，もれなくすべての頻出パター(証明) k = 0 の場合における αh,i,0 = 1 は定義より明らかでンを列挙する．

ある.

k>= b のときは，次が不一致であると 0 以下
= 1 とする．i <になってしまうためしなければ局所最適性を満たさない．よって αh,i,k = αh,i+a,k となる．i = h − (a + b)k − a の場合は，一致すると h − (a + b)k に到達してしまうため不一致しかあり

5. 実

験

ヒトゲノムの２１番染色体で本手法の有効性を検証する．以下では Σ = {A, C, G, T } とし，以下のスコア関数 w を用いる
ものとする．

{w(x, y) =+1(x = y : match)

−4

(x =
| y : mismatch)(4)

このスコア関数において類似と判断される２つの文字列は80%より多くの位置で文字が一致していることに注意されたい．
まず，無記憶情報源から発生するシーケンスにおいて各位置独立であるという仮定の影響について実験を行い，その後本手法をヒトゲノムに適用した実験を行う．

5. 1 独立性の仮定の影響
図 3 m=11 における比較．

提案手法では，無記憶情報源から発生するシーケンスのオカ
レンスの発生が各位置で独立であるという仮定を行いさらに２項分布をポアソン分布で近似してパターンのオカレンスの出現
頻度分布を推定するが，そのように推定した分布が実際の分布とどのくらい異なるかを調べる．
無記憶情報源から発生する文字列の長さは 10, 000, 000 とする．以下の２つの条件下で実験を行う．
（ 1 ） 条件 1 各文字の出現確率が等確率 (PA = PG = PC =PT = 0.25)（ 2 ） 条件 2 各文字の出現確率が 21 番染色体と同じ (PA =0.29689322, PG = 0.20436933, PC = 0.20395605, PT =0.29478140)
条件 1 の場合は，長さ m の文字列の極小局所最適なオカレ

図 4 m=7 における比較．

ンスとなる確率はどの長さ m の文字列に対しても同じである．
そこで，4 文字が等確率で発生する無記憶情報源から出力された長さ 10, 000, 000 の文字列において，各位置からの長さ m の文字列 (10, 000, 000 − m + 1) 個の各々をパターンとした場合の，極小局所最適なオカレンスの出現回数を調べた．図 2，図3 にそれぞれ m = 7，m = 11 の結果を示す．赤のプロットラ
インは提案手法による近似値を表し，青のプロットラインは出
現割合 (出現回数/(10, 000, 000 − m + 1)) を表す．

図 5 m=11 における比較．

は実測値を表す．
近似値と実測値との間に少し誤差がみられる．平均にはほとんど差がないが，実測値の方が分散が大きくなっている．これは’A’ の連続をパターンとした場合を考えているため，パター
図 2 m=7 における比較．

ンが連続して起こりやすくなっていることによるものと考えられる．文字列長 n に対して nPLOOMax (m) がある程度大きい場

近似値は，実測値とほぼ一致していることがわかる．
条件 2 の場合は，PLOOMax (m) は A のみからなる文字列がパターンの場合の極小局所最適なオカレンスの出現確率である．
そこで各文字の出現確率が条件 2 の無記憶情報から出力される
長さが 10, 000, 000 の文字列を 10, 000 本生成し，各文字列において長さが m の連続する A をパターンとした場合の極小局
所最適なオカレンスの出現回数を調べた．図 4，図 5 にそれぞれ m = 7，m = 11 の場合の結果を示す．それぞれ赤のプロッ
トラインは提案手法による近似値を表し，青のプロットライン

合は中心極限定理より正規分布で近似できるため，論文 [4] のように正規分布で近似し，隣接文字列との共分散を考慮に入れて計算した分散を用いて分布を近似することにより，より誤差の少ない近似が可能になると考えられる．

5. 2 ヒトゲノムによる実験
ヒトゲノムの 21 番染色体に提案手法を適用し，リピートとして既にデータベースに登録されているものとの比較を行った.

21 番染色体は約 4500 万塩基対からなっているが，不定を意味

する’N’ が連続する領域を多く含むため，それらが繰り返し領域として抽出されないように 10 回以上連続する’N’ を取り除いてそこで切断して複数のシーケンスに分割し，各々のシーケン提案手法により検出できた．
以下図 7 に提案手法のみがカバーする領域に現れたパターンのサイズの分布を示す．

スのオカレンスカウントの合計を全体のオカレンスカウントとした. ’N’ を取り除いた結果，長さの合計は約 3510 万塩基対に減少した．
問題 2 において s を 21 番染色体の塩基配列とし，P =100 × 10−23 に設定して，提案手法により頻出近似パターンを列挙した．
局所最適なオカレンスに対する頻出近似マイニングは逆単調性を満たさないことから，局所最適なオカレンスの数は，パターンが長くなっても増えることがあるが，左右どちらに長くしても局所最適なオカレンスの数が少ないものしか存在しないパターンを閉パターンと定義し，閉パターンのみ列挙した．左右両方の伸張に関して同時にチェックしながら列挙は難しいた

図 7 提案手法のみがカバーする領域に現れたパターンサイズの分布

め，まずは右端を延ばしながら右伸張のチェックを行って列挙
し，列挙されたものに関して左伸張のチェックを別に行うこと

また図 8 に Repbase に反復配列として登録されている領域

により閉パターンのみに絞り込んだ．さらに，相補シーケンス

で，かつ提案手法でカバーできなかった領域に現れたパターン

も頻出パターンになっているものに関しては，頻度の多い方ののサイズ分布を示す．

み残して少ない方は削除した．その結果，4, 819, 759 パターンが抽出された．
抽出されたパターンを用いて以下のように 21 番染色体の各位置に情報を埋め込んだ．各位置において，そこから始まる抽出されたパターンまたはその相補パターンのオカレンスで最長なものでかつ，どのパターンの他のオカレンスにも包含されていないオカレンスの，パターン ID とオカレンス長をその位置の情報として埋め込んだ．その結果，全体の長さ約 3510 万の位置のうち，2, 039, 898 の位置から始まるオカレンスの情報が埋め込まれ，それらのオカレンスに覆われている部分は全体の60.001%であった．
データベースに登録されている既知の散在反復配列として，

図8

既知の手法のみがカバーする領域に現れたパターンサイズの分布

Genetic Information Research Institute の反復配列データベースである RepbaseU pdate [5] に登録されている反復配列のオカ
レンスを Repeat Masker (RM) を用いて抽出したものを用いた．
．反復配列のオカレンスにより覆われている部分は全体の45.196%であった．
図 6 に詳細を示す．

図 7 より，提案手法のみがカバーした領域はパターン長の小さいパターンが多くを占めている．一方図 8 より，Repbase に登録されている反復配列のオカレンスがカバーする領域は提案手法のみがカバーした領域におけるパターンサイズと比べ大きなパターン長のパターンが多く検出された．これは，本稿において文字列とパターン間におけるギャップを許していないことから，パターン長が大きくなるにつれてオカレンスと判断されづらくなるためであると推測される．
次に提案手法が反復配列と判断した領域に関して考察を行う.
表 1，表 2 に

図6

提案手法のオカレンスと Repbase+RM のオカレンスの領域の比較提案手法が反復配列と判断した領域

の詳細

を示す.
提案手法によって高いカバー率を得られた反復配列に関して，

Repbase Update に登録されている反復配列の出現回数と，提２１番染色体領域全体の内、提案手法のみにカバーされた領域
は 27.2%，Repbase に登録されているリピートのオカレンスであるが提案手法によりカバーされなかった領域は 12.4%，Rep-base に登録されているリピートのオカレンス領域の内 72.3%が案手法によるパターンの出現回数が非常に近い値になっている．
これは断片的な短いパターンで網羅的にカバーしているのではなく，データベースに登録されている反復配列のオカレンスと表 1 領域ごとのカバー率（降順上位 25 種)

しない反復配列も含まれている．そのため，反復配列領域を提

反復配列名

カバー率

オカレンス数
Repbase+RM 提案法

CER Satellite
L1PA2 LINEL1SVA D RetroposonSVA
L1PA4 LINEL1
THE1 int LTRERVL MaLR
ALRAlpha Satellitecentr
L1PA3 LINEL1
THE1A int LTRERVL MaLR
L1PA5 LINEL1
L1PA7 LINEL1
LTR22C2 LTRERVK
L1PA6 LINEL1
L1P2 LINEL1
L1HS LINEL1
THE1B int LTRERVL MaLR
L1PA8A LINEL1
AluYk11 SINEAlu
AluYa8 SINEAlu
AluY SINEAlu
AluYa5 SINEAlu
AluYk2 SINEAlu
AluYk3 SINEAlu
AluSg7 SINEAlu
AluYm1 SINEAlu
AluYb8 SINEAlu

99.9795%
99.9349%
99.9328%
99.8761%
99.8748%
99.8721%99.8720%99.8462%
99.8253%
99.8077%
99.7963%
99.7890%
99.7770%
99.7709%99.7432%
99.6861%
99.6725%
99.6678%99.6601%99.6553%
99.6422%99.6388%
99.6317%99.6187%
99.6184%

4
56
7
117
6
7
100
31
125
164
2
49
13
12
69
26
3
1
1194
30
90
71
78
106
41

4
58
7
121
6
7
103
34
133
183
2
54
13
12
81
30
3
1
1197
30
90
71
78
107
43

案手法では反復配列と判断できなかった可能性がある.

6. ま と め
本稿では，極小局所最適なオカレンスとなる確率を動的計画法を用いて効率的に計算し，その確率を用いてパターン長 m に依存する最小サポート σ̂(S0 , n, m, P ) を設定することで，従来の頻出パターンマイニングの問題点の改善を図った．
提案手法によって計算した最小サポートを，類似度をアライ
ンメントスコアで測る従来法に適用することで，既知の反復配列とされている領域の約 72.306 %を，事前情報無しで，かつ短い断片的なパターンで網羅的にカバーすることなく，正しく
反復配列領域であると判断した上で検出できた．
今後の課題として，文字列とパターンの間にギャップを考慮することが挙げられる．本稿ではギャップを許していないため，
提案手法のみがカバーする領域においてパターン長の小さいパ
ターンが多くを占める結果となった．ギャップを考慮した極小
局所最適なオカレンスとなる確率の最大値を導入することで，パターン長の小さいパターンのオカレンスに過敏に反応してしまうことの少ない最小サポートを設定できると考えられる．ま表 2 領域ごとのカバー率（降順下位 25 種)
反復配列名

カバー率

SSU rRNA Hsa rRNA
LTR22A LTRERVKHERVE int LTRERV1
MamRep488 DNAhAT Tip100
CR1 16 AMi LINECR1
MER91B DNAhAT Tip100
UCON28b Unknown
L1P3b LINEL1
UCON97 DNA
tRNA Arg AGA tRNA
X34 DNA DNA
MER68B LTRERVLtRNA Met tRNA
UCON69 DNAhAT
U4 snRNA
Eulor6A DNA
MER133B DNA
CR1 13 AMi LINECR1
LTR103b Mam LTRERV1
Eutr2 DNAtRNA Gly GGY tRNA
L1M3de LINEL1tRNA Cys TGY tRNA
tRNA Lys AAG tRNA

21.6216%
21.5536%
21.2851%
21.2329%
21.0256%
20.8672%
19.4915%
19.4805%
18.8679%
18.4211%18.3908%
18.1992%
18.1818%
17.5258%
15.4930%
14.2857%
13.7255%
12.5786%
11.3636%9.3750%8.4906%0.0000%0.0000%0.0000%

た，既知の反復配列領域で，かつ提案手法で反復配列として検オカレンス数
Repbase+RM 提案法

2
2
1
3
1
6
1
2
1
1
2
3
1
1
1
1
1
1
1
1
2
1
2
1

13
17
8
9
4
15
2
3
1
2
5
17
1
2
2
3
1
2
1
1
2
0
0
0

ほぼ同じ領域を提案手法で見つけた反復配列のオカレンスと判断できていることを意味している．
一方でカバー率が非常に低い反復配列領域も存在する．これは染色体全体でその反復配列の出現回数が非常に少ないか，
もしくは 1 度しか出現しないような反復配列であることがカ
バー率が低くなってしまった原因の 1 つであると考えられる.

Repbase Update に登録されている反復配列はヒトゲノム全体
における反復配列であり，他の染色体には複数回出現する反復配列であっても 21 番染色体には少数，もしくは 1 度しか出現出できなかった領域に関して，検出できなかった理由の追求と，それらの領域に関する調査が必要である．

謝

辞

本研究に関して大変有意義なコメントいただいた北海道大学の有村博紀教授に感謝いたします．本研究の一部は，JSPS 科
研費 25280079 の助成を受けたものです．

文

献[1] R. Agrawal and R. Srikant. Mining sequential patterns. In
Proceedings of the 11th international conference on Data
Engineering (ICDE1995), pages 3–14, 1995.
[2] G. J. Faulkner et al. The regulated retrotransposon transcriptome of mammalian cells. Nature Genetics, 41:563–
571, 2009.
[3] M. Ghodsi, B. Liu, and M. Pop. Dnaclust: accurate and efficient clustering of phylogenetic marker genes. BMC Bioinformatics, 12(1):1, 2011.
[4] Robert Gwadera, Mikhail J. Atallah, and Wojciech Szpankowski. Reliable detection of episodes in event sequences. In Proceedings of the 3rd international conferenceon Data Mining (ICDM2003), pages 67–74, 2003.
[5] J. Jurka, VV. Kapitonov, A. Pavlicek, P. Klonowski, O. Kohany, and J. Walichiewicz. Repbase update, a database of
eu-karyotic repetitive elements. Cytogenet Genome Res.,
110(1-4):462–467, 2005.
[6] C. Low-Kam, C. Raissi, M. Kaytoue, and J. Pei. Mining statistically significant sequential patterns. In Proceedings of the 13th international conference on Data Mining(ICDM2013), pages 488–497, 2013.
[7] A. Nakamura, I. Takigawa, H. Tosaka, M. Kudo, and
H. Mamitsuka. Mining approximate patterns with frequentlocally optimal occurrences. Discrete Applied Mathematics,
200:123–152, 2016.
[8] F. Zhu, X. Yan, J. Han, and P.S. Yu. Eﬃcient discovery

of frequent approximate sequential patterns. In Proceedings of the 7th international conference on Data Mining(ICDM2007), pages 751–756, 2007.