背景•!バイオインフォマティクスにおける情報量の爆発‒! 配列・立体構造データベースのデータ量の増加

知識の表現と抽出

京都大学化学研究所
バイオインフォマティクスセンター
五斗 進

http://www.genome.jp/ja/db_growth_ja.html!

•!多種多様なデータ
バイオインフォマティクス速習コースIe 2009/6/18

1‒! 文献、パスウェイ、相互作用、発現

背景

この講義では•!生命知識の階層性と多様な表現（データ型）•!多様なデータベースにおける知識表現と、そこからの知識抽出について学ぶ‒! 個体、細胞：テキスト、図‒!主に KEGG (Kyoto Encyclopedia of Genes andGenomes) を例に用いる‒! タンパク質間相互作用、パスウェイ：ネットワーク、グラフ•!内容‒!階層と関係による知識表現‒! 発現パターン：数値、ビット‒! タンパク質立体構造：３次元座標
MNKTLIAAAVAGIVLLASNAQAQTVPEG..
.!
!

!
"!

‒!その他の知識表現‒! アミノ酸配列、塩基配列：文字列•!ルールベースと推論‒! 化合物：文字列、グラフ‒!オントロジーとセマンティックウェブ

!
"!

"!

‒!（情報検索とデータマイニング）!

•!複数のレベルの情報を統合する必要性

2

3‒!データ統合による知識抽出

階層と関係による知識表現

フラットファイル

•!フラットファイル•!フラットファイル‒! レコードの集合‒!レコードの集合

4

KEGG PATHWAY のレコード!

•!レコード‒! フィールドからなる•!XML: The eXtensible Markup Language•!一つのフラットファイル中のレ
コードは同じフィールド構成を持つ‒!計算機処理を前提とした表現•!タブ切りファイルもフラットファイルの一種•!階層構造•!フラットファイルのスキーマは各レコードの構造（フィールドの種類）を示す‒!知識分類のための表現•!スキーマはオントロジーの一種と考えることができる
5

http://www.genome.jp/dbget-bin/www̲bget?pathway+map00010

6

フラットファイル

フラットファイル

KEGG PATHWAY のスキーマ!

•!Pathway entry‒! Entry•! マップ番号（map|ko|rn|生物種コード+番号）‒! Name, Description•! パスウェイの説明とモジュールとの関係‒! Class•! 階層分類情報‒! Pathway map•! マップへのリンク‒! Enzyme, Compound, Related pathway•! マップ中のオブジェクトのリスト‒! Reference•! 参考文献

http://www.genome.jp/dbget-bin/www̲bget?pathway+map00010

7

KEGG PATHWAY

http://www.genome.jp/dbget-bin/www̲bget?pathway+map00010

XML•!パスウェイはフラットファイル（テキスト）でもあり、イメージでもある

8

The eXtensible Markup Language•!XML は計算機処理を前提としたデータ表現用の１フォーマット
•!XML の element はフラットファイルのレコードに対応する•!XML の attribute はフラットファイルのフィールドに対応する
http://www.genome.jp/kegg/docs/xml/

http://www.genome.jp/kegg/pathway/map/map00010.html•!XML DTD (Document Type Deﬁnition) はスキーマの一種と考えることができ、XML ファイルの要素間の構造を示す
9XML DTD: Document Type Deﬁnition

10KGML: KEGG Markup Language
http://www.genome.jp/kegg/xml/•!KEGG PATHWAY 用のXML 表現•!マップ（pathway element）
ごとにタンパク質間のつながりの情報（相互作用：relation element）、化合物間のつながりの情報（反応：reaction element）を用意•!XML の element は階層的に構成できる

解糖系 ko00010 の KGML
1112

関係

名前空間

Relationships

