DEIM Forum 2013

E5-3

異なる尺度を持つ類似文字列検索が最小汎化集合抽出に与える影響
森近

昭紀

北上

始

森

康真

広島市立大学大学院情報科学研究科〒731-3194 広島市安佐南区大塚東三丁目４番１号
E-mail: mw67033@edu.ipc.hiroshima-cu.ac.jp, {kitakami,mori}@hiroshima-cu.ac.jp
あらまし
配列データベースに対して類似文字列検索を行うと，類似する文字列の集合，すなわち，ミス
マッチクラスタが得られるが，ミスマッチクラスタから抽出される規則性の精度等は，類似文字列検索で利用される尺度（文字列間の距離）の定義の違いにより左右される．本研究では，この尺度として，編集距離とハミング距離の 2 種類をとりあげ，最小汎化集合（正規表現）を規則性として抽出し，その精度等を評価する．具体的には，それぞれの尺度をもつ類似文字列検索手法に対する最小汎化集合を抽出し，支持数に関して上位にランキングされた汎化配列パターンの精度等を評価し，2 種類の尺度の違いによる影響を比較・考察する．
キーワード
データマイニング, 配列データベース, バイオインフォマティクス, 正規表現, ランキング

1. はじめに類似文字列検索は，テキストデータベースや配列データベースから類似する部分文字列の検索をさし，Web 文書，オンライン文書，分子配列デー
タなどに対する情報検索をはじめとし，クラスタ
リングや配列データマイニングなどの多くの分野で重要な要素技術である．
類似文字列検索を行うことで，検索結果として，非常に多くの類似した部分文字列を得ることができる．この得られた部分文字列の集合をミスマッ
チクラスタと呼ぶ．このミスマッチクラスタをユーザーが目で直接見て，規則的な特徴を見つけ出し把握することは，膨大なコストがかかってしまい，極めて困難なことである．そこで，ミスマッ
チクラスタから最小汎化集合と呼ばれる，極大な汎化配列パターンの集合と汎化できなかった部分
文字列の集合とを抽出する研究が行われている．
最小汎化集合を抽出できれば，ユーザーは，(1)曖
昧な問合せ処理の結果として得られたすべての部
分文字列を閲覧，分析の手間から解放され，(2)部
分文字列の規則的な変化の様子を理解できる．例
えば，アミノ酸配列データを用いた実験において，ミスマッチクラスタから最小汎化集合を抽出することで，汎化配列パターンを支持数でランキング
すると，生物学的な機能をもつモチーフと呼ばれる配列パターンが，上位にランキングされる傾向があることが確認されている．

このように，ミスマッチクラスタから最小汎化集合を抽出することは，規則的な特徴を把握することに有効である．また，ミスマッチクラスタを構成する部分文字列の文字列長が等しくない場合でも，研究[1]により，異なる文字列長の部分文字列で構成されたミスマッチクラスタに対してアライン
メント処理を行い，アラインメント結果から最小汎化集合を抽出することが可能となった．
そこで，本研究では，類似性検索で利用する非類
似度の尺度として，編集距離とハミング距離の 2
つをとりあげ，それぞれが最小汎化集合の計算結果に与える精度面の影響について考察する．なお，精度を検証するために，ZincFinger データセットとKringle データセットの 2 種類のデータセットを利用している．
本論文の構成は以下の通りである．第 2 章では関連研究について述べる．第 3 章で本論文に扱う記号の定義を示し，第 4 章では，検索手法について説明する．第 5 章で評価実験について説明する．
第 6 章で本論文のまとめを行う．

2. 関連研究ミスマッチクラスタから最小汎化集合を効率よく抽出する方法がいくつか研究されており，反復精密化法，ドメイン分割法と反復精密化法の併用
方法，段階的一般化法が提案されている．反復精密化法は，ミスマッチクラスタから最汎パターン

