DEIM Forum 2017 E4-1

ラベル情報と構造情報の相関を用いた三次元点集合マッチングの高速化とそのインフルエンザウイルス解析への応用
佐々木耀一†

渋谷哲朗††

大森 亮介†††

伊藤 公人†††

有村 博紀†† 北海道大学大学院情報科学研究科 〒 060–0814 札幌市北区北 14 条西 9 丁目†† 東京大学医科学研究所ヒトゲノム解析センター 〒 108–8639 東京都港区白金台 4-6-1††† 北海道大学人獣共通感染症リサーチセンター 〒 001–0020 札幌市北区北 20 条西 10 丁目
E-mail: †{ysasaki,arim}@ist.hokudai.ac.jp, ††tshibuya@hgc.jp, †††{omori,itok}@czc.hokudai.ac.jp
あらまし

本稿では頂点ラベル付き三次元点集合の照合アルゴリズムを考察する．先行研究において，ラベルなしの点集合データに対して，我々は可能なマッチングの全列挙とスコアの下限見積もりを用いた照合アルゴリズムを提案した． また，タンパク質データなど，生物分野の三次元点集合データでは ラベル情報に基づく距離 (正規化ハミング距離) と構造情報に基づく距離 (RMSD) の間に近似的な相関関係があることが経験的に知られている．本稿では，このような相関関係を用いてラベル情報に基づく距離の下限見積もりを用いた高速化手法を提案する．実験では，インフルエンザウイルスデータを対象として，実際のデータから上記の下限関数を経験的に求め，さらにその有効性を検証した．
キーワード パターン照合，分枝限定法，列挙アルゴリズム，RMSD, 最小二乗和平均平方根距離，正規化ハミング距
離，点集合マッチング

1. は じ め に
1. 1 背景.

1. 3 関 連 研 究
本論文の関連研究として，Schwartz と Sharir [3] はデータベースとパターンを共に点列の入力とし，RMSD 指標による近年，タンパク質や高分子の三次元構造の高速な検索は重要マッチングを考察し，データベースサイズを N としたときにな問題になっている．例えば，あるタンパク質の構造が与えらO(N log N) 時間で実行するアルゴリズムを提案している．また，れているが，その性質がわかっていないときに，既に構造と性

Shibuya [2] は，同じマッチング問題を，データベースサイズに質が知られているタンパク質との構造的に類似しているかを調対して線形時間で実行するアルゴリズムを提案している．そのべることにより，性質を予想することが行われている [1]．

他に，Akutsu [4] らは，ハッシュを用いた手法を提案しており，我々は，タンパク質の構造を三次元空間に分布する点集合とO(N) 期待計算時間を実現している．また，Shibuya [1] は，幾とらえて，二つの点集合 P と T の間の三次元点集合マッチン

何接尾辞木 (geometric suﬃx tree) と呼ばれる，三次元構造に対グ問題を考察し，高速なアルゴリズムを提案した [10] [9]．このする索引データ構造を示している．これは，文字列に対する索アルゴリズムは，点集合の構造の類似距離には平行移動と回転引構造である接尾辞木 (suﬃx tree) [6], [7] を基に，タンパク質のに関する最小二乗和平方距離（RMSD）を採用し，その上限推ような複雑な三次元構造に対して適応させたデータ構造である．

定を用いた枝刈りにより，高速な照合を実現する．

このデータ構造は，RMSD 指標による効率よい近似部分構造

1. 2 本研究の目的.

マッチングを実現し，データベース中に存在するタンパク質構

本稿では，点の座標以外の情報を利用して，RMSD の三次元造同士の頻出する類似部分構造の発見にも用いることができる．

点集合マッチングを高速化することを考える．近年，分子生物

また，三次元点集合マッチング問題に対して，分枝限定法を学分野では，二つのタンパク質の間で，それらの RMSD 値と用いた実際的に高速なアルゴリズムが提案されている．[9] [10]DNA 配列の文字列距離に密接な関係があることが指摘されている [11]．そこで，我々は，この RMSD と文字列距離の関係を

2. 準備用いて，三次元点集合マッチングの高速化を考える．初めに，

2. 1 基本的定義