Namespaces•!関係（relationships）は概念をお互いに結びつける•!名前空間は多数の DTD からくる語彙を同時に使えるように構成する•!XML における階層関係は containment という•!例：KGML 以外にも reaction を定義する DTD は多数ある•!XML において、その他の関係を定義する方法‒! SBML: Systems Biology Markup Language•! http//www.sbml.org/sbml/level2/‒! 新規レイヤーを追加する（striping）‒! CML: Chemical Markup Language‒! リファレンスを使用する（reference)•! http://cml.sf.net/schema/cmlCore•!名前空間は XML ドキュメントで宣言される URI (Uniform
Resource Identiﬁer) である

containment !

•!要素名と属性は名前空間のプレフィックスを用いることにより限定することができる

reference!

13

xmlns:cml=“http://cml.sf.net/schema/cmlCore”
xmlns:sbml=“http://www.sbml.org/sbml/level2”
xmlns:kgml=“http://www.genome.jp/kegg/xml”<sbml:reaction sbml:id=“reaction_1” sbml:reversible=“false”>…
</sbml:reaction><kgml:reaction …>…
</kgml:reaction>

分類のための階層構造

階層の意味•!分類（classiﬁcation）はあるドメインの情報をより簡単に理解するための一手法である•!（階層）分類はトップダウン、ボトムアップ、または中間層からのいずれのやり方でも構築することができる

14•!分類はしばしば階層的に構成される•!分類は多様な要素で成り立つ。サブクラス（サブセット）、インスタンス（メンバー）、その他の複雑な関係（relationships）など。
•!分類は複数の関係を同時に持つようなやり方ですることもできる

http://www.genome.jp/kegg/brite.html

1516

この講義ではその他の知識表現•!多様なデータベースにおける知識表現と、そこからの知識抽出について学ぶ•!ルールベースと推論‒! 形式論理：三段論法‒!主に KEGG (Kyoto Encyclopedia of Genes andGenomes) を例に用いる•! P と P→Q という二つの命題から Q を導く•! 論理プログラミング‒! 推論規則：If-then ルール•! エキスパートシステム：プロダクションルール

•!内容•! DENDRAL‒!階層と関係による知識表現•! MYCIN•! PSORT（初期のバージョン）‒!その他の知識表現•!ルールベースと推論•!その他‒!オントロジーとセマンティックウェブ‒! 意味ネットワーク‒!（情報検索とデータマイニング）‒!データ統合による知識抽出‒! フレーム1718

ルールベースシステム

前向き、後向き推論エンジン•!ルールベースプログラミングはより一般的な手続きプログラミングとは異なるスタイルである。

•!前向き推論、後向き推論ともに、ルールと前提知識ベースであるファクトの集合が必要である。

‒! Prolog などの論理プログラミング言語

path(X, Y) :- enzyme(Z), reaction(Z, X, Y).
path(X, Y) :- enzyme(Z), reaction(Z, X, W), path(W, Y).
enzyme(a). enzyme(b).
reaction(a, c, d). reaction(b, d, e)!

‒! LISP などの関数型プログラミング言語•!ルールは前提と結論からなる（if-then ルール）。前提が成立すれば結論が導かれる。
•!ルールエンジンは事実（fact）を別の事実から論理的に導く。したがって、自動推論システムとして機能を持つ。
path(X, Y) :- enzyme(Z), reaction(Z, X, Y).
path(X, Y) :- enzyme(Z), reaction(Z, X, W), path(W, Y).
enzyme(a). enzyme(b).
reaction(a, c, d). reaction(b, d, e)!

•!前向き推論エンジンは適用できなくなるまでファクトをルールに適用することによって知識ベースを増やしてから、その知識ベースに対して問い合わせる。

ルール!

path(c, d), path(d, e), path(c, e)!

ファクト!

•!後向き推論エンジンはクエリから始めて、知識ベースに対して後向きにルールを適用して満足する解を得る。

•!ルールベースシステム以外にも定理証明器、制約ソルバー、ビジネスルールシステム等の自動推論システムがある。

？- path(c, X)!

19

推論の種類