と呼ばれるミスマッチクラスタを表現する最も一般的な汎化配列パターンの起点を探索木のルートとし，パターン切除に基づき，ルートから下方向に探索を進める．段階的一般化法は，ミスマッチ
クラスタを構成する部分文字列の部分集合に対する汎化配列パターンを段階的に列挙することで探索を進める．反復精密化法や段階的一般化法を用いることで，ミスマッチクラスタから最小汎化集合を求めることができるが，これらはミスマッチ
クラスタを構成するすべての部分文字列の長さが等しいことを前提に作成されている．
ミスマッチクラスタを構成する部分文字列の長さがそれぞれ異なる場合では，アラインメント処理に基づくミスマッチクラスタからの最小汎化集
合の抽出[1]として提案されているものがある．これはミスマッチクラスタに対して，階層的に部分文字列をクラスタリングしながら，アラインメントを行っていく累進法を用いてアラインメント処理を行い，ミスマッチクラスタを構成するインスタ
ンスを列ごとに比較し，列についてまとまりのある部分文字列を$(n)と表記する記号に変換する，この変換を用いて，汎化処理を行い，最小汎化集合を抽出する．
本論文では，このアラインメント処理に基づく
ミスマッチクラスタからの最小汎化集合の抽出において，ミスマッチクラスタを計算する曖昧検索の段階で編集距離を用いると，抽出精度にどの程度向上するのかについて検証している．

𝐷(𝑖, 𝑗 − 1)𝐷(𝑖 − 1, 𝑗)
𝐷(𝑖, 𝑗) = 𝑚𝑖𝑛 {}𝐷(𝑖 − 1, 𝑗 − 1) + 𝑡(𝑋𝑖 , 𝑌𝑗 )1𝑓𝑜𝑟 𝑡(𝑖, 𝑗) = {0

この式により検出された D(n, m)の値が編集距離の値である．
また，トレースバックというものを行い，空白
文字の入るところも確認できる．トレースバックの方法として，作成した編集グラフの D(n, m)から
D(0, 0)に向かって，左側，上側，左斜め上側のどの値の最小値をとってきたかをたどっていくことにより，トレースバック経路が生成される．もし D(i,j)でトレースバック経路を左側に行くと，その時に文字列 X に空白文字が入り，上側に行くと，文字列 Y に空白文字が入る．またトレースバック経路
は複数ある時もある．
また，トレースバックを行う際，検索文字の中にあるワイルドカード以外の文字が空白文字に置
き換わり，うまくクラスタリングができない．このため，本論文では検索文字側には文字の削除は許さないとし，式(1)を以下のように変更して行う．
𝐷(𝑖, 𝑗 − 1) + 100
𝐷(𝑖 − 1, 𝑗)
𝐷(𝑖, 𝑗) = 𝑚𝑖𝑛 {}𝐷(𝑖 − 1, 𝑗 − 1) + 𝑡(𝑋𝑖 , 𝑌𝑗 )1 (𝑋𝑖 ≠ 𝑌𝑗 )𝑓𝑜𝑟 𝑡(𝑖, 𝑗) = {}0 (𝑋𝑖 = 𝑌𝑗 )3. 記号の定義
本章では，本論文で使用する記号と編集距離の定義を行う．

3.1

編集距離

ある 2 つの文字列 X と Y があるとき，X に対して文字の削除，挿入，置換などをすることにより，
X を Y に変換する操作は，編集操作と呼ばれる．
編集距離とは，この 2 つの文字列どちらかに空
白文字を挿入（この挿入が Y 側ならば X 側の対応する文字は削除を意味する）して長さを同じにそろえ，編集操作の最小数を指す．また，文字列 Xから文字列 Y に変換する編集距離を d(X, Y)と表す．
また，この d(X, Y)の値を出すために編集グラフというものが用いられる．文字列 X の長さを n，文字列 Y の長さを m とする．また，編集グラフの i
列 j 行目を D(i, j)と表す．編集グラフの作成にあたり，まず i 列に 0 から n， j 行に 0 から m までの数字を入れる．その後以下の式に従い，値を入れていく．

(𝑋𝑖 ≠ 𝑌𝑗 )} ⋯ (1)(𝑋𝑖 = 𝑌𝑗 )本研究ではこの編集距離を用いてデータベース
に対し，類似性検索を行うと最小汎化集合にどのような影響があるのかを研究することがゴールで
ある．

3.2

ミスマッチクラスタ

ミスマッチクラスタ MIS を本論文では，以下の形式で表記する．
𝑀𝐼𝑆 = {< 𝑖𝑛𝑠𝑡1 >, < 𝑖𝑛𝑠𝑡2 >, ．．． , < 𝑖𝑛𝑠𝑡𝑘 >}また，編集距離による類似性検索により，デー
タベースから得られた部分文字列< instk >をインスタンスと呼ぶ．各インスタンス< instk >の長さは|<instk >|と表し，インスタンス< instk >の第 i 文字目を< instk >[i ]と表記する．

