ビジネス応用におけるデータマイニングと知識発見

演繹データベースと相関ルール発見
－ゲノム情報処理への応用－
北陸先端科学技術大学院大学
知識科学研究科
佐藤賢二
ビジネス応用におけるデータマイニングと知識発見
自己紹介
略歴：九州大学～東京大学（医科研HGC）～JAIST
研究：知識ベースや知識発見の技術を応用した
ゲノム情報処理（特にタンパク質関係）
宣伝：人工知能学会第二種研究会・分子生物情報
研究会（SIGーMBI）
http://www.hgc.ims.u-tokyo.ac.jp/sigmbi/
宣伝： JAIST知識科学研究科（４月にスタートした新学
科）
http://www.jaist.ac.jp/ks/
紹介用のCD-ROMあります
ビジネス応用におけるデータマイニングと知識発見
講演内容
ゲノムデータベースの概要（GenomeNet)
タンパク質立体構造解析のための演繹データ
ベースシステムPACADE
相関ルール発見を用いたゲノム情報処理
統合システムWebPACADE
ビジネス応用におけるデータマイニングと知識発見
ゲノムデータベース
主に分子生物学の実験の結果得られるデータを
世界各国で集積・配付している
•核酸配列情報
GATC…
•タンパク質配列情報
SER ALA PRO …
•タンパク質立体構造情報
•遺伝病などの疾病に関する情報
•文献情報
…
実験技術の進歩とともに
データの産出速度が加速
ビジネス応用におけるデータマイニングと知識発見
指数的に増え続けるゲノムデータ
ビジネス応用におけるデータマイニングと知識発見
ゲノムネット（GenomeNet)
JAISTでもミラー
サーバ立ち上げ中
京大化研
スパコンラボ
東大医科研
ヒトゲノム解析センター
ビジネス応用におけるデータマイニングと知識発見
ゲノムネットがサポートするデータベース
タンパク質の
構造データ
タンパク質の
配列データ
ビジネス応用におけるデータマイニングと知識発見
タンパク質に関するデータの階層
一次構造 …MSTPARKRLMRDFKRLQQDPPAGISGAPQDNN…
α-helix
coil
β-strand
二次構造
超二次構造
立体構造
ビジネス応用におけるデータマイニングと知識発見
PDB（Protein Data Bank）
X線結晶回折やNMRなどの手法で測定したタンパク質の構造データを
格納したもの。現在8000個ほどのエントリを持つ（個々のエントリ
が１分子に対応する）。テキストファイルの形で配布されている。
立体構造の可視化や、新しい分子を設計する時の下敷きとしてよく
使われる。
キーワードなどの情報で検索することは容易だが、実際には構造に
基づいた検索がしたい（例えば特定の条件を満たす部分構造がどの
タンパク質のどこにあるかなど）。
演繹データベースを使ってみてはどうか？
ビジネス応用におけるデータマイニングと知識発見
演繹データベースとは
論理プログラミングシステム＋関係データベース
ファクト
ルール
質問
解
par(a,b). par(b,c). par(c,d).
anc(X,Y) :- par(X,Y).
anc(X,Y) :- anc(X,Z), par(Z,Y).
:- anc(a,Y).
anc(a,b). anc(a,c). anc(a,d).
フリーウェアの処理系：CORAL（Wisconsin Univ.）
ftp://ftp.cs.wisc.edu/coral/coral-1.5（オリジナル）
ftp://ftp.jaist.ac.jp/pub/dbms/coral/coral-1.5（ミラー）
書籍
森下真一著「知識と推論」共立出版
ビジネス応用におけるデータマイニングと知識発見
演繹データベースの特徴
関係データベースに比べると、再帰検索や否定の記述が容易
な分、検索能力が高い。検索に用いるルールは宣言的に記述
されるため、モジュール性が高い。
Prologのような論理プログラミングシステムに比べると、ユ
ーザが推論を制御しなくてもすべての解を探索し停止する分
、扱いやすい。大量データ処理に向いているため、データベ
ース検索向き。
応用がちょっと少ない？
タンパク質立体構造解析のための演繹
データベースシステムPACADEの開発
ビジネス応用におけるデータマイニングと知識発見
PACADE
二次構造のジオメトリ情報をPDBから抽出し、ファクトデータ
として演繹データベースに格納
length
distance
angle
DBMSとしてウィスコンシン大学で開発されたフリーウェア
(CoralおよびEXODUS)に少し手を加えたものを用いている
ビジネス応用におけるデータマイニングと知識発見
PACADEを使った超二次構造の検索例（Greek Key）
２種類の4-stranded
Greek Key
5-stranded
Greek Key
２種類の6-stranded
Greek Key(jerry roll)
相互再帰的に定義できる構造
ビジネス応用におけるデータマイニングと知識発見
Greek Key の検索ルール
ルール集合(一部)
greek_even_r(A,L,D,4,P) :- hairpin(B,C,P), hairpin(C,D,P), not_coils(A,B,P),
neighbour(A,D,P), double_anti_parallel(A,D,P), L=[B,C].
greek_even_r(A,L,D,Num1,P) :- greek_odd(B,L1,D,Num,P), not_coils(A,B,P),
neighbour(A,D,P), double_anti_parallel(A,D,P), append([B],L1,L), Num1=Num+1.
greek_even_l(A,L,D,4,P) :- hairpin(A,B,P), hairpin(B,C,P), not_coils(C,D,P),
neighbour(A,D,P), double_anti_parallel(A,D,P), L=[B,C].
greek_even_l(A,L,D,Num1,P) :- greek_odd(A,L1,C,Num,P), not_coils(C,D,P),
neighbour(A,D,P), double_anti_parallel(A,D,P), append(L1,[C],L), Num1=Num+1.
greek_odd(A,L,D,Num1,P) :- greek_even_r(A,L1,B,Num,P), greek_even_l(C,L2,D,Num,P),
append(L1,[B],L), append([C],L2,L3), L=L3, Num1=Num+1.
…
質問(6個の二次構造から成る Greek key の場合)
:- greek_even_r (A,L,D,6,P).
ビジネス応用におけるデータマイニングと知識発見
検索結果：γ2-cristarin(1gcr)内のjerry roll
8
14
解
12 10
4
6
greek_even_r(4,[6,8,10,12],14,6,”1gcr”).
ビジネス応用におけるデータマイニングと知識発見
類似構造検索
特定の部分構造に似た部分構造を探す
ビジネス応用におけるデータマイニングと知識発見
類似構造検索のメカニズム
ユーザの入力：
類似元（タンパク名、チェイン名、領域）
許容誤差範囲（角度、距離、etc.）
探索空間（全エントリ、一部のエントリ）
システムの動作：
１）類似元自身を検索し、推論中に使用した束縛値を
記憶する（類似元の特徴抽出）
２）記憶した束縛値に基づいて、±αの誤差を許容し
ながら、指定された探索空間内で類似部分構造を
探すようなルールと質問を自動的に生成
３）生成したルールと質問を使って検索
システムの出力：類似部分構造を解として返す
ビジネス応用におけるデータマイニングと知識発見
類似構造検索の例
コマンド
similar -p 5tnc -s 131 -e 159 -a 30 -d 6 -sp pacade_nr
類似元
許容誤差範囲
探索空間
経過時間
16.00 sec. for the 1st search, 26.00 sec. for the 2nd search.
一次検索
二次検索
解集合
131
131
131
131
131
159
159
159
159
159
類似元
_
_
_
_
_
5tnc
5tnc
5tnc
5tnc
5tnc
2.51000
3.30035
3.30971
3.50223
4.61469
類似度
40
40
40
40
130
64
64
64
64
159
_
_
_
_
a
1rro
5pal
1rtp
1cdp
2scp
類似部分構造
ビジネス応用におけるデータマイニングと知識発見
グラフィック表示
類似元
TROPONIN-*C (5tnc)
131～159
類似部分構造
RAT ONCOMODULIN (1rro)
40～64
ビジネス応用におけるデータマイニングと知識発見
検索から発見へ
PACADE
fact
rule
par(1,2). par(2,3).…
anc(X,Y) :- par(X,Y).
anc(X,Y) :- anc(X,Z), par(Z,Y).
query :- anc(1,Y).
演繹推論に
よる検索
answer
anc(1,2). anc(1,3).…
大量かつ多様な
ゲノムデータ
有用な知識
(e.g. 相関ルール)
自動的な知識発見
CCGCAT
AGTCGA
TCGG…
ビジネス応用におけるデータマイニングと知識発見
相関ルール発見
・IBMのAgrawalらが1993年に提案。商品の販売記録を分
析し、商品間の相関関係を把握するために使用された。
・１回の商品購入で一緒に買われる頻度が高い商品集
合を検索し、ルール化する。
２段階処理
・ルールの価値はサポートおよび確信度という２つの
パラメータで定量的に評価される。
・サポートがある値以下の組合せは計算途中で捨てる。
同様に確信度がある値以下の相関ルールは生成しない。
ビジネス応用におけるデータマイニングと知識発見
コンビニエンスストアの例
アイテム
顧客の購買レシート番号パンバター米ミルク醤油
1
1
1
0
1
0
データ
2
3
4
5
0
1
1
1
1
0
1
1
0
0
0
1
0
0
1
0
相関ルール発見
（Apriori）
1
1
1
0
最小サポート= 1
最小確信度= 60%
パン, バター => ミルク
サポート= 2
確信度= 66.6%
ビジネス応用におけるデータマイニングと知識発見
ゲノムデータからの相関ルール発見の例
配列
構造
機能
特徴的な
部分構造
leu-pro-glu-ser-…
…-pro-ile-lys-asn
折れ畳み
機能発現
protease
機能上の
分類
配列
モチーフ
これらの情報にまたがる相関ルール
ビジネス応用におけるデータマイニングと知識発見
異種ゲノムデータを関連付ける
タンパク質に関する種々のゲノムデータ
タンパク質名モチーフ１モチーフ２部分構造１機能１機能２
タンパク１
タンパク２
タンパク３
タンパク４
タンパク５
1
0
1
1
1
0
0
0
0
1
1
1
0
1
1
相関ルール発見
（Apriori）
0
1
1
1
0
1
0
0
1
0
最小サポート= 1
最小確信度= 60%
モチーフ１, 部分構造１=>機能２
サポート= 2
確信度= 66.6%
ビジネス応用におけるデータマイニングと知識発見
データの準備（使用する特徴）
配列の特徴
PROSITEモチーフ
構造の特徴
類似部分構造
PACADEの類似構造
検索機能を用いる
機能の特徴
SWISS-PROTのキーワード
4桁のEC番号(酵素の機能分類)
ビジネス応用におけるデータマイニングと知識発見
データの準備（ビットベクターの表）
部分構造のID
PROSITE
のモチーフ
EC番号に
EC番号に
よる分類
よる分類
(第1～第3レベル)
(第1～第2レベル)
SWISS-PROT
キーワード
pdb {1187,… ,699} SPPR=UBIQUITIN_EC3= EC2= SPKW= …
code
CONJUGAT
H6.3.2 4.2 SIGNAL …
類似部分構造
1aaj
0
0
1
0
0
…
の集合
1aak
0
1
0
0
0
…
1abe
1
0
0
0
0
…
…
…
…
…
…
…
…
ビジネス応用におけるデータマイニングと知識発見
実験結果
実験条件
ルールはマルチヘッド可とする
最小サポート=4, 最大サポート=30, 最小確信度=65%
ヘッドのサポート＞ボディのサポートであるような
ルールは生成しない（ヘッドのほんの一部分しか説明
しないようなルールを抑制するため）
以下のような背景知識から自明なルールは生成しない
EC3=1.2.3 => EC2=1.2
相関ルールの例
構造の特徴
構造の特徴
配列の特徴
{596,…,9965}, {1361,…,9459}, SPPR=ASP_PROTEASE
=> SPKW=ASPARTYL PROTEASE, EC3=3.4.23
機能の特徴
機能の特徴
ビジネス応用におけるデータマイニングと知識発見
見つかった相関ルール（一部）
ASPARTYL PROTEASE関連
{596,…,9965}, {1361,…,9459}, SPPR=ASP_PROTEASE
=> SPKW=ASPARTYL PROTEASE, EC3=3.4.23
カルシウム結合タンパク関連
{186,…,9310}, SPPR=EF_HAND
=> SPKW=CALCIUM-BINDING, {1994,…,7532}
構造の共起のみ
{1477,…,9811}, {1718,…,9998}
=> {6714,…,7062}, {6874,…,7206}
ビジネス応用におけるデータマイニングと知識発見
ASPARTYL PROTEASEに共通かつ特有な部分構造
ビジネス応用におけるデータマイニングと知識発見
カルシウム結合タンパクに共通かつ特有な部分構造
ビジネス応用におけるデータマイニングと知識発見
機能が異なるタンパクで共通かつ特有な部分構造
ビジネス応用におけるデータマイニングと知識発見
２つの事例に共通する問題
どちらも記号処理ベースなので可視化システムと
連動しないと使いにくい（特に立体構造の可視化）
相互に関連があるようでない
できればネットワーク経由でサービスしたい
PACADEに可視化機能を付けて、ゲノムネットが
提供するサービスともリンクし、ついでに簡易
データマイニング機能を付けて、Webブラウザ
からアクセスできるようにしてはどうか？
ビジネス応用におけるデータマイニングと知識発見
統合システム WebPACADE
類似部分構造検索機能（PACADE)
http://pacade.genome.ad.jp/pacade.html
可視化機能（PDB highlight）
http://pacade.genome.ad.jp/pdb_highlight.html
簡易データマイニング機能
http://pacade.genome.ad.jp/cgi-bin/mining_form.pl
これらのサービスは相互呼び出しを行っており
ゲノムネット上でサービスされている（可視化
機能を提供する PDB highlight から入れる）
ビジネス応用におけるデータマイニングと知識発見
システムの構成と動作
WebPACADE
PACADE
structural
sim. search
PDB highlight data mining module
assoc. rule
visualization
discovery
links to
foreign
services
input forms
result of
sim. search
visual
window
links to
foreign
services
result of
mining
user
ビジネス応用におけるデータマイニングと知識発見
WebPACADE がサポートするデータ
PACADE
PDB rel.80 から選んだ4842エントリのタンパク質の
二次構造に関するジオメトリ情報をファクトとして
格納している（約１７０万ファクト）
PDB highlight
ゲノムネットでの最新PDB（rel.84）を全てサポート
（7688エントリ）
簡易データマイニング
ゲノムネットが提供する LinkDB（異なるゲノムデータ
ベースのエントリ間の参照関係）を用いている
参照関係の総数は約６００万件
ビジネス応用におけるデータマイニングと知識発見
PACADE による類似部分構造検索
可視化で使う
プラグイン
（フリーウェア）
類似元を
可視化
類似部分構
造を可視化
簡易データ
マイニング
ビジネス応用におけるデータマイニングと知識発見
PDB highlight による可視化
他のデータベースの参照
一次構造
他の解析サービスの呼び出し
立体構造
プラグインを操作するこ
とにより拡大縮小／回転
／平行移動などが可能
二次構造
ビジネス応用におけるデータマイニングと知識発見
WebPACADE における簡易データマイニング機能
ユーザが指定したPDBエントリ集合に対してビットが立っているような
特殊なアイテムを動的に生成し、そのアイテムに関する相関ルールだけ
を効率よく求める。他のアイテムは LinkDB から供給される参照関係
データのサブセット（ユーザが別途指定したゲノムデータベースに関す
るアイテムだけを使用）。
1aa3
1ab0
1ac1
1ady
1ae5
1afp
1ag2
1ahe
1aid
ユーザ指定
0
1
1
0
1
0
0
1
0
A1
0
0
0
1
1
0
0
0
0
B1
0
1
1
0
0
0
0
1
0
B2
0
0
0
0
1
0
0
0
0
C1
1
1
0
0
0
0
0
1
0
C2
0
1
0
1
0
0
0
0
1
C3
1
0
0
0
1
0
1
0
1
D1
0
0
0
0
1
1
1
0
0
E1
1
0
1
0
0
0
0
1
0
結局、ユーザは「指定したPDBエントリ集合と他のデータ
ベースエントリとの相関」を求めることができる。
ビジネス応用におけるデータマイニングと知識発見
簡易データマイニングの模様
対象のゲノムデータ
ベースを指定
PDBのエントリ集合
簡易データ
マイニング
見つかった
相関ルール
ビジネス応用におけるデータマイニングと知識発見
おわりに
PACADE の類似検索は並列処理による高速化が必要
PDB highlight はさらに高機能化が必要
簡易データマイニングはまだプロトタイプレベル
各種精練手法の実装や発見した相関ルールの再利
用（e.g.相関ルールを使った推論）などを行い、
ゲノムデータベースからの実用的データマイニン
グサービスに発展させたい
タンパクの設計や創薬などの役に立つ機能があれ
ば積極的に追加して行きたいので、興味がある方
はぜひ御相談ください
ビジネス応用におけるデータマイニングと知識発見

Download Report