この講義ではReasoning (Inference)•!多様なデータベースにおける知識表現と、そこからの知識抽出について学ぶ•!演繹推論：Deduction‒! ファクトとルールから三段論法を用いて新しいファクトを推論する‒!主に KEGG (Kyoto Encyclopedia of Genes andGenomes) を例に用いる•!帰納推論：Induction‒! 複数のファクトから新しいルールを推論する•!内容‒!階層と関係による知識表現‒! 配列モチーフの定義等もこれにあたる‒!その他の知識表現•!ルールベースと推論•!アブダクション：Abduction‒!オントロジーとセマンティックウェブ‒! ファクトと仮定（ルール）から前提となったファクトを推論する‒!（情報検索とデータマイニング）‒! 仮説形成21

オントロジーとセマンティックウェブ‒!データ統合による知識抽出

22

セマンティックウェブと RDF•!オントロジー•!セマンティックウェブ（Semantic Web）‒! A precise formulation of the concepts that form the basis
for communication within a speciﬁc ﬁeld‒! WWW (World Wide Web) のハイパーリンクに意味づけをしたもの‒! A computer-readable system for encoding knowledge
which speciﬁes not only the concepts in a given ﬁeld but
also the relationships among those concepts•!RDF (Resource Description Framework)‒! ウェブ上のリソースやデータ間の多対多関係（property）を明確に表現するためのフレームワーク。

•! Baclawski & Niu; Ontologies for Bioinformatics (2006) MIT press‒! RDF のセマンティクスは RDF グラフで定義される。

•!セマンティックウェブの必要性‒! RDF はサブクラス、サブプロパティ、ドメイン、レンジのための組み込み推論ルールを持っている。

‒! ウェブシステムやデータベースで得られるバイオインフォマティ
クスデータの急激な増加により新しいデータ処理の方法が必要となってきている。

‒! 順序付きの構造は RDF container や collection を用いて定義する。

‒! 多種多様なバイオインフォマティクスデータや高度に複雑な解析の必要性により、意味論に基づいた統合方法が必要となってきている。
•! 別のリソースで同じものが違う名前で呼ばれていることがある

20•!XTM (XML Topic Maps)‒! RDF を若干拡張したメタモデル。
2324

もっと単純なやり方

OWL: The Web Ontology Language•!LinkDB: http://www.genome.jp/dbget/linkdb.html•!OWL は RDF に基づいた言語で３つのバージョンがある。より一般的になる順番で、OWL Lite, OWL-DL, OWL Full。

‒! データベース間で同じものを表すエントリー間の対応関係を管理する‒! ヒト遺伝子 hsa:100 (ADA; adenosine deaminase [EC:3.5.4.4]) の場合
hsa:100
ncbi-geneid:100equivalenthsa:100
hsa:100
hsa:100hsa:100
hsa:100
hsa:100
hsa:100
hsa:100
hsa:100
hsa:100
hsa:100
hsa:100
hsa:100

rs:NM_000022
rs:NP_000013
unigene:Hs.654536
up:P00813
emb:AL139352
emb:CH471077
gb:AL139352
gb:CH471077
ipi:IPI00296441
ipi:IPI00872639
mim:608958
ncbi-gi:119596310
ncbi-gi:119596311

equivalentequivalentequivalentequivalentequivalentequivalentequivalentequivalentequivalentequivalentequivalentequivalentequivalent‒! 相手先の URL と組みで持っておくことにより同じもののエントリーを取得できる•!BIRC の biodb.jp（ヒト遺伝子）や JST のリンクセンター（化合物）も同様のアプローチを取っている。