3.3

汎化配列パターン

記号 Σi を任意の 1 文字 Σ の部分集合とするとき，k 個の Σi を並べたパターンを k-汎化配列パターンと呼び，次の式のように< patk >と表記する．
< patk >= < Σ1Σ2 ．
．
．Σk -1Σk >だだし，Σi はたびたび括弧[ ]の中に Σ の全要素を列挙した表記する．Σi ⊆Σ が存在する場所を曖昧
文字領域と呼ぶ．また，｜Σi｜≦2 のとき，集合 Σiは曖昧文字ドメインと呼ばれ，Σi 内に存在する任意の 1 文字の配置が許されることを示している．
曖昧文字ドメインが 1 個所以上存在するとき，< patk >を k-汎化配列パターンと呼ぶ．

3.4

最小汎化集合最小汎化集合 MGS = {G1, G2，．．
．, Gm } ( 1≦m ≦|MIS | )が，k-汎化配列パターン< patk >および k -イ
ンスタンス< instk >から構成されているとする．ただし，EVAL(< patk >) ⊆MIS かつ，< instk > ∈MIS を満たすものとする．また，関数 EVAL は汎化配列パターンに含まれるすべてのインスタンスを求める関数とする．この集合 MGS が以下の性質を満たす
とき，MGS を MIS に対する最小汎化集合と呼ぶ．
(1) EVAL(MGS ) = MIS(2) MGS の任意の 2 つの要素 Gi，Gj に対して，Giと Gj の間には冗長な関係が存在しない．(1≦i≠ j ≦m)(3) MGS に含まれるどの要素 Gi も極大（さらに汎化すると MIS に存在しないインスタンスを含んでしまう）である．
(4) 上記の(1) ~ (3)を満たす任意の MGS’ に対し，
|MGS’ | ≦ |MGS |が成立する．
一般に，MGS が上記の(1) ~ (3)を満たすだけでは
MGS を一意に定めることができないので，これらに上記(4)を追加し，最小汎化集合が一意に定まるようにしている．

4. 検索手法
本章では，検索手法について説明する．4.1 節では．全体の処理手順について説明を行う．4.2 節では，既存の手法のハミング距離を用いた類似性検索について述べ，4.3 節で編集距離による類似性検索について示す．

4.1

を用いた類似性検索を行い，ミスマッチクラスタ
MIS を得る．得られたミスマッチクラスタ MIS に対して，累進法[1]を用いたアラインメント処理を行
い，文字列長の等しいミスマッチクラスタ MIS’を得る．次に，ミスマッチクラスタ MIS’に対して$変換を行い，まとまりのある部分文字列を$(n)と表記する．また，変換元の文字列と変換後の$(n)記号の対応表 R を作成する．最後に，ミスマッチクラス
タ MIS’に対して$変換したものに，汎化処理にかけ，最小汎化集合を抽出するという流れである．

処理手順

図 1 を用いて，提案手法の処理手順を説明する．
最初に，テキストデータベースに対して編集距離

図 1：提案手法による処理手順
処理手順の詳細は，以下のとおりである．
(1) 配列データベース D に対して，
キーワード K，
誤差数 ε をそれぞれ入力し，編集距離を用いて類似性検索を行う．類似性検索で得られた結果をミスマッチクラスタ MIS とする．編集距
離を用いた類似性検索についての詳細は，4．
3 節で説明する．
(2) ミスマッチクラスタ MIS に対して，累進法[5]を用いたアラインメント処理を行い，ギャッ
プ記号”－“を入れることでミスマッチクラス
タの各インスタンス< instk > (1≦k≦n) の長さを同じにする．アラインメント処理を行った
後のミスマッチクラスタを MIS’ とする．
(3) ミスマッチクラスタ MIS’ に対して$変換を行
う．$変換関数を Dollar(X)(X はミスマッチクラスタ)とすると MIS’’ = Dollar(MIS’ )となる．$変
換では，ミスマッチクラスタを構成するインスタンスを列ごとに比較し，列について，まとまりのある部分文字列を$(n)と表記する記号に変換する．また，変換元の文字列と変換後の$(n)記号の対応表 R を作成する．
(4) $変換によって各インスタンスが$(n)の記号列に変換されたミスマッチクラスタ MIS’’ に対して汎化処理を行い，最小汎化集合 MGS を抽出する．
(5) 対応表 R を使用して，$(n)の記号列を文字列に
戻す．