実際のインフルエンザウイルスのタンパク質データベースを用

本稿では，三次元空間 R3 を考える．まずはじめに，長さ n の点いて，上記の RMSD と文字列距離の相関関係を実験的に調べ列（point sequence）S は，S = (s1 , . . . , sn ) ∈ (R3 )n である．ここる．次に，観察した相関関係に基づいて経験的枝刈り関数 f をに，各 i = 1, . . . , n に対して，si = (xi , yi , zi ) ∈ R3 は i 番目の点の定める．最後に，我々の照合アルゴリズムに枝刈り関数を組み三次元座標を表すベクトルである．ここに，|S | = n で S の長さを込み，提案手法による高速化の有用性を調べる．

表す．任意の 1 <=i<= j<= n に対して，P[i . . . j] = (si , si+1 , . . . , s j )で S の添え字 i から j までの部分点列を表す．点列 S の長さ

1<=i<= n の前綴り（prefix）とは，最初の i 個からなる列 S [1..i]が成立することである．このとき，T の部分点集合 Q を，T における P の出現位置という．

である．
三 次 元 の 回 転 行 列 R に よって 点 列 S を 回 転 し た 構 造 は［定義 2.1］ 最小 RMSD スコアに関する点集合マッチング探索

R · S = (Rs1 , . . . , Rsn ) で与えられる．回転行列 R と移動ベク問題は，データ点集合 T と，パターン点集合 P，非負実数 r > 0

トル v は三次元空間の点に対する変換 f = fR,v (S ) = R · S + v をを受け取り，T 上の最小 RMSD スコア r でのパターン P の出与える．ベクトル v の転置ベクトルを vt で表し，行列 A の転置

現位置 Q⊂T を一つ見つける問題である．
=
上記の問題の変種として，P が T に最小 RMSD スコア r で行列を At で表す．trace(A) は行列 A のトレースを与え，|v| はベクトル v のノルムを与える．

マッチするかどうかを YES または NO で答えるものを点集合

次に，長さ n の点集合（point set）T とは，T = T [1, . . . , n] ={}T [1] · · · T [n] = t1 , . . . , tn ∈ (R3 )n である．ここに，各 P[k] =マッチングの決定問題と呼ぶ．また，全ての出現位置 Q⊂T を=もれなく，かつ重複なしに見つけるものを点集合マッチングの(xk , yk , zk ) ∈ R3 (k ∈ [1..k]) は R3 の点であり，点の順序は任意に列挙問題と呼ぶ．ただし，点列として異なる出現位置 Q は互い決めておく．に異なるとみなす．

各点 ak = (xk , yk , zk , rk ) (k ∈ [1..k]) となり， xk , yk , zk ∈ (R) で,x 座問題を考察する．決定版と探索版の問題は，列挙版のアルゴリ

標，y 座標，z 座標を表し，rk ∈ Σ でラベル (文字) も保持してズムで解くことができる．

{}
また，長さ n のラベル付き点集合 A とは，A = a1 , . . . , an で，本稿では，とくに断らなければ，点集合マッチングの列挙版

2. 4 ラベル情報を用いない三次元点集合マッチング問題にいる．

対する基本アルゴリズム

2. 2 二つの点集合間の最小 RMSD
本小節では，本稿で問題としている，二つの点集合間の類

本小節では，我々が考案したラベル情報を用いない三次元点似度として用いられる最小平方平均二乗和距離（最小 RMSD，集合マッチングのアルゴリズム [9] [10] を紹介する．このアルMinRMSD）を定義する．P = P[1..n] と Q = Q[1..n] を，要素ゴリズムは，最小 RMSD スコアの下界関数を用いた探索の枝数 n の三次元空間の点集合とする．ただし，これらの点集合は，刈りによる効率化を行う．

点列として表されているものとし，要素である点の順番は任意

まず初めに，素朴なアルゴリズムとして，再帰的な計算により解となる候補集合を探索し，探索木の葉，すなわち，候補集に固定するとする．
順列 π : {1, . . . , n} → {1, . . . , n} に対して，π による長さ n の合のサイズがパターンサイズと同じ k に達したときに初めて，点列 P = P[1..n] の並べ替えを π(P) = (P[π(1)], . . . , P[π(n)]) と定