25<?xml version="1.0" encoding="UTF-8"?><rdf:RDF
xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#”
xmlns:bp="http://www.biopax.org/release/biopax-level2.owl#”
xmlns:rdfs="http://www.w3.org/2000/01/rdf-schema#”
xmlns:owl="http://www.w3.org/2002/07/owl#”
xmlns:xsd="http://www.w3.org/2001/XMLSchema#"!xmlns="http://www.bndb.org/#" xml:base="http://www.bndb.org"><owl:Ontology rdf:about=""><owl:imports rdf:resource="http://www.biopax.org/release/biopax-level2.owl" /></owl:Ontology><bp:dataSource rdf:ID="BNppDataSource"><bp:NAME rdf:datatype="http://www.w3.org/2001/XMLSchema#string">BN++</bp:NAME><bp:COMMENT rdf:datatype="http://www.w3.org/2001/XMLSchema#string">http://www.bnplusplus.org</bp:COMMENT><bp:XREF rdf:resource="#BNpp"></bp:XREF></bp:dataSource><bp:NAME rdf:datatype="http://www.w3.org/2001/XMLSchema#string">Glycolysis /Gluconeogenesis</bp:NAME><bp:SHORT-NAME rdf:datatype="http://www.w3.org/2001/XMLSchema#string">Glycolysis /Gluconeogenesis</bp:SHORT-NAME><bp:SYNONYMS rdf:datatype="http://www.w3.org/2001/XMLSchema#string">Glycolysis /Gluconeogenesis</bp:SYNONYMS><bp:XREF rdf:resource="#3" /><bp:ORGANISM rdf:datatype="http://www.w3.org/2001/XMLSchema#string">eco</bp:ORGANISM><bp:XREF rdf:resource="#6" /><bp:COMMENT rdf:datatype="http://www.w3.org/2001/XMLSchema#string">http://www.genome.jp/
kegg/pathway/eco/eco00010.gif</bp:COMMENT><bp:COMMENT rdf:datatype="http://www.w3.org/2001/XMLSchema#string">http://www.genome.jp/
dbget-bin/show_pathway?eco00010</bp:COMMENT><bp:PATHWAY-COMPONENTS rdf:resource="#299" />…!

バイオインフォマティクスにおけるオントロジーの例

この講義では•!Bio-Ontologies•!多様なデータベースにおける知識表現と、そこからの知識抽出について学ぶ‒! UMLS: Uniﬁed Medical Language System‒!主に KEGG (Kyoto Encyclopedia of Genes andGenomes) を例に用いる‒! The Gene Ontology‒! オントロジーのオントロジー•! OBO, TAMBIS•!内容•!バイオインフォマティクスと関係の深いオントロジー言語。

‒!階層と関係による知識表現‒! SBML‒! MAGE-ML‒!その他の知識表現‒! CellML•!ルールベースと推論‒! CML‒!オントロジーとセマンティックウェブ‒! 様々なデータベースで XML 形式のデータを用意している‒!（情報検索とデータマイニング）•! パスウェイデータベースでは BioPAX など
27

データ統合による知識抽出
マイクロアレイ
遺伝子発現

26

類似度行列
（カーネル）‒!データ統合による知識抽出

28

カーネルN %&'()*+ x1 , x 2 ,..., x N !"#$ネットワーク
推定:;<# K (x, x!) -.678!9 x 5 x! $234

酵母２
ハイブリッド()*+,-./01!"#$%&'

細胞内
局在情報

タンパク質セットの類似度行列

系統
プロファイルK ij = K (x i , x j ) (i, j = 1,2,..., N )2930カーネルの例

カーネルの例!"#$%& :遺伝子 x1 , x 2 ,..., x N の塩基構成比& K (x1 , x1 ) K (x1 , x 2 ) # # &0.3 0.26 # #K = $$ K (x 2 , x1 ) K (x 2 , x 2 ) # !! = $$0.26 0.26 # !!
" !"!
"!"! %$ "
%$ "

&0.1#
&0.2#
$0.4!
$0.3!
' (x1 ) = $ !, ' (x 2 ) = $ !, ...
$0.2!
$0.3!
$ !
$ !
%0.3"
%0.2"

=

一種の類似度行列とみなせる

K (x1 , x 2 ) = " (x1 ) # " (x 2 )一種の遺伝子類似性ネットワーク= 0.1! 0.2 + 0.4 ! 0.3 + 0.2 ! 0.3 + 0.3 ! 0.2 = 0.2631

多様なデータとデータ型

32

多様なデータとデータ型

Data!

Type!

Microarray gene expression!

Numericalvector!

Protein interaction by Y2H!

Graph!

Subcellular localization!

Bit vector!

Phylogenetic profiles!

Bit vector!