4.2

ハミング距離による類似性検索

テキストデータベースにおいて既存の手法として，ハミング距離を用いた類似性検索がある．部
分文字列 K と許容誤差数 ε ( ≧0 ) (本実験では，ε =1 とする) が，
問合せ Q として与えられているとき，
この問合せ Q が，ハミング距離 d (K, K’ ) ≦ ε を満たす部分文字列 K’ のすべてを配列データベース
DB から選択するとき，この問合せ Q による検索を
ハミング距離による類似性検索と呼ぶ．

4.3

編集距離による類似性検索

編集距離による類似性検索では編集グラフを用いて，類似性検索を行っていく．問合せ Q が，編集距離 d (K, K’ ) ≦ε (本実験では，ε = 1 とする)を満たす部分文字列 K’ のすべてを配列データベース
DB から選択するとき，この問合せ Q を，編集距離を用いた類似性検索と呼ぶ．

5. 評価実験
提案手法の評価を行うために，提案手法である
編集距離を用いた類似性検索と，既存の手法であるハミング距離を用いた類似性検索の 2 種類の手法を ZincFinfer と Kringle の 2 種類のアミノ酸配列
データベースに対してそれぞれ行い，得られたミスマッチクラスタから最小汎化集合を抽出することを行った．そして，抽出された最小汎化集合の汎化配列パターンの支持数が多い順にランキングを行い，それぞれの汎化配列パターンにどの程度の意味のあるパターンが含まれているか，どれくらいの精度で汎化配列パターンを抽出できているかを比較することによって，編集距離を用いた類
似性検索とハミング距離を用いた類似性検索による影響を考察する．

5.1

データセット

表 1 に評価実験に用いたデータセットとその詳細を示す．用いたデータセットは，PROSITE[6]から取得した ZincFinger（登録番号:PS00028）と Kringle（登録番号:PS00021) の特徴を示す．
表 1 データセット詳細
データ
セット名
ZincFinger
Kringle

登録番号PS00028PS00021

データ
件数
1839
90

総長
(bytes)114650659123

実験では，最初に ZincFinger データセットに対して，編集距離による類似性検索を用いて曖昧な問合せを行う．ZincFinger のモチーフ配列パター
ンは，<C-x(2,4)-C-x(3)-[LIVNFYWC]-x(8)-H-x(3,5)-H> と して 知 ら れ て い る ． ZincFinger の 検 索 文 字 は ，<C-x(2,4)-C-x(3)-L-x(8)-H-x(3,5)-H>（可変長ワイル
ドカード）とし，許容誤差数は 1 で行う．次に，ハミング距離による類似性検索を用いて曖昧な問合せを行う．ハミング距離を用いる場合は，アラインメントを行った場合と行わなかった場合で行う．
次に，Kringle データセットに対する類似性検索で あ る ． Kringle の モ チ ー フ 配 列 パ タ ー ン<[FY]-C-[RH]-[NS]-x(7,8)-[WY]-C> と し て 知 ら れ ているが，モチーフパターンの中で Kringle データセ
ット中に出てきていないパターンがあるかを調べて，Kringle データセット中に出現しないモチーフ
パターンは，予め削除した．よって，モチーフ配列パターンは，<[FY]-C-R-N-x(7,8)-W-C>,<F-C-R-S-x(7)-W-C>,<Y-C-R-N-x(7)-Y-C>となった．
また，検索文字列は，<F-C-R-N-x(8)-W-C>とし，許容誤差数 ε = 1 で行う．実験の手順は，ZincFingerと同様である．
また，表 3 ~ 表 8 に実行結果を示す．
本論文では，配列パターンの表記は，PROSITE
表記[6]に従って表記することとする．x(3)は，3 文
字のワイルドカード領域(ワイルドカードとは，どんな文字でもよいことを示す)を示し，x(2,4)は，2
文字~4 文字のワイルドカード領域であることを示
す．

5.2

実験結果

ZincFinger データセットと Kringle データセット
対して，非類似度の尺度として，編集距離とハミング距離の 2 種類の類似性検索をそれぞれ行った．
また，ハミング距離を用いた類似性検索では，累進法を用いたアラインメント処理を行う場合と行わない場合の 2 種類の場合で実験したが，編集距離を用いた類似性検索では，検索されたミスマッ
チクラスタは，長さが異なる要素が含まれるため，
必ずアラインメント処理を行うこととした．この
結果，返された合計 6 種類のミスマッチクラスタ
について，ミスマッチクラスタごとに部分文字列の文字別ごとに検索を行った．汎化用ミスマッチ
クラスタとして，ミスマッチクラスタ MIS の構成
条件と用いたデータセットによって次のように定義する．まず，データセットに ZincFinger を用い