最小 RMSD スコアによる解の検査を行う手順が考えられる．しめる．

かし，探索のすべての枝を葉までたどるので効率が悪い．

点列として表されたサイズ n の集合 P と Q 間の最小平方平これを改良するために，前綴りに関する最小 RMSD スコアの均二乗和距離を，すべての順列 π と，回転行列 R，移動ベクト下界関数（lower-bound function of minimum RMSD for prefices）

ル v に関する最小の RMSD 値を導入し，これを用いた分枝限定法（branch-and-bound method）

MinRMS D(P, Q) = min min RMS DR,v (π(P), Q)
π

R,vを取り入れている．

(1)と定義する．すなわち，MinRMS D(P, Q) は，全ての並べ替えに関して点列 P と Q の最小 RMSD スコアをとった最小値である．

2. 3 最小 RMSD に関するラベル付き近似点集合マッチング問題［定義 2.2］（MinRMSD の下界関数） 任意の正整数 1 <= k= i <に対して，下界関数を次のように定める：

LB MinRMS Di,k (P[i], Q[i])( )1/2= ki
MinRMS D(P[i], Q[i]).

(2)

本論文で考察する最小 RMSD スコアに関するラベル付き近Algorithm 1 に，下界関数による分枝限定を用いた点集合マッ

似点集合マッチング問題を次のように定義する．三次元空間をチングアルゴリズムを示す．このアルゴリズムは，再帰に基づ考える．

いて，すべての候補集合を列挙し，最小 RMSD スコアが閾値 r

データ点集合とは，n 個の点からなる点集合 T = {t1 , . . . , tn }以下の解を正しく出力する．17 行目から 19 行目で，下界関数

で あ る ．パ タ ー ン 点 集 合と は ，k 個 の 点 か ら な る 点 集 合を用いた枝刈りを行う．この枝刈りは健全であり，いかなる正P = {p1 , . . . , pk } である．T と P の要素を，それぞれ，デー解を見落とすこともないことが言える．このアルゴリズムにつタ点およびパターン点と呼ぶ．また各点は，三次元の座標とラいて次が示されている．

ベルを保持している．ただし，以下では常に k <= n であり，デー［定理 2.1］ 点集合マッチングアルゴリズム Algorithm 1 は，与タ点集合とパターン点集合は，点列として表されるものと仮定えられたデータ点集合 T とパターン点集合 P に対して，最小する．

RMSD スコアが閾値 r 以下となる P のすべての出現位置を正非負実数 r > 0 に対して，パターン点集合 P がデータ点集合

T に最小 RMSD スコア r でマッチするとは，k 個のデータ点からなるある点集合 Q⊂T が存在して，=MinRMS D(P, Q) <=r

しく見つける．
アルゴリズムの使用領域は O(k) 領域である．計算時間に関しては，総計算時間が O(knk ) 時間であること以外はわからない．ただし，素朴なアルゴリズムが入力に無関係に常に Θ(knk )の時間を要するのに対して，枝刈りアルゴリズムは早期終了の

Algorithm 1 ラベル情報を用いない点集合マッチングの基本ア

Algorithm 2 NHD の枝刈りに基づくラベル付き点集合マッチン

ルゴリズム BasicMatch
1: procedure BasicMatch(P, T, r)

グ問題の提案アルゴリズム
1: procedure Main(P, T, r)2:

入力： パターン点集合 P[1..k]，データ点集合 T [1..k]，正実

入力： パターン点集合 P[1..k]，データ点集合 T [1..k]，正実数 r.

数 r.

出力： T 中の最小 RMSD スコア r に関する P の全ての異

出力： T 中の最小 RMSD スコア r に関する P の全ての異なる出現位置．

なる出現位置．

BasicFind(ε, 0, P, T, |Q|, |T |) を呼び出す;

2:

Find(ε, 0, P, T, |Q|, |T |) を呼び出す;

3: end procedure

3: end procedure

4:4:

5: procedure BasicFind(Q[1..i], i, P, T, k, n)