数値ベクトル間の類似度を求める関数

K (x i , x j ) = exp(" || x i " x j ||2 / ! 2 )グラフ上の頂点間の類似度を求める関数
K = exp(! L)**+ L) !"#$"%"&'((Kondor, 2002)33

多様なデータとデータ型

34

教師なしの場合•! 各データにおける遺伝子間の距離をカーネル行列として定義‒! Kg: ゲノム上での遺伝子間の距離‒! Ke: 発現パターンの類似度‒! Kp: 系統プロファイルの類似度•! カーネルの和を取る‒! K = Kg + Ke + Kp•! 統合されたカーネル K を用いて遺伝子間の関係を変換•! 教師付き学習3536

教師付き学習の利用

教師付き学習•! Convert the relationship between
genes using the integrated kernel

発現データの類似度行列

タンパク質ネットワーク‒! Supervised learning approach can beused‒! Genes near in the pathway should benear in the projected space by the kernelUnknown pathway

37

教師付き学習発現データの類似度行列

教師付き学習タンパク質ネットワーク

発現データの類似度行列

トレーニングトレーニング38

トレーニングテスト

Unknown pathway

タンパク質ネットワーク

トレーニング

Unknown pathway

39

教師付き学習40

教師付き学習

元の空間

元の空間

x2

テスト

x1

x1

x3

x3
x2

：トレーニングセット
41: 教師なしで直接予測した結果：トレーニングセット
42

教師付き学習

教師付き学習ステップ１：相互作用するタンパク質ペアが近くにあるような特徴空間に射影
元の空間

元の空間

x1

x1

x3

f (x1 )

fx3
：真のネットワーク

x2

特徴空間

：真のネットワーク

x2：トレーニングセット：トレーニングセット

f (x 3 )f (x 2 )43

教師付き学習44

教師付き学習ステップ１：相互作用するタンパク質ペアが近くにあるような特徴空間に射影
元の空間

特徴空間

x1

fx3
：真のネットワーク

x2：トレーニングセット

元の空間

特徴空間

f (x1 )x1

f (x 3 )x3：真のネットワーク

x2

f (x 2 )：トレーニングセット：テストセット45

教師付き学習元の空間

f (x 2 )46

ステップ２：テストセットに関与するタンパク質間相互作用を予測

特徴空間

f

x3
x2

f (x 3 )教師付き学習ステップ２：テストセットに関与するタンパク質間相互作用を予測

x1f (x1 )f：真のネットワーク：トレーニングセット：テストセット

元の空間

特徴空間

f (x1 )x1

f (x 3 )x3x2

f (x 2 )47

f：真のネットワーク：トレーニングセット：テストセットf (x1 )f (x 3 )f (x 2 )48

アルゴリズム

性能評価
直接予測

K1 : -./'0)*+,!"