た時，アラインメント処理を適用し，編集距離を用いて類似性検索を行った結果得られたミスマッ
チクラスタを MIS1 とし，アラインメント処理を適用し，ハミング距離を用いて類似性検索を行った
結果得られたミスマッチクラスタを MIS2 とし，アラインメント処理を適用せず，ハミング距離を用いて類似性検索を行った結果得られたミスマッチ
クラスタを MIS3 とする．次に，データセットに
Kringle を用いた時，アラインメント処理を適用し，編集距離を用いて類似性検索を行った結果得られたミスマッチクラスタを MIS4 とし，アラインメン
ト処理を適用し，ハミング距離を用いて類似性検索を行った結果得られたミスマッチクラスタを
MIS5 とし，アラインメント処理を適用せず，ハミング距離を用いて類似性検索を行った結果得られたミスマッチクラスタを MIS6 とする．これを表にまとめると以下のようになる．
表 2 : 汎化用ミスマッチクラスタの種類
MIS の
構築条件

データ
セット名

ZincFinger
Kringleアラインメント処理
有り

アライン
メント処
理無し

編集距離

ハミング
距離

ハミング
距離

MIS1
MIS4

MIS2
MIS5

MIS3
MIS6

そして，抽出された最小汎化集合の汎化配列パターンを何個のインスタンスから構成されているかでランキングづけを行った．表 3 は，MIS1，表 4
は MIS2，表 5 は MIS3，表 6 は MIS4，表 7 は MIS5，
表 8 は MIS6 のランキング結果をまとめたものである．
支持数とは，何本の配列データベースに汎化配列パターンが含まれるかを示す値である．また，EVAL(汎化配列パターン)のうち，モチーフに該当するインスタンスがどれだけの割合で含まれているかも示した．(以下，割合)すなわち，割合は，{モチーフに該当するインスタンス数}÷{EVAL(汎化配列パターン)のインスタンス数}で計算したものである．また，検索した結果が良かったかどうかは，出力した結果に，どれだけの必要な情報が含まれているか，ノイズと呼ばれる不要な情報がどれだ
けあったかで判断されるため，検索の評価の基準と し て ， 再 現 率 (Recall Ratio) と 適 合 率 (Precition
Ratio)を用いる．再現率とは，データベース全体の中にある全適合文献の内，何割が検索されたかをみるものであり，いわゆる検索漏れをはかるための指標である．また，適合率(精度)とは，検索で得られた文献の内，どれだけテーマに適合していたかを表すものであり，ノイズの割合をみるための指標である．また，再現率と適合率は以下のように定義する．
再現率の計算では，A+B はデータセットのデー
タ件数，B は汎化配列パターンの支持数とし，適合率の計算では，B+C は汎化配列パターン中のモチーフ配列パターンに含まれる文字列の個数と汎化
配列パターン中のモチーフ配列に含まれない文字列(ノイズ)の個数の和，B は，汎化配列パターン中のモチーフ配列パターンに含まれる文字列の個数とすると，再現率(𝑅) =𝐵
× 100(%)
𝐴+𝐵

適合率(𝑃) =𝐵
× 100(%)
𝐵+𝐶と定義する．
また，再現率と適合率の調和平均として，トレードオフの指標である F 値を以下のように定義す
る．
𝐹値=

2×𝑃×𝑅
𝑃+𝑅

この F 値が高いほど，性能が良いと言える．
よって，この割合と再現率と適合率と F 値を用いて，抽出された最小汎化集合の汎化配列パターンの検索精度を比較する．
また，汎化配列パターンにおいて，①汎化配列
パターンの先頭に不要な文字がついている場合，②汎化配列パターンの語尾に不要な文字がついている場合，③ワイルドカードの前後に不要な文字がついている場合，①と②については，最小汎化集合とみなし③については，ノイズとみなすこととする．下線の文字列が該当箇所である．
例えば，①の場合の例として,< (Y|F|NF|AF|H|TF)-C-R-N-x(7)-W-C >，②の場合の例として,<F-C-R-N-x(7,8)-(WC|WCF|WCY|WCH|W|C|PWC|VW
C|AWC) >,③の場合の例として，<F-C-R-N-x(7,8)-(WC|WCF|WCY|WCH|W|C|PWC|VW
C|AWC) >のような汎化配列パターンが実際に検索された．このとき，①と②の場合は，最小汎化集合とみなし，③の場合は，ノイズとみなすということである．これは，検索のときに，検索文字列の誤差を許容誤差数 1 として認めたが，検索される汎化配列パターンの文字列の長さは制限しなかったためであると考えられる．