5: procedure Find(Q[1..i], i, P, T, k, n)

6:

if i = k then

▷ すべての点を選び終わった8:

if MinRMS D(P[1..k], Q[1..k]) <= r then
マッチング位置の集合 Q を出力する;

9:

end if

7:

10:

6:
7:

if i = k thenif MinRMS D(P[1..k], Q[1..k]) <= r then
マッチング位置の集合 Q を出力する;

8:
9:

else

10:

▷ すべての点を選び終わった

end ifelse

11:

for j = 1, . . . , n do

11:

for j = 1, . . . , n do

12:

x = T [ j];12:x = T [ j];13:

if x ∈ Q then13:

if x ∈ Q then14:

continue

14:

continue15:

end if15:

end if16:

R := Q の末尾に要素 x を加えて得られる点列;

16:

R := Q の末尾に要素 x を加えて得られる点列;

17:

if LB MinRMS Di+1,k (R, P[1..i + 1]) > r then17:

if NHD(R, P[1..]) <= d then
▷ NHD による新しい枝刈り

continue

18:

continue19:

end if18:

20:

BasicFind(R, i + 1, P, T, k, n) を再帰的に呼び出す;

19:

end if20:

if U B MinRMS Di+1,k (R, P[1..i + 1]) > r then21:

end forcontinueend if21:

23: end procedure22:

end if23:

Find(R, i + 1, P, T, k, n) を再帰的に呼び出す;

22:

24:

可能性をもっている点で実際には利点がある．

25:

3. 提 案 手 法

end forend if

26: end procedure

本節では，実データへの応用を考え，具体的にはインフルエ
ンザウイルスにおける類似構造を見つけるという問題に，ラベ意の実数関数 f : [0, ∞) → [0, 1] である．多くの点集合の対ル付き近似点集合マッチング問題を適応する．この問題においτ = (P, Q) に対して，関係て，各点の持つラベル情報はタンパク質におけるアミノ酸の種類に対応させる．生物学で一般的に知られている RMSD とDNA 配列の文字列距離の間の関係 [11] を利用した枝刈り手法を定式化し，これを用いて前節で説明した点集合マッチング問
題の高速化を考える．提案手法では，次の文字列距離を用いる．
［定義 3.1］ 点集合 P と Q の間の順列 π の下での正規化ハミン
グ距離（NHD）を，対応する点のラベルの不一致数を長さで正規化したもの

NHDπ (P, Q) = NHD(π(P), Q)n1∑=Ψ [ π(P)[i] , Q[i] ] ∈ [0, 1]
n i=1

RMS D(π(P), Q) <= r ⇒ NHD(π(P), Q) <= d = f (r)(5)が成立するならば，与えられた RMSD 値の上限 r に対して NHD
値の上限 d = f (r) を用いて，再帰的なマッチングアルゴリズ
ムの繰り返しにおいて，第 i 番目の点対に対して，制約違反NHD(P[π(1)] · · · P[π(i)]]), Q[1..i]) > d が成立したとき，これ以上の探索を行わないという枝刈りが行える．一般には，対上のある同時確率分布 D に従う点集合の対 (P, Q) ∼ D に対して高い(3)

確率で式 (5) が成立するならば，一定の照合ミスを許した上で，照合の高速化を期待できる．上記のアルゴリズムの擬似コード(4)と定める．ここに，Ψ[·] は特性関数である．

RMSD による NHD の上限関数（または上限関数）とは，任を 2 に示す．

0.80.6

手法

0.4

表20.1

0.15

0.20.25

照合 時間 照合 時間 照合 時間 照合 時間

提案手法

025

4 166

4 3684 1532

全解出力0674 301

4 14634 9341

実験 3．各 RMSD 値毎に，見つけた照合数（照合）と要した計算時間（時間，単位 sec) を示す．

0.20.0Normalized Humming Distance

RMSD r5. 結論

本稿では，３次元空間でのラベル付き点集合マッチングを考

0.0

1.0

2.0

3.0

察し，RMSD と文字列距離である NHD の関係から考えた関数

RMSD(A)を用いて枝刈りによる高速化を行うアルゴリズムについて議論