教師付き学習K 2 : #$%&'()*+,!"("1, "2) = arg max"1T K1K 2"2
1/ 2(1+ #" K " ) (1+ #" K " )
T
1 1

21 1T

22 2

1 2

1/ 2nf ( x ) = ! " 1 j K1 ( x j , x )j =1!

データの類似度行列が入力であることが特長
49

50

バクテリアの代謝系遺伝子の予測

バクテリアの代謝系遺伝子の予測
Lysine degradation of Pseudomonas aeruginosaOO
NH2HOONH2H2N

O
NH2

HOO

HOH

NH2

Glutaryl-CoA dehydrogenase"
OO

O

HO

Missing enzymes

O
CoA+" FAD"

FADH2" +"Glutaryl-CoA!

O

HOCoA

OH

+" CO2"

Crotonoyl-CoA

O

O

HOCoA

GcdH
MVGKASFNWIDPLLLDQQLTEEERMVRDSAYQFAQDKLAPRVLEAFRHEQTDPAIFREMG!
EVGLLGATIPEQYGGSGLNYVCYGLIAREVERIDSGYRSMMSVQSSLVMVPINEFGTEAQ!
KQKYLPKLASGEWIGCFGLTEPNHGSDPGSMITRARKVDGGYRLTGSKMWITNSPIADVF!
VVWAKDDAGDIRGFVLEKGWQGLSAPAIHGKVGLRASITGEIVMDNVFVPEENIFPDVRG!
LKGPFTCLNSARYGISWGALGAAEACWHTARQYTLDRQQFGRPLAANQLIQKKLADMQTE!
ITLALQGCLRLGRMKDEGTAAVEITSIMKRNSCGKALDIARMARDMLGGNGISDEFGVAR!
HLVNLEVVNTYEGTHDVHALILGRAQTGIQAFY!

緑膿菌のリジン分解系

5152

バクテリアの代謝系遺伝子の予測

バクテリアの代謝系遺伝子の予測

Lysine degradation of Pseudomonas aeruginosa

Lysine degradation Pseudomonas aeruginosa

OO
NH2HO

Citrate cycle

H2N

O
NH2O
NH2HOOHOO
HNH2HONH2?

O
H2N

NH2?

O
HONH2?

O

Lysine monooxygenase"

O

O

H

NH2HO+" O2"

H2N

NH2O

HOOH?
O

5-aminopentanamide!

O
OH+" CO2" +" H2O"

NH2

L-lysine!

?

O

HOO

O

HONH2HOOONo sequence data for any other species!

CoAGene: Unknown

HOO
CoA

Gene: Unknown
Citrate cycle

Citrate cycle

5354

予測方法

予測に使える情報•! 機能的に関連のあるタンパク質の遺伝子は、ゲノム上で近い位置にある傾向(Bork, P. et al. , 1998)

Known
O
NH2HO?

O
NH2H2N?

ONH2HO?

OO

HOH

NH2?
O

1.!Predicting network of 4,225 protein
genes in Pseudomonas, and extractlysine degradation pathway
2.!Candidate genes are extracted fromthe genes located between known
genes•! 機能的に関連のあるタンパク質は、同じような進化パターンを持つ傾向(Pazos, F., 2001; Pellegrini, M. et al, 1999)

OHOOH?
OO

HOCoA

Known
TCA cycle

55

系統プロファイル

カーネル（類似度の表現）•! Pellegrini et al.
‒! Proc. Natl. Acad. Sci. USA, 96:4285 (1999)•! オーソログ遺伝子のパターンを分類•! ゲノム上での位置
K gen (x, x!) = exp("d / h)E.coliS.cerevisiae

B.subtilis

H.influenzae!"#$101!"#%

110!"#&

56

同じパターンを持つ遺伝子は01
進化的・機能的に関連がある++,-d'()* x & x! !"#$%•! 系統プロファイル
K phy (x, x!) = x " x!

1!"#'

100!"#(011!"#)1

10**+,x!"#$%&'()•! 統合

K int = K gen + K phy

57

予測結果

58

まとめ
•!多様なデータベースにおける知識表現と、そこからの知識抽出について学ぶ‒!階層と関係による知識表現•!KEGG における PATHWAY の XML 表現および BRITEの階層分類‒!その他の知識表現•!ルールベースと推論

PA0262,260 (hypothetical)‒!オントロジーとセマンティックウェブ•!データベース間でのエントリーの相互参照

PA0265 (dehydrogenase) PA0266 (amino-transferase)‒!（情報検索とデータマイニング）‒!データ統合による知識抽出•!データ間の関連を利用して機能予測へ結びつける
59•!データベース間の統合が重要60

参考図書、文献、URL•!Baclawski, K. and Niu T.; Ontolgies for bioinformatics. (2006)
The MIT Press•!Genesereth, M.R. and Nilsson N.J. (古川康一訳); 人工知能基礎論. (1993) オーム社•!金久實（編）; ゲノムネットのデータベース利用法第３版. (2002)
共立出版•!http://www.genome.jp/ja/•!http://www.kegg.jp/ja/•!Yamanishi, Y. et al. Bioinformatics, 20, i363-i370 (2004).
•!Yamanishi, Y. et al. FEBS J, 274, 2262-2273 (2007).

61