5.3

考察

まず，ZincFinger データセットの場合であるが，編集距離を用いた類似性検索(表 3)とハミング距離を用いた類似性検索(表 4)，両者ともに高い精度で検索が行われている．編集距離を用いた場合とハミング距離を用いた場合の 3 位と 4 位をそれぞれ比較してみると，わずかであるがハミング距離を用いた類似性検索の方が，編集距離を用いた類似性検索よりわずかに適合率が高くなっている．つまり，ノイズの少ない検索が行えていると言える．
一方，支持数に注目すると，編集距離を用いた場
合は，5 位まで 1700 以上の支持数を維持しているのに対し，ハミング距離を用いた場合は，3 位までしか維持できていないことが分かる．
次に，Kringle データセットの場合であるが，データ件数が 90 件と少ないということもあり，かな
り波のある結果となった．適合率に注目すると，編集距離を用いた類似検索(表 6)は，上位 4 位の平均は約 71%であるが，ハミング距離を用いた類似検索(表 7)は，約 98%という高い値をとっている．
よって，ZincFinger データセットと Kringle デー

タセットで，編集距離を用いた類似性検索とハミング距離を用いた類似性検索を行った結果，ハミング距離を用いた類似性検索の方がノイズの少ない検索が行えていることが分かる．
また，アラインメント処理について着目すると，ZincFinger データセットでは，アラインメント処理を行う場合(表 4)の方が，アラインメント処理を行わない場合(表 5)に比べて，2 位以下に現れる支持数に大きく上回っていることがわかる．また，割合，再現率，適合率においても，ほとんどの場合に，アラインメント処理を行う場合の方が，高い値をとっていることから，やはり，アラインメン
ト処理を行って，類似性検索を行うと精度のよい検索が行えることがわかる．
最後に F 値について着目すると，ZincFinger デー
タセットでは，MIS1 (表 3)と MIS2(表 4)を比較すると，ほとんど同じくらいの値を示しているが，Kringle データセットでは，MIS4(表 6)と MIS5(表 7)を比較すると，MIS5(表 7)が上位で良い値をとっていることから，ハミング距離を用いた類似性検索の方が検索性能は，良いということが分かる．

表 3 : MIS1 のランキング
No

汎化配列パターン

支持数

割合

再現率

適合率

F値

1
2

<C-[x(2)|x(4)]-C-x(3)-[FLYCT]-x(8)-H-x(3,5)-H><C-[x(2)|x(4)]-C-x(3)-[FLHYCTSGV]-x(8)-H-x(3,4)-H>

1815
1763

80.0
55.6

98.7
95.6

100
100

0.993
0.978

3
4

<C-x(2)-C-x(3)-[FILHYCTSAGVM]-x(8)-H-x(3,5)-H><C-x(2,4)-C-x(3)-[FL]-x(8)-H-x(3,5)-H>

1731
1725

58.3
100

90.8
91.6

96.5
97.8

0.936
0.946

5
6

1718

60.0

93.2

99.8

0.964

1667

50.0

90.6

99.8

0.950

7

<C-x(2,4)-C-x(3)-[FLYTS]-x(8)-H-x(3,4)-H><C-x(2)-C-x(3)-[FILHYNCTSDAGRVMW]-x(8)-H-x(3,4)-H><C-x(2,3)-C-x(3)-[FLYSTA]-x(8)-H-x(3,4)-H>

1631

50.0

88.3

99.6

0.936

8
9

<C-x(2,3)-C-x(3)-[FLS]-x(8)-H-x(3,5)-H><C-[x(2)|x(4)]-C-x(3)-[FILHYCTSGV]-x(8)-H-x(3)-H>

1628
1612

66.7
60.0

88.1
87.7

99.6
99.9

0.935
0.934

10

<C-x(2,4)-C-x(3)-[FLYCTS]-x(8)-H-x(3)-H>

1596

66.7

86.8