図 1 実験 1：RMSD と NHD の散布図 (RMS D <= 3.5(Å))

した．
実験では，RMSD 値が小さい時に RMSD と NHD に我々の係に基づいて経験的枝刈りを定めて，f による枝刈りが安全に0.8行われていることを確認した．最後に，実験より r が小さい時0.6(r <= 0.25) において，3 倍から 5 倍程度高速化していることが確認できた．

0.4

今後の課題として，実験 3 で与えた枝刈り関数の損失率を定0.2式化し，枝刈り関数のクラスを設計して，要求する損失率に対して，適切な枝刈り関数を与える．
文

0.0

sequence dissimilarity

1.0

指摘した関係があることを観察した．さらに，観察した相関関020406080100rmsd

図 2 実験 2：RMSD と NHD の散布図 (RMS D >= 3.5(Å))

r (A) 0.0∼0.1 0.1∼0.3 0.3∼0.5 0.5∼2.0 2.0∼3.0 3.0∼
d0.003

0.006

0.04

0.2

0.80.1

表 1 今回用いた経験的な上限関数 d = f (r)

4. 実

験

実験 1. 実験 1 では，PDB database 内にある 342 種類のイ
ンフルエンザウイルスのヘマグルチニンと呼ばれるタンパク質データに対して，それらの RMSD が 3.5（Å）以下となる組み合わせに対して，RMSD と HND の値を計測した．これより，rの上限と d の上限の間にわれわれが主張するような上記の関係があるかどうかを調べた．
実験 2. 実験 2 では，実験 1 と同様のデータに対して，RMSDが 3.5(Å) 以上では上記のような RMSD と NHD の関係は観察されないことを確認した．
実験 3. 実験 1 の結果のグラフから，経験的な枝刈り関数 f を求めた (表 1)．また，この関数 f を用いて，PDB database（注 ∗） の一組のインフルエンザウイルスのヘマグルチニン (4bgw.pdb(点の数=486) VS 4bgx.pdb(点の数=485)) に対して，f による枝刈りの正しさを確認した．

（注 ∗）http://www.rcsb.org/pdb/home/home.do

献[1] Tetsuo Shibuya, ”Geometric Suﬃx Tree : Indexing Protein 3-DStructures,” Jounal of the ACM, Vol.57, No.3, Article 15, 2010.
[2] Tetsuo Shibuya, ”Searching Protein 3-D Structures in Linear Time,”
RECOMB 2009, LNCS 5541, 115, 2009.
[3] Jacob T. Schwartz, Micha Sharir, ”Identification of partially obscured
objects in two and three dimensions by matching noisy characteristiccurves,” Intl. J. of Robotics Res. 6, 2944, 1987.
[4] Tatsuya Akutsu, Kentaro Onizuka, Masato Ishikawa, ”New Hashing Techniques and Their Application to a Protein Strucure Database
System,” Proc. Hawaii Int. Conf. System Sciences 5, 197-206, 1995.
[5] Gilbert Strang, ”Introduction to Linear Algebra, 3rd Edition,”
Wellesley-Cambridge Press, 2003.
[6] Dan Gusfield, ”Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology,” Cambridge UniversityPress, 1997.
[7] Esko Ukkonen, ”On-line construction of suﬃx-trees,” Algorithmica,Vol. 13, No. 3, 249-260, 1995.
[8] Mark Pinsky and Samuel Karlin, ”An introduction to stochastic modeling,” Academic press, 2010.
[9] 佐々木 耀一，渋谷 哲朗，伊藤 公人，有村 博紀，”三次元空間における効率良い近似点集合マッチングと分子パターン照合への応用,” 第 42 回バイオ情報学研究会, 2015.
[10] Yoichi Sasaki, Tetsuo Shibuya, Kimihito Ito, Hiroki Arimura, ”Eﬃcient Approximate 3-Dimensional Point Set Matching Using RootMean-Square Deviation Score,” SISAP 2015, 191-203, 2015.
[11] Aneerban Bhattacharya, et al. ”Assessing model accuracy using thehomology modeling automatically software”, Proteins: Structure,Function, and Bioinformatics, Volume 70, Issue 1, Pages 105118,
2008