Applied Topology

Applied Topology
平岡裕章
（広島大学）
内容
離散データの幾何モデル
--- 脈体、Čech複体、Vietoris-Rips複体
応用１：センサーネットワーク被覆問題
応用２：タンパク質の構造解析
背景
トポロジー
幾何対象を位相不変量から調べる
Hi (S ) =
n
�
Z,
0,
i = 0, n
o.w.
�
X
調べたい幾何対象について完全な情報が得られない場合は？
例：実験観測 X � = {xi ∈ Rn |i = 1, · · · K} ∼ X ⊂ Rn
問題点 ① 有限データ (K < ∞)
② 観測誤差 (0 < dist(xi , X) � 1)
ホモロジー群のような便利な道具を導入できるか？
Persistent ホモロジー群（Zomorodian，Carlsson）
その為に適した離散データに対する幾何モデルは？
脈体，Čech複体，Vietoris-Rips複体
離散データの幾何モデル
脈体（nerve complex）
やりたい事
H∗ (X) を
X の幾何学的対象具体的に計算したい
Ne
r
ve
T
X � Xsc：homotopy同値
Xsc
となる単体複体が
得られればよい
事実１
Xsc：単体複体
H∗ (Xsc ) は計算可能
he
o
re
m
事実２
X � Y ：homotopy同値
⇒ H∗ (X) � H∗ (Y )
脈体（nerve complex）
--- 定義（抽象単体複体）---
V V
∆
有限集合との空でない部分集合の集まりが次の条件を満たすとき
K = (V, ∆) を抽象単体複体とよぶ：
V の全ての元はに含まれる
∆
σ
σ ∈ ∆ ならばの空でない部分集合は全てに含まれる
∆
σ = {α0 , · · · , αk } ∈ ∆ k-単体とよぶ．
X：位相空間
X
U = {Uα }α∈A：の閉被覆
|A| < ∞
--- 定義（脈体）--次で与えられる抽象単体複体 U の脈体とよぶ：
N (U) = (A, ∆) を σ = {α0 , · · · , αk } ∈ ∆
Uα0 ∩ · · · ∩ Uαk �= ∅
X：位相空間
X
U = {Uα }α∈A：の閉被覆
|A| < ∞
--- 定義（脈体）--次で与えられる抽象単体複体 U の脈体とよぶ：
N (U) = (A, ∆) を σ = {α0 , · · · , αk } ∈ ∆
Uα0 ∩ · · · ∩ Uαk �= ∅
--- 脈体定理 ---
∩α∈S Uα が空もしくは可縮ならば
任意の ∅=
� S ⊂ A について X � N (U) homotopy同値
�
�
�
�
注）脈体定理はもう少し一般の設定でも成り立つ
Čech複体
有限データ V = {x ∈ RN }, |V | < ∞
B� (V ) := {B� (x) | x ∈ V } : � -球による被覆
ˇ
�) := N (B� (V ))
--- 定義 --- Čech複体 C(V,
�
�
�
脈体定理より
ˇ
�)
系： ∪x∈V B� (x) � C(V,
欠点：複数の球の共通部分を調べることは困難
Vietoris-Rips複体
--- 定義 ---
�>0
V = {x ∈ RN } とに対して次で与えられる
有限データ V R(V, �) = (V, ∆)
単体複体をVietoris-Rips複体とよぶ：
σ = {x0 , · · · , xk } ∈ ∆
B� (xi ) ∩ B� (xj ) �= ∅, 0 ≤ ∀i, j ≤ k
V R(V, �) は構成可能
２点間の距離のみで ∪x∈V B� (x) とのホモトピー不変性は一般には不明
Čech複体
�
�
ˇ
C(V,
�)(1) = V R(V, �)(1)
Vietoris-Rips複体
ˇ
ˇ
C(V,
�) ⊆ V R(V, �) ⊆ C(V,
2�)
重み付きČech複体，重み付きVietoris-Rips複体
有限データ V = {xi ∈ RN | i = 1, · · · , K}
--- 定義 --�i > 0 として作られる
xi ∈ V ごとに球の半径を Čech複体とVietoris-Rips複体をそれぞれ重み付き Čech複体，
重み付きVietoris-Rips複体とよぶ
Čech複体，Vietoris-Rips複体によるモデリング
センサーネットワーク（Ghrist）
各センサーをノード，センシング領域や
通信領域により球を構成
タンパク質ファンデルワールス球体表現
センサーネットワークへの応用（by Ghrist）
領域被覆問題
--- Intl. J. Robotics Research. 25, 1205-1222, 2006
--- Notices American Mathematical Society, 54, 10-17, 2007
ターゲットカウント
SIAM J. Appl. Math. 70, 825-844, 2009
Ghristのwebpage: http://www.math.upenn.edu/~ghrist/
センサーネットワーク
センサーネットワーク：
小型センサーを対象領域にたくさん配置し，各センサーか
らの局所的な情報を統合して大域的な情報を抽出する
１．ネットワーク層での研究
各センサーからくる膨大な情報の統合方法，効率
的なデータ伝搬
２．アプリケーション層での研究
どのような有益な情報を抜き出せるか
------- 制約条件：各センサーは低性能 ------領域被覆問題を１，２の観点から調べてみる
領域被覆問題
：センサーの計測領域
rc
（半径）
D：領域
領域被覆問題
：センサーの計測領域
rc
（半径）
D：領域
D⊂
�
xi :sensor
Brc (xi ) or not ?
従来の手法
センサーの絶対位置がわかっている（GPS等を搭載）
--- 計算幾何的扱い（ボロノイ図など）
--- 携帯の基地局設計などでは有用
---（小型）センサーにとって絶対位置の情報は仮定したくない
センサーが対象領域内で一様に分布している
--- 確率論的扱い
--- 一様分布という仮定は強すぎる
問題設定
D ⊂ R2
対象領域はコンパクトかつ連結
∂D は連結かつその上のノードが定める
境界（フェンス）区分線形な線分
P := {xi ∈ D | i = 1, · · · , N } ノード（センサー）の集合
rb ：通信半径（半径 rb 円内にある他のセンサーと通信可能）
rb 以下
∂D
の隣接ノード間距離は rb
r
rc 円内を計測），rc ≥ √
c ：センシング半径（半径 3
�
U=
Brc (xi ) ：センシング領域
xi ∈P
領域被覆問題： D ⊂ U ?
ˇ
rc )
センシングČech複体 C(P,
センシング領域 U =
�
xi ∈P
ˇ
Brc (xi ) � C(P,
rc )
短所：個々のセンサーのセンシング領域の共通部分を
調べることは大変
通信 Vietoris-Rips 複体 R = V R(P, rb /2)
長所：構成することは容易（ノード間で通信可能かどう
かを判定するだけ）
短所：センシング領域のトポロジーを正確に反映しない
場合がある
H1 (U ) = 0 but H1 (V R) = Z
穴なし
穴あり
R ⊃ F ：境界ノードによって定まる１次元部分複体
被覆定理（de Silva & Ghrist）
[σ] ∈ H2 (R, F) が存在し δ[σ] �= 0 (∈ H1 (F)) となるならば
D ⊂ U となる．（つまりセンサー達は領域を被覆している）
δ
→ H2 (F) → H2 (R) → H2 (R, F) → H1 (F) →
Remark ① センサーの絶対位置の情報は仮定しない
（局所的な接続情報から大域的な被覆情報を抜き出す）
② 穴があいている場合の修復方法
③ 省エネモード
④ ターゲット追跡問題
⑤ ３次元被覆問題への拡張
p : R → R2
R2
VR複体 R からへの実現
σ = |x0 · · · xn | �→ p(σ) = conv(x0 , · · · , xn )
x0 , · · · , xn で作られる凸包
σ
p(σ)
補題：をVR複体 R の単体とすると，は被覆領域 U に含まれる
証明の概略）２単体の場合を考えれば十分．
２単体を構成していて，かつ最も各ノードが離れている
rb の正三角形
状況は一辺 rc
σ
rb
p : R → R2
R2
VR複体 R からへの実現
σ = |x0 · · · xn | �→ p(σ) = conv(x0 , · · · , xn )
x0 , · · · , xn で作られる凸包
σ
p(σ)
補題：をVR複体 R の単体とすると，は被覆領域 U に含まれる
証明の概略）２単体の場合を考えれば十分．
２単体を構成していて，かつ最も各ノードが離れている
rb の正三角形
状況は一辺 √
rc ≥ rb / 3
σ
rb
被覆定理： ∃[σ]
定理の証明）
H2 (R)
↓ p∗
[σ ] ∈
→
H2 (R, F)
↓ p∗
δ
→
∈ H2 (R, F) s.t. δ[σ] �= 0 ⇒ D ⊂ U
H1 (F)
� p∗
→
···
→ H2 (R2 ) → H2 (R2 , ∂D) → H1 (∂D) → H1 (R2 ) → · · ·
δ
→
H1 (R)
↓ p∗
···
→ ···
0 �= p∗ δ[σ] = δp∗ [σ] ⇒ p∗ [σ] �= 0
q ∈ D \ U をとる
D�U
として補題から p(R) ⊂ U なのでとなり
q∈
/ p(R)
q
p : (R, F) → (R2 , ∂D) を分解する：
−→
−→
H2 (R2 − q, ∂D)
p¯∗
i∗
p∗
H2 (R, F) −→ H2 (R2 , ∂D)
−→
−→
(R2 − q, ∂D)
p¯
i
p
(R, F) −→ (R2 , ∂D)
H2 (R2 − q, ∂D) = 0 より p∗ [σ] = i∗ p¯∗ [σ] = 0 矛盾．
被覆定理の実用化に向けて
問題点：だれがどうやってホモロジー群を計算するか？
各ノードが基地局に単体の情報を送り，
そこでホモロジー群を計算することになる
バッテリーの制限から長距離通信は行いたくない
ホモロジー群の計算は３次オーダー
局所分散的な計算を積み上げてホモロジー群を計算したい
Mayer-Vietoris完全系列を用いた分散型ホモロジー群計算
（荒井，林，平岡）
分散型ホモロジー群計算アルゴリズム
Mayer-Vietoris完全系列：
→ Hk (R1 ∩ R2 ) → Hk (R1 ) ⊕ Hk (R2 ) → Hk (R1 ∪ R2 ) → Hk−1 (R1 ∩ R2 ) →
R
アルゴリズムの流れ
1
通信VR複体の分割
R
2
R=
K
�
Ri
i=1
各部分VR複体で
H∗ (Ri ), H∗ (Ri ∩ Rj )
を並列的に計算
R
4
R
3
Mayer-Vietoris完全系
H∗ (R)
列からを計算
補題（Chambers, et al.）:
R が平面VR複体ならば H1 (R) は自由加群
π1 (R) � π1 (S) が成立するので
証明概略） S = p(R) ⊂ R2 としたとき仮定の追加
S = p(R) ⊂ D
仮定：（non-pinching
condition）
shadow path
GOOD
BAD
命題：以下の条件は同値である
δ[σ] �= 0
[σ] ∈ H2 (R, F)
（１）となるが存在する（被覆定理の仮定）
j : H1 (R) → H1 (R, F)
（２）は同型写像
i : H1 (F) → H1 (R)
（３）は
i=0
（４）H1 (R) = 0
δ
i
j
→ H2 (F ) → H2 (R) → H2 (R, F ) → H1 (F ) → H1 (R) → H1 (R, F ) →
Remark: １次のホモロジー群までを扱えば十分となる
証明概略）２→３，４→１は明らか．
j
δ
i
j
→ H1 (R, F ) → H0 (F ) →
１→２：の全射性は
Z � H1 (F) ⊃ Im δ � cZ, c �= 0
単射性は，より
H1 (F)/Ker i � H1 (F)/Im δ � Z/cZ � Zc
c = 1 δ : H2 (R, F) → H1 (F) が全射
一方は自由加群なので． H1 (R)
j
になるのでは単射．
π1 (R) � π1 (S) = 0
S=D
３→４：を示す．これと補題より．
R1 , R2 が
命題：VR複体 H0 (R1 ) � H0 (R2 ) � Z,
H0 (R1 ∩ R2 ) � Zr , r ≥ 0
H1 (R1 ) � Zn , H1 (R2 ) � Zm
ならば
H1 (R1 ∪ R2 ) �
�
Zn+m+r−L−1 , r ≥ 1
Zn+m−L ,
r=0
L
となる．ここではMayer-Vietoris完全系列
i
→ H1 (R1 ∩ R2 ) → H1 (R1 ) ⊕ H1 (R2 ) → H1 (R1 ∪ R2 ) →
の L = rank i.
数値計算
D
領域：200×100の長方形
分割：縦方向に1，2，5分割
100
0
200
数値計算に用いたホモロジー群計算のオーダー
3000
2500
３次曲線
CPU時間
2000
1500
1000
500
2単体の数
0
0
200
400
600
800
1000
1200
1400
数値計算例１
#{2単体} = 426,
#{1単体} = 295,
#{0単体} = 68
分割数：１２５
計算時間： 589 138 6
（CPU）
数値計算例２
#{2単体} = 519,
#{1単体} = 184,
#{0単体} = 30
分割数：１２５
計算時間： 81 49 1
（CPU）
課題
計算量の数学的な評価
non-pinching条件を仮定しないで分散計算を行う
実装（実験用センサー：１個１-２万円）
一般的な設定でのホモロジー群分散計算アルゴリズム
タンパク質の構造解析
タンパク質：２０種類のアミノ酸が多数結合してできている高分子
生命活動の基本単位
Protein Data Bank: タンパク質の立体構造に関するデータベース
（X線構造解析結果）
Welcome to PDBj - トップページ
English
Korean
Japanese
トップページ
データ登録 >>
ADIT: PDB
Deposition
ADIT-NMR
検索 >>
Search PDB
(Mine/xPSSS)
Latest Released
Search
SequenceNavigator
StructureNavigator
SeSAW
Ligand Binding
Sites (GIRAF)
EM Navigator
Search NMR
Data (BMRB)
Status Search
サービス&ソフト
ウェア >>
j V: Graphic
simplified Chinese
traditional Chinese
統計情報
日本蛋白質構造データバンク（PDBj: Protein Data Bank
Japan)は、JST-BIRDの支援を受け、米国RCSB、BMRB、お
よび欧州PDBeと協力して、生体高分子の立体構造データベー
スを国際的に統一化されたアーカイブとして運営するととも
に、様々な解析ツールを提供しております。
データ登録
データ登録のご案内
>>
NMRデータ登録
PDB登録
検索
PDB検索
NMRデータ検索
Mine日本語ページについて
PDB ID or Keyword
Go
詳細条件検索 >>
Accession number
Deposition code
Go
10/11/03 9:33
ヘルプ FAQ お
問い合わせ
68998
entries available
on 3 Nov., 2010
00:00(UTC) / 09:00(JST)
ここにタンパク質
名を入力
（例）ペルオキシダーゼ（ID: 1w4w）
PDBj Mine 概要ページ : 1w4w
統計情報
Japanese
トップページ
データ登録 >>
ヘルプ
10/11/03 9:36
FAQ
日本蛋白質構造データバンク（PDBj: Protein Data Bank Japan)は、JST-BIRDの支援を受け、米
国RCSB、BMRB、および欧州PDBeと協力して、生体高分子の立体構造データベースを国際的に統一化され
たアーカイブとして運営するとともに、様々な解析ツールを提供しております。
タンパク質の立体
ADIT: PDB
Deposition
ADIT-NMR
概要[1w4w]
検索 >>
Search PDB
(Mine/xPSSS)
Latest Released
Search
SequenceNavigator
StructureNavigator
SeSAW
Ligand Binding
Sites (GIRAF)
EM Navigator
<非対称単位>
エントリーID (PDB ID)
関連構造のPDB ID
Status Search
j V: Graphic
Viewer
Protein Globe
ASH
MAFFTash
日本語ページについて
構造に関する
PDBj Mineについて
情報が得られる
更新情報
PDB ID or Keyword
Search NMR
Data (BMRB)
サービス&ソフト
ウェア >>
お問い合わせ
分子名称
（回転なし）他の画像...
3次元構造ビューア
jV3 / Jmol
(jV3 と Jmol には
Java(TM)Plug-in 1.5以上が必要で
タイトル
1w4w 配列情報 (FASTA形
式) PDBファイルのダウンロード
1atj, 1gw2, 1gwo, 1gwt,
1gwu, 1gx2, 1h55, 1h57,
1h58, 1h5a, 1h5c, 1h5d,
1h5e, 1h5f, 1h5g, 1h5h,
1h5i, 1h5j, 1h5k, 1h5l,
1h5m, 1hch, 1kzm, 1w4y,
2atj, 3atj, 4atj, 6atj, 7atj
HORSERADISH
PEROXIDASE C1A
(E.C.1.11.1.7)
FERRIC HORSERADISH
PEROXIDASE C1A IN
COMPLEX WITH
FORMATE
OXIDOREDUCTASE, 3D-
検索
（例）ペルオキシダーゼ（ID: 1w4w）の取得データ
http://www.pdbj.org/pdb_nc/pdb1w4w.ent
HEADER
TITLE
COMPND
COMPND
COMPND
COMPND
COMPND
COMPND
SOURCE
SOURCE
SOURCE
SOURCE
SOURCE
SOURCE
KEYWDS
KEYWDS
KEYWDS
EXPDTA
AUTHOR
REVDAT
REVDAT
JRNL
JRNL
JRNL
JRNL
JRNL
JRNL
JRNL
JRNL
REMARK
REMARK
REMARK
REMARK
REMARK
REMARK
REMARK
REMARK
REMARK
REMARK
REMARK
REMARK
OXIDOREDUCTASE
03-AUG-04
1W4W
FERRIC HORSERADISH PEROXIDASE C1A IN COMPLEX WITH FORMATE
MOL_ID: 1;
2 MOLECULE: HORSERADISH PEROXIDASE C1A;
3 CHAIN: A;
4 EC: 1.11.1.7;
5 ENGINEERED: YES;
6 OTHER_DETAILS: A FORMATE ION IS BOUND IN THE ACTIVE SITE
MOL_ID: 1;
2 ORGANISM_SCIENTIFIC: ARMORACIA RUSTICANA;
3 ORGANISM_COMMON: HORSERADISH;
4 ORGANISM_TAXID: 3704;
5 EXPRESSION_SYSTEM: ESCHERICHIA COLI;
6 EXPRESSION_SYSTEM_TAXID: 562
OXIDOREDUCTASE, 3D-STRUCTURE, FORMATE ION, CALCIUM, FERRIC
2 STATE, GLYCOPROTEIN, HEME, HORSERADISH, IRON, MULTIGENE
3 FAMILY, PEROXIDASE, PYRROLIDONE CARBOXYLIC ACID, SIGNAL
X-RAY DIFFRACTION
G.H.CARLSSON,P.NICHOLLS,D.SVISTUNENKO,G.I.BERGLUND,J.HAJDU
2
24-FEB-09 1W4W
1
VERSN
1
19-JAN-05 1W4W
0
AUTH
G.H.CARLSSON,P.NICHOLLS,D.SVISTUNENKO,G.I.BERGLUND,
AUTH 2 J.HAJDU
TITL
COMPLEXES OF HORSERADISH PEROXIDASE WITH FORMATE,
TITL 2 ACETATE, AND CARBON MONOXIDE
REF
BIOCHEMISTRY
V. 44
635 2005
REFN
ISSN 0006-2960
PMID
15641789
DOI
10.1021/BI0483211
1
1 REFERENCE 1
1 AUTH
G.I.BERGLUND,G.H.CARLSSON,A.T.SMITH,H.SZOKE,
1 AUTH 2 A.HENRIKSEN,J.HAJDU
1 TITL
THE CATALYTIC PATHWAY OF HORSERADISH PEROXIDASE AT
1 TITL 2 HIGH RESOLUTION
1 REF
NATURE
V. 417
463 2002
1 REFN
ISSN 0028-0836
1 PMID
12024218
1 DOI
10.1038/417463A
1 REFERENCE 2
1 AUTH
A.T.SMITH,N.SANTAMA,S.DACEY,M.EDWARDS,R.C.BRAY,
10/11/03 9:45
誰が、いつ、どうやって、
どんな環境で実験して得ら
れたデータかが載っている
SITE
4 AC3 25 GLY A 169 HIS A 170 PHE A 172 GLY A 173
SITE
5 AC3 25 LYS A 174 ASN A 175 GLN A 176 PHE A 179
SITE
6 AC3 25 PHE A 221 SER A 246 FMT A1310 HOH A2353
SITE
7 AC3 25 HOH A2354
SITE
1 AC4 5 ARG A 38 PHE A 41 HIS A 42 HEM A1307
SITE
2 AC4 5 HOH A2189
CRYST1
40.330
68.302 117.048 90.00 90.00 90.00 P 21 21 21
4
ORIGX1
1.000000 0.000000 0.000000
0.00000
ORIGX2
0.000000 1.000000 0.000000
0.00000
ORIGX3
0.000000 0.000000 1.000000
0.00000
ファイルの途中から
SCALE1
0.024795 0.000000 0.000000
0.00000
原子の空間座標データが始まる
SCALE2
0.000000 0.014641 0.000000
0.00000
SCALE3
0.000000 0.000000 0.008544
0.00000
グルタミン
ATOM
1 N
GLN A
1
27.178 16.649 15.783 1.00 26.78
ATOM
2 CA GLN A
1
26.756 15.666 16.822 1.00 24.87
ATOM
3 C
GLN A
1
25.529 16.146 17.589 1.00 23.01
ATOM
4 O
GLN A
1
25.581 17.171 18.267 1.00 23.79
ATOM
5 CB GLN A
1
27.896 15.425 17.818 1.00 26.64
ATOM
6 CG GLN A
1
29.093 14.680 17.252 1.00 28.43
ATOM
7 CD GLN A
1
28.821 13.203 17.036 1.00 29.14
ATOM
8 OE1 GLN A
1
29.684 12.465 16.563 0.00 29.08
ATOM
9 NE2 GLN A
1
27.617 12.764 17.388 0.00 29.08
ATOM
10 N
LEU A
2
24.429 15.405 17.484 1.00 19.34
ATOM
11 CA LEU A
2
23.215 15.765 18.204 1.00 17.22
ATOM
12 C
LEU A
2
23.460 15.514 19.688 1.00 17.26
ATOM
13 O
LEU A
2
24.194 14.597 20.050 1.00 19.22
ATOM
14 CB LEU A
2
22.033 14.917 17.722 1.00 14.98
ATOM
15 CG LEU A
2
21.687 15.012 16.232 1.00 14.35
ATOM
16 CD1 LEU A
2
20.440 14.184 15.950 1.00 12.62
ATOM
17 CD2 LEU A
2
21.454 16.464 15.839 1.00 14.43
ATOM
18 N
THR A
3
22.849 16.330 20.541 1.00 15.96
ATOM
19 CA THR A
3
23.013 16.190 21.986 1.00 16.22
ATOM
20 C
THR A
3
21.703 16.503 22.707 1.00 15.16
ATOM
21 O
THR A
3
20.991 17.435 22.340 1.00 15.46
ATOM
22 CB THR A
3
24.118 17.133 22.511 1.00 17.01
ATOM
23 OG1 THR A
3
24.193 17.036 23.938 1.00 20.44
X
Y
Z
N
C
C
O
C
C
C
O
N
N
C
C
O
C
C
C
C
N
C
C
O
C
O
ATOM
ATOM
ATOM
ATOM
ATOM
ATOM
ATOM
ATOM
ATOM
ATOM
ATOM
ATOM
ATOM
ATOM
ATOM
ATOM
ATOM
ATOM
ATOM
ATOM
ATOM
ATOM
ATOM
ATOM
ATOM
ATOM
ATOM
ATOM
ATOM
ATOM
ATOM
ATOM
ATOM
ATOM
TER
HETATM
2367 CG
2368 CD
2369 NE
2370 CZ
2371 NH1
2372 NH2
2373 N
2374 CA
2375 C
2376 O
2377 CB
2378 CG1
2379 CG2
2380 N
2381 CA
2382 C
2383 O
2384 CB
2385 CG1
2386 CG2
2387 N
2388 CA
2389 C
2390 O
2391 CB
2392 CG
2393 OD1
2394 ND2
2395 N
2396 CA
2397 C
2398 O
2399 CB
2400 OG
2401
2402 FE
ARG
ARG
ARG
ARG
ARG
ARG
VAL
VAL
VAL
VAL
VAL
VAL
VAL
VAL
VAL
VAL
VAL
VAL
VAL
VAL
ASN
ASN
ASN
ASN
ASN
ASN
ASN
ASN
SER
SER
SER
SER
SER
SER
SER
HEM
A 302
A 302
A 302
A 302
A 302
A 302
A 303
A 303
A 303
A 303
A 303
A 303
A 303
A 304
A 304
A 304
A 304
A 304
A 304
A 304
A 305
A 305
A 305
A 305
A 305
A 305
A 305
A 305
A 306
A 306
A 306
A 306
A 306
A 306
A 306
A1307
1.981
0.599
-0.247
-0.994
-1.014
-1.709
5.825
6.496
7.938
8.321
5.742
4.314
5.743
8.736
10.133
10.136
9.262
10.909
12.363
10.811
11.105
11.173
11.396
12.104
12.301
12.086
10.956
13.175
10.788
10.930
11.248
11.104
9.646
8.549
23.903
24.519
23.676
22.674
22.386
21.947
26.009
26.712
27.077
27.222
28.009
27.684
28.947
27.219
27.598
29.088
29.821
27.361
27.769
25.893
29.537
30.950
31.820
31.430
31.211
30.506
30.192
30.272
33.002
33.932
35.333
35.535
33.967
34.418
8.073
8.262
9.101
8.648
7.353
9.495
6.221
5.138
5.448
6.605
4.783
4.365
5.981
4.397
4.543
4.869
4.410
3.226
3.392
2.826
5.661
6.018
4.786
3.857
7.020
8.345
8.723
9.070
4.785
3.671
4.182
5.407
2.839
3.613
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
13.76
15.08
14.33
15.46
15.08
14.81
12.64
14.04
14.17
14.87
15.38
15.00
16.92
15.12
16.69
17.75
16.78
17.96
19.23
17.62
18.79
19.62
22.42
22.69
18.32
16.69
15.74
16.15
25.14
27.47
27.76
29.09
27.30
31.23
3.082
1.872
11.482
1.00
8.68
セリン
C
C
N
C
N
N
N
C
C
O
C
C
C
N
C
C
O
C
C
C
N
C
C
O
C
C
O
N
N
C
C
O
C
O
FE
Rasmol：PDBファイルをもとに３次元描画をするソフトウェア
RasMol and OpenRasMol
10/11/03 10:10
visits since 28 Sep
2000
www.RasMol.org and www.OpenRasMol.org
| Copying and Distribution | Contents | Software Distributions | Latest Windows Installer | External
Packages |
| RasMol Manual | Frequently Asked Questions | RasMol 2.7 Series History | RasMol and OpenRasMol |
| RasMol GForge Site | Click Here to Make a Donation | RasMol SourceForge Site |
Home Page
for
RasMol and OpenRasMol
Molecular Graphics Visualisation Tool
RasMol Latest Windows
Installer
RasMol 2.7.5 Windows
Installer
RasMol Latest Source Tarball
RasMol 2.7.5 Source Tarball
RasMol Latest Manual
RasMol 2.7.5 Manual
Donate to Support RasMol
Register your RasMol
Donate to Support RasMol
Register your RasMol
（例）ジヒドロ葉酸還元酵素（3fl9）
ある生命科学者と話をしていると
PDBに詳細なデータがたくさんあるけど、さらなる有益な情報の
とりだし方をいろいろ知りたがっている
らしい
「例えばタンパク質の柔らかさの指針である圧縮率をPDBデータ
から推定できませんか？」
と尋ねられました。
背景：タンパク質の静的な構造情報としてX線構造解析データがあるが，
実際には常にゆらいでいて，このゆらぎが機能発現に重要．
このゆらぎ具合をはかる大事な指標の一つが圧縮率．
さらに圧縮率を実験でもとめるのは大変で知られていない
タンパク質もたくさんある．
（らしい）
さらに生命科学者と話をしていると
「Rasmolで描画させて調べてると，穴が気になることがあるけど
これって数学的に扱えないんですか？柔らかさに関係しそうなん
ですが、、、」
ということでホモロジー群と圧縮率を
キーワードに議論を進めてみました
予想する傾向：
トンネル（b1）や空洞（b2）が多い
タンパク質の圧縮率は大きい（つまり
柔らかい）だろう
数学的な問題設定：
タンパク質のモデリング
P = {pi ∈ R3 | pi : atom} ：PDBによる原子の空間座標データ
原子は以下の６種類：水素，炭素，窒素，酸素，硫黄，リン
ファンデルワールス半径
rh = 1.2, rc = 1.7, rn = 1.55, ro = 1.52, rs = 1.8, rp = 1.8
ˇ
{ratom })
重み付き Čech複体 C(P,
計算量的にとても大変なのでパス
重み付き VR複体 V R(P, {ratom })
ファンデルワールス半径パラメータ �
betti
X� = V R(P, {Ratom,� })
Ratom = � × ratom
1
�
数値計算による観察：b1 persistence
b1
b1 persistence
600
1a4v
1avu
1ca2
1e7i
1giw
1h02
1ig8
1kde
1mbo
1ova
1ryx
1w4w
1zen
2kef
2lyz
2mlt
2ptn
3blg
3dfr
3etd
3ilg
3nbs
5lip
5rsa
8cat
500
400
300
200
100
0
0.4
0.6
0.8
1
1.2
1.4
1.6
1.8
2
ε
数値計算による観察：b2 persistence
b2
b2 persistence
100
1a4v
1avu
1ca2
1e7i
1giw
1h02
1ig8
1kde
1mbo
1ova
1ryx
1w4w
1zen
2kef
2lyz
2mlt
2ptn
3blg
3dfr
3etd
3ilg
3nbs
5lip
5rsa
8cat
90
80
70
60
50
40
30
20
10
0
0.4
0.6
0.8
1
1.2
1.4
1.6
1.8
2
ε
数値計算による観察：b1 & b2 persistence
b2
b1 & b2 persistence
600
500
400
300
200
100
0
0.4
0.6
0.8
1
1.2
1.4
1.6
1.8
2
ε
b1 persistence
600
b2 persistence
100
1a4v
1avu
1ca2
1e7i
1giw
1h02
1ig8
1kde
1mbo
1ova
1ryx
1w4w
1zen
2kef
2lyz
2mlt
2ptn
3blg
3dfr
3etd
3ilg
3nbs
5lip
5rsa
8cat
500
400
300
200
100
1a4v
1avu
1ca2
1e7i
1giw
1h02
1ig8
1kde
1mbo
1ova
1ryx
1w4w
1zen
2kef
2lyz
2mlt
2ptn
3blg
3dfr
3etd
3ilg
3nbs
5lip
5rsa
8cat
90
80
70
60
50
40
30
20
b1 & b2 persistence
600
500
400
300
200
100
10
0
0.4
0.6
0.8
1
1.2
1.4
1.6
1.8
2
0
0.4
b1 persistence
0.6
0.8
1
1.2
1.4
1.6
1.8
2
b2 persistence
0
0.4
0.6
0.8
1
1.2
1.4
1.6
b1&b2 persistence
0.4 < ε < 0.8の局所ピーク
--- 0.4 < ε < 0.7に b1ピーク，その直後 0.7 < ε < 0.8に b2ピーク
b1，b2ともに最大ピーク点は ε = 1 より大きい
さらに ε = 1 では b2 =０
b1の方がb2よりも滑らか
1.8
2
0.4 < ε < 0.8の局所ピーク
400
Peroxidase(1w4w) b1
Peroxidase(1w4w) b2
350
300
250
200
150
100
50
0
0.4
0.6
0.8
1
1.2
1.4
1.6
1.8
2
0.4 < ε < 0.8の局所ピーク
ε=1での状態（b1=b2=0）
答え：ベンゼン環
r = 0.5
r = 0.73
400
Peroxidase(1w4w) b
Peroxidase(1w4w) b
350
300
250
200
150
100
50
0
0.4
0.6
b1とb2で数が異なるのはなぜ？
0.8
1
1.2
1.4
1.6
1.8
0.4 < ε < 0.8の局所ピーク
答え：イミダゾール
r = 0.5
r = 0.73
400
Peroxidase(1w4w) b
Peroxidase(1w4w) b
350
300
250
200
150
100
50
0
0.4
0.6
0.8
ループがつぶれても
空洞はでない
1
1.2
1.4
1.6
1.8
数値計算による観察：アミノ酸数に対するb1, b2 の最大値
b1 max
b2 max
proteinsize vs b1max
600
proteinsize vs b2max
100
90
500
80
400
300
200
100
0
0
100
200
300
400
1a4v
1avu
1ca2
1e7i
1giw
h02
1ig8
1kde
1mbo
1ova
1ryx
1w4w
1zen
2kef
2lyz
2mlt
2ptn
3blg
3dfr
3etd
3ilg
3nbs
500 5lip
5rsa
8cat
70
60
50
40
30
20
10
600
700
0
0
100
200
300
400
アミノ酸数
1) アミノ酸数小 → 線形性，アミノ酸数大 → ずれ
2) 正規化してみても柔らかい（固い）タンパク質が上（下）にある傾向
は見えない
3) 半径をあまり大きくすると偽の空洞が現れる
4) そこでもう一度 persistence を観察すると、、、
1a4v
1avu
1ca2
1e7i
1giw
h02
1ig8
1kde
1mbo
1ova
1ryx
1w4w
1zen
2kef
2lyz
2mlt
2ptn
3blg
3dfr
3etd
3ilg
3nbs
500
5lip
5rsa
8cat
600
700
アミノ酸数
数値計算による観察：b2 persistence
b2
b2 persistence
100
1a4v
1avu
1ca2
1e7i
1giw
1h02
1ig8
1kde
1mbo
1ova
1ryx
1w4w
1zen
2kef
2lyz
2mlt
2ptn
3blg
3dfr
3etd
3ilg
3nbs
5lip
5rsa
8cat
90
80
70
局所ピークあり
60
50
40
30
20
10
0
0.4
0.6
0.8
1
1.2
1.4
1.6
1.8
2
ε
1.0 < ε < 1.2 の局所ピーク
b2／#{アミノ酸}
0.07
b2 persistence
1avu
1e7i
1mbo
2ptn
3etd
3ilg
5rsa
0.06
0.05
柔いタンパク質
（1e7i, 1mbo, 3etd, 3ilg）
0.04
固いタンパク質
（1avu, 2ptn, 5rsa）
0.03
0.02
傾向をつかめてそうに
見える
0.01
0
1
1.05
1.1
1.15
1.2
1.25
ε
今後の課題１：「圧縮率」の「homological」な定義は可能か？
サンプルを増やしてさらに傾向を調べる
別の幾何モデルを考える
今後の課題２：computational topology のその他の応用はあるか？
タンパク質の穴の生成元が網羅的にわかることはちょっと
驚きだったらしい
タンパク質の形が徐々に変わっていく際の生成元の変化を詳細
に調べたいらしい
最小生成元の特徴付けはできる？
Persistent Homologyの応用
参考文献：
Applied Topology 全般
Edelsbrunner & Harer, Computational Topology: An Introduction,
AMS 2010.
離散データ解析
Carlsson, Topology and Data, Bulletin of AMS, 255-308, 2009.
センサーネットワークやロボティックスへの応用
Ghristのwebpage: http://www.math.upenn.edu/~ghrist/

Download Report