99.8

0.928

No
1

汎化配列パターン
<C-[x(2)|x(4)]-C-x(3)-[CLYFT]-x(8)-H-x(3,5)-H>

支持数
1815

割合
80.0

再現率
98.7

適合率
100

F値
0.993

2
3

<C-[x(2)|x(4)]-C-x(3)-[CLYFHSTVG]-x(8)-H-x(3,4)-H><C-x(2)-C-x(3)-[CLYIFHSTVMAG]-x(8)-H-x(3,5)-H>

1763
1731

55.6
58.3

95.9
94.1

100
99.7

0.979
0.968

4
5

<C-x(2,4)-C-x(3)-[YFST]-x(8)-H-x(3,4)-H><C-x(2,4)-C-x(3)-F-x(8)-H-x(3,5)-H>

1684
1678

50.0
100

91.6
91.2

99.7
100

0.955
0.954

6

<C-x(2)-C-x(3)-[CLYIDRFHSTVMANWG]-x(8)-H-x(3,4)-H>

1667

50.0

90.6

99.8

0.950

7
8

<C-[x(2)|x(4)]-C-x(3)-[CLYIFHSTVG]-x(8)-H-x(3)-H><C-x(2,3)-C-x(3)-[YFSTA]-x(8)-H-x(3,4)-H>

1612
1609

60.0
40.0

87.7
87.5

99.9
99.6

0.934
0.932

9
10

<C-x(2,3)-C-x(3)-[FS]-x(8)-H-x(3,5)-H><C-x(2,4)-C-x(3)-[CYFST]-x(8)-H-x(3)-H>

1593
1578

50.0
60.0

86.6
85.8

99.6
99.7

0.926
0.922

表 4 : MIS2 のランキング

表 5 : MIS3 のランキング
No1

汎化配列パターン<C-x(2)-C-x(3)-[CDFGHILMNRSTVWYA]-x(8)-H-x(3)
-H>

支持数

割合

再現率

適合率

F値

1535

50

83.2

97.5

0.898

2

< C-x(2)-C-x(3)-[CDEFGHIKLMNPQRSTVWYA]-x(8)H-x(4)-H>

573

40

29.3

79.2

0.428

3
4

<C-x(4)-C-x(3)-[CFGHILSTVY]-x(8)-H-x(3)-H><C-x(2)-C-x(3)-L-x(8)-H-x(3)-[CDEFHLMNPQRSTVA]>

442
203

60
6.67

22.3
7.9

94.8
68.9

0.361
0.142

5

<C-x(2)-C-x(3)-L-x(8)-H-x(4)-[CFGHIKLMNPQRSTV
WA]>

203

5.88

2.7

22.7

0.048

203

5.88

1.3

9.7

0.023

7

<C-x(2)-C-x(3)-L-x(8)-H-x(5)-[DEFGHIKLMNPQRSTY
A]><C-x(2)-C-x(3)-[CEFGHILMSTVYA]-x(8)-H-x(5)-H>

202

53.8

9.9

74.5

0.175

8
9

<C-x(4)-C-x(3)-[CFGHLQSTVYA]-x(8)-H-x(4)-H><[CDHIKNQRSTY]-x(2)-C-x(3)-L-x(8)-H-x(3)-H>

173
167

45.5
9.09

8.6
7.9

92.2
85.9

0.157
0.145

10

<[CDEFGHKLNPQSTVWY]-x(4)-C-x(3)-L-x(8)-H-x(3)
-H>

167

6.25

0.7

6.3

0.013

No
1

汎化配列パターン< (Y|F|NF)-C-R-N-x(7,8)-W-C >

支持数
81

割合
66.7

再現率
68.9

適合率
76.5

F値
0.725

2
3

< (Y|F|NF|AF|H|TF)-C-R-N-x(7)-W-C >< F-C-(RN|R)-x(8)-W-C >

60
31

33.3
50.0

50.0
12.2

75.0
35.5

0.600
0.182

4
5

< F-C-[RN|RS|WN]-x(7)-W-C ><F-C-R-N-x(7,8)-(WC|WCF|WCY|WCH|W|C|PWC|
VWC|AWC)->

24

66.7

25.6

95.8

0.404

22

38.5

20.0

81.8

0.321

No
1

汎化配列パターン< [YF]-C-R-N-x(7,8)-W-C >

支持数
81

割合
66.7

再現率
90.0

適合率
100

F値
0.947

2
3

< [YFH]-C-R-N-x(7)-W-C >< F-C-R-[NS]-x(7)-W-C >

60
23

33.3
50.0

65.5
25.6

98.3
100

0.786
0.408

4

< F-C-[RW]-N-x(7)-W-C >

15

50.0

15.6

93.3

0.267

No

汎化配列パターン

割合

再現率

適合率

F値

1
2

< [FHY]-C-[RW]-[NS]-x(8)-C >< [FHY]-C-R-N-x(7)-W-C >

69
60

33.3
66.7

76.7
66.7

99.1
99.0

0.865
0.797

3
4

< [FY]-C-R-N-x(8)-C >< F-C-R-[NS]-x(7)-W-C >

42
23

100
50.0

46.7
25.6

100
100

0.637
0.708

6

表 6 : MIS4 のランキング

表 7 : MIS5 のランキング

表 8 : MIS6 のランキング
支持数

6. まとめ
本論文では，曖昧な問合せを行う際，編集距離を用いた類似性検索と，ハミング距離を用いた類
似性検索の 2 種類の異なる尺度をもつ類似性検索により，最小汎化集合を抽出し，支持数に関して上位にランキングされた汎化配列パターンの精度等を評価し，2 種類の尺度の違いによる影響を比較・考察した．
適合率(精度)に着目すると，編集距離を用いた場
合より，ハミング距離を用いた場合の方が高い検索精度であることが確認できた．同様に，F 値について着目すると，ZincFinger データセットでは，編
集距離を用い た類似性検索とハミング距離を用いた類似性検索は，ほとんど同じ検索性能であった

が，Kringle データセットでは，ハミング距離を用いた類似性検索の方が，ランキングの上位で良い値をとっていることから，ハミング距離を用いた類似性検索の方が検索性能は，良いということが分かった．
また，ハミング距離を用いた類似性検索において，累進法を用いたアラインメント処理を行った
方が精度の高い類似性検索が行えるということが確認できた．F 値についても同様に，ZincFinger データセットでは，すべての順位でアラインメント処理を行った方が高い値をとっており，Kringle データセットにおいても，1 位と 2 位の上位の部分で，アラインメント処理を行った場合の方が高い値をとる結果になった．
課題として，今回は，ZincFinger データセットの検索文字は，<C-x(2,4)-C-x(3)-L-x(8)-H-x(3,5)-H>（可変長ワイルドカード）とし，許容誤差数は ε = 1 で行 い ， Kringle デ ー タ セ ッ ト の 検 索 文 字 列 は ，<F-C-R-N-x(8)-W-C>とし，許容誤差数 ε = 1 として実験を行ったが，他の検索文字列の場合や，他のデータセットで類似性検索を行うとどのような影響が出るかを検証するということが今後の課題といえる．

謝辞
本研究の一部は, 日本学術振興会・科学研究費補助金(基盤研究(c)，課題番号:20500137)の支援により行われた．

参考文献[1]

宮原 和也，岡田 一志，田村 慶一，北上
始：アラインメント処理に基づく曖昧検索結果からの最小汎化集合の抽出，第 60 回電気・情報関連学会中国支部連合大会，pp.53-54，
2009 年 10 月．

[2]

K. Araki, K. Tamura, T. Kato, Y. Mori, and H.
Kitakami: Extraction of ambiguous sequential
patterns with least minimum generalization frommismatchclusters,
THE
THIRD
INTERNATIONALCONFERENCEON
SIGNAL-IMAGETECHNOLOGY and
INTERNET-BASED SYSTEMS, IEEE Computer
Society Press, pp. 32-39 (2007).

[3]

H. Kimura, H. Kitakami, K. Araki, and K.
Tamura: A stepwise generalization method forextracting minimum generalized set frommismatch cluster, Proceedings of the 2008
International Conference on Bioinformatics and,Computational Biology (BIOCOMP'08), Vol. II,
pp. 998-1004 (2008).

[4]

Kazuya Miyahara, Hajime Kitakami,
Yoshifumi Takahashi, Keiichi Tamura,
Susumu Kuroki:
Mining Minimum Generalized Set Based on
Multiple Alignments from
Mismatch Cluster,
BIOCOMP 2010, pp.35-41, 2010.

[5]

阿久津達也：バイオインフォマティクスの数
理とアルゴリズム，共立出版，2007 年．

[6] PROSITE：http://kr.expasy.org/prosite/.