組合せ剛性理論の最近の進展と応用

解説論文

組合せ剛性理論の最近の進展と応用

加藤 直樹

^†a)

Recent Advances and Applications in Theory of Combinatorial Rigidity Naoki KATOH

^†a)

あらまし 二次元平面または三次元空間内の伸び縮みのしない棒材と棒材をつなぐピンジョイント（つながっ ている棒材がジョイントの周りで自由に回転可能なジョイント）からなる二次元または三次元フレームワークが 剛堅であるかどうかを調べる（つまり剛性を調べる）ことは，機械工学，建築学の分野における基本的問題であ る．この問題を効率良く解くことは，大規模構造物の剛性を検査する場合，特に重要である．組合せ剛性理論は，

構造物の剛性とその構成要素の接続関係，つまり組合せ的性質との関係を純粋な数理モデルのもとで解明するこ とが主要な研究課題である．実際，ジョイント配置に特殊な幾何学的依存性がない場合，二次元フレームワーク の剛性はその接続関係によって決定されることが1970年にLamanによって証明されている．組合せ剛性理論 の成果は構造物の基礎的知見を与えるのに留まらず，機械設計やタンパク質の挙動解析・知的CADの開発・セ ンサネットワークのローカライゼイション等，様々な分野において応用されている．本論文では，組合せ剛性理 論の基礎理論について解説し，最後に，たんぱく質機能解析と建築デザインへの応用についても触れる．

キーワード 組合せ剛性理論，ピンジョイントフレームワーク，剛体棒フレームワーク，剛板ヒンジフレーム ワーク，タンパク質挙動解析

1.

ま え が き

伸び縮みのしない

m

本の棒部材が

n

個のピンジョイ ントで結合された二次元フレームワーク（いわゆる平 面トラス構造で

bar-jont

フレームワークという．図

1

参照）が剛堅であるためには

m ≥ 2 n − 3

が必要条件で ある．同様に三次元の場合は，

m ≥ 3 n − 6

が必要であ ることが知られている．これは，

1864

年

Maxwell [1]

によって発見された古典的事実であり，

Maxwell

の条 件として広く知られている．これは構造物の組合せ 的性質であり，この条件は構造物の剛性がそのトポロ ジー（棒とジョイントの接続関係）に大きく依存して いることを示唆している．実際，後に述べるように，

二次元フレームワークの剛性はその接続関係によって 決定されることが

Maxwell

の結果から約

100

年後の

1970

年に

Laman [2]

によって証明された．このよう に，ある構造モデルの剛性をその構成要素の接続関係，

†関西学院大学理工学部，三田市

Faculty of Science and Technology, Kwansei Gakuin Univer- sity, 2–1 Gakuen, Sanda-shi, 669–1337 Japan

a) E-mail: [email protected] DOI:10.14923/transinfj.2015JDS0002

つまり組合せ的性質との関係を純粋な数理モデルのも とで解明することが，組合せ剛性理論の主たる研究課 題である．組合せ剛性理論の成果は構造物の基礎的知 見を与えるに留まらず，機械設計やタンパク質の挙動 シミュレーション・知的

CAD

の開発・センサネット ワークのローカライゼイション等，

90

年代後半から 様々な分野において応用されている．本論文では，組 合せ剛性理論の基礎理論について解説し，最後にたん ぱく質機能解析と建築デザインへの応用についても触 れる

[3]

．

2.

組合せ剛性理論

組合せ剛性理論においては，グラフ

G = ( V, E )

と

d

^{次元空間への写像}

p : V → R

^dのペア

( G, p)

をフ レームワークと呼ぶ．

G

の各頂点はジョイントを，各 辺は棒材を表現し，写像

p

はジョイント配置を指定す る．つまり頂点

u, v

^{間を繋ぐ辺}

e = uv

^は，

p( u )

と

p( v )

間の距離

p( u ) − p( v )

を指定する．ここでは，

|V | ≥ d + 1

かつどの

d + 1

点もアフィン独立である ようなジョイント配置のみを考える．

フレームワーク

( G, p)

において，各辺長一定の制約 化でのジョイントの連続的移動をフレームワークの連

図1 平面上の(a)剛なフレームワークと(b)柔なフレー ムワーク

Fig. 1 (a) rigid framework and (b) flexible framework in the plane.

続的な動き

(motion)

と呼ぶ．特に，合同なフレーム ワークへの移動を自明な動きと呼び，自明な動きのみ が可能なフレームワークを剛

(rigid)

という．剛でな いフレームワークを柔

(flexible)

という（図

1

）．

フレームワークの剛性は以下のように定義される．

グラフ

G

^と

d

次元ユークリッド空間内のジョイント 配置

p , q ∈ R

^d|V|に対し，

p( u )−p( v )

²

= q( u ) −q( v )

²

, ∀uv ∈ E (1)

ならば，

( G, p)

と

( G, q)

は同値という．また，この制 約式が全ての頂点対に対して成り立つとき，

( G, p)

と

( G, q)

は合同という．

フレームワーク

( G, p)

が剛であるとは，

p−q <

を満たす任意の

q ∈ R

^{d|V|に対して}

( G, q)

が

( G, p)

に同値ならば，

( G, p)

と合同であるような

> 0

が存 在することである．

2. 1

無限小剛性

剛性を判定する問題は一般に

co-NP

困難であること が知られている．そのため，剛性を一次近似した無限 小剛性

(inifinitesimal rigidity)

の概念が有用である．

その目的のために，

p( v ) ( v ∈ V )

は時間

t

の微分可能 な連続関数とみなして，各式

(1)

を

t

^{について微分し} て，

p ˙ : V → R

^{dに対する線形方程式}

(p( u ) − p( v )) · ( ˙ p( u ) − p( ˙ v )) = 0 ∀uv ∈ E (2)

を得る．式

(2)

の解

p ˙

を

( G, p)

の無限小動き

(in- finitesimal motion)

と呼ぶ．可能な無限小動きが全 て自明なフレームワークを無限小剛

(infinitesimally rigid)

なフレームワークという．

線形方程式

(2)

を変数

p ˙

に対し行列表現して得られる 連立方程式の左辺の行列は剛性行列

(rigidity matrix)

と呼ばれ，

R ( G, p)

と記す．

例えば以下の図

2

のような二次元フレームワークの 剛性行列

R ( G, p )

は以下のようになる．各

p

iは二次 元ベクトルなので，この剛性行列は

5 × 8

行列である ことに注意されたい．

図2 二次元bar-jointフレームワーク Fig. 2 2-dimensional bar-joint framework.

⎛

⎜⎜

⎜⎜

⎜⎜

⎝

v₁ v₂ v₃ v₄

e₁ p₁−p₂ p₂−p₁ 0 0 e₂ 0 p₂−p₃ p₃−p₂ 0 e₃ 0 0 p₃−p₄ p₄−p₃ e₄ p₁−p₄ 0 0 p₄−p₁ e₅ p₁−p₃ 0 p₃−p₁ 0

⎞

⎟⎟

⎟⎟

⎟⎟

⎠

自明な無限小動きを表す線形空間の次元が

_d+1

2

で あ る の で（ 例 え ば ，

d = 2

の と き ，

x

^{軸 ，}

y

^軸 方 向 の 平 行 移 動 ，原 点 周 り の 回 転 の

3 =

₃

2 種

類の自明な動きがある），

dim ker R ( G, p) ≥

_d+1

2

で あ る ．上 記 の 例 で は ，三 つ の 独 立 な ベ ク ト ル

u

x

= [ 1 0 1 0 1 0 1 0 ] , u

y

= [ 0 1 0 1 0 1 0 1 ] , u

r

= [ −p

y,1

p

x,1

− p

y,2

p

x,2

− p

y,3

p

x,3

− p

y,4

p

x,4

]

は，それぞれ，

x

^{軸方向の平行移動，}

y

軸方向の平行移動，反時計ま わりの回転を表し，それぞれ先の等式

R ( G, p ) u = 0

を満たすことが確認される．ここで，

p

i の座標を

( p

x,i

, p

y,i

)

としている．したがって，

( G, p)

が無限小 剛であるための必要十分条件は次式で与えられる．

rank R ( G, p) = d|V | −

d + 1 2

(3)

2. 2

一 般 剛 性

無限小剛性と剛性は異なる概念であるが，

p

が一般

的

(generic)

である場合は二つの性質は一致する．こ

こで

p

が一般的とは，ジョイントの座標値の集合が有 理数体上で代数的に独立である場合を指す．この定義 より，ほとんど全てのジョイント配置は一般的である．

Asimov and Roth [4]

によって，次の事実が知られて いる．

定理

1 (Asimov and Roth [4])

一般的ジョイント配 置のフレームワーク

( G, p)

が剛であるための必要十 分条件は，

( G, p)

が無限小剛であることである．

一般的なジョイント配置におけるフレームワーク

( G, p)

の剛性は，一般剛性と呼ばれる．

p

が一般的なら，

rank R ( G, p) = max{rank R ( G, q) | q ∈ R

^d|V|

}

で ある．これより，フレームワークの一般剛性はグラフ

G

^{のみに依存している．}

3.

組合せ的特徴付け

式

(3)

より，フレームワーク

( G, p)

が無限小剛であ るためには

|E| ≥ d|V | −

_d+1

2 が必要である．フレー ムワーク

( G, p)

が極小剛とは，どの辺を削除しても剛 ではなくなるようなフレームワークのことである．無 限小剛かつ極小剛なフレームワークを無限小極小剛で あるという．以下の定理が知られている．

定理

2

（

Maxwell

の条件）．

d

^{次元ユークリッド空} 間におけるフレームワーク

( G, p)

が無限小極小剛 ならば，

G = ( V, E )

は以下の計数条件を満たす：

|E| = d|V | −

_d+1

2 かつ，

|V ( F ) | ≥ d

^{を満たす任意} の

F ⊆ E

に対して

|F | = d|V ( F ) | −

_d+1

2 ．ここで，

V ( F )

は辺集合

F

^{の端点集合を表す．}

一般的なジョイント配置に対して，

d = 2

の場合，定 理

2

の必要条件が十分となる．

定理

3

（

Laman

の定理

[2]

）．一般的なジョイント配 置に対して，二次元ユークリッド空間において，フ レームワーク

( G, p)

が無限小極小剛であるための必 要十分条件は，

G

が以下の計数条件を満たすことであ る：

|E| = 2|V | − 3

かつ空でない任意の

E

⊆ E

^に対 して

|E

| ≤ 2 |V ( E

) | − 3.

この定理によって，二次元フレームワークの一般剛 性がグラフの頂点数と辺数の関係で決定される．定理 の条件を満たすグラフは，以下の操作を繰り返し適用 することによって得られることが知られている

[5]

．

0-extension (Henneberg 1):

新たな頂点を追加し，そ れとそれ以外の

2

頂点を新たな辺で繋ぐ（図

3(a)

）．

1-extension (Henneberg 2):

辺を一つ取り除き，新た な頂点と取り除いた辺の両端点及びそれら以外の一頂 点を新たな辺で結ぶ（図

3(b)

）．

d ≥ 3

の場合，

d = 2

のような組合せ的特徴付けは 得られていない．有名なダブルバナナフレームワーク

（図

4

）が示すとおり，

Maxwell

の条件は十分でない．

以下，

Laman

の定理の証明の概略を記す．証明は

|V |

に関する帰納法である．フレームワークが

0-extension

で得られたのか，

1-extension

で得られたのかによっ

図 3 Henneberg 操 作 ．(a) 0-extension と (b) 1- extension

Fig. 3 Henneberg operations. (a) 0-extension, (b) 1- extension.

図4 ダブルバナナフレームワーク Fig. 4 Double banana framework.

図5 0-extensionによってGからGが得られるときの グラフの変化

Fig. 5 Change from a graphGtoGby 0-extension.

て，場合分けして証明する．

ケース

1

：

G

^が

G

^から

0-extension

によって，頂点

v

を追加し，頂点

a , b

と辺をつなぐことによって得られ たとする（図

5

参照）．頂点

v, a, b

^{の位置ベクトルを}

p

v

, p

a

, p

bとする．このとき，

p

vが直線

p

a

p

b上にない ので，

rank =

p

v

− p

a

p

v

− p

b

= 2 (4)

となる．よって，

rank R ( G, p ) ≥ rank

p

v

− p

a

p

v

− p

b

+ rank R ( G

, p

)

= 2 + 2|V | − 5 = 2|V | − 3

よって，得られたフレームワークが剛であることが示 された（図

6

参照）．

ケース

2

：

G

^が

G

^から

1-extension

によって得られる

（図

7

参照）．

G

に対応するフレームワークで，

p

v

p

b

p

c

図6 0-extensionによってGからGが得られるときの 剛性行列の変化

Fig. 6 Change of a rigidity matrix by 0-extension.

図7 1-extensionによってGからGが得られるときの グラフの変化

Fig. 7 Change from a graphGtoGby 1-extension.

が一直線上にあるものを考える．すると，その剛性行 列は，図

8

の一番上の行列となる．

p

v

p

b

p

cが一直線上 にあることを利用すると

p

v

− p

b及び

p

v

− p

cがそれ ぞれ

p

b

− p

cに比例するので，この行列に基本変換を 施すと図

8

の真ん中の行列になる．更に，この行列の 第

3

行から第

2

行を引くという基本変形を施すと図

8

の一番下の行列が得られる．基本変形によって行列の ランクは変化しないので，ケース

1

と同様に

rank R ( G, p ) ≥ rank

p

v

− p

a

p

b

− p

c

+ rank R ( G

, p

)

= 2 + 2|V | − 5 = 2|V | − 3

が成り立つ．したがって，図

7

のように

p

b

p

v

p

cが一 直線上に並んでいる場合でも，剛であることが分かる．

この特殊な場合に剛であることが示されると，

p

vが一 般の位置にある場合でも，剛となることが直ちに示さ れる．

3. 1 Body-bar

フレームワークと

Body-hinge

フレームワーク

bar-joint

フレームワークの頂点を

d

^{次元上に広が} りをもつ剛体に置き換えたフレームワークを

body- bar

フレームワークという．これらの剛体をグラフの 辺集合に対応する棒材で接続したものが

d

次元上の

図8 1-extensionによってGからGが得られるときの 剛性行列の変化

Fig. 8 Change of a rigidity matrix by 1-extension.

図9 (a) body-barフレームワーク，(b) body-hingeフ レームワーク，(c) panel-hingeフレームワーク Fig. 9 (a) body-bar framework, (b) body-hinge

framework, and (c) panel-hinge framework.

body-bar

フレームワークである（図

9(a)

参照）．一

般に

d

次元上の

body-bar

フレームワークは，グラフ

G = ( V, E )

及び，各棒材の

d

^{次元への埋め込み}

b

に よって表現される（ここで埋め込みとは，棒材の配置 位置を定めることを意味する）．

d

^次元上の

body-bar

フレームワーク

( G, b)

の無限 小動きを考えるために，各剛体

v ∈ V

に速度ベクトル

m

_v

∈ R

^{Dを与える．ここで，}

D = d + 1

2

^である．

各剛体はジョイントと異なり，

d

次元空間内に各軸方 向の

d

種類の平行移動と

d ( d − 1) / 2

種類の回転の動 きがあるので，速度ベクトルの次元が

D

^{であること} に注意する．

以下，三次元の

body-bar

フレームワークの剛性に ついて詳しく論じよう．剛体の動きは，回転と平行移 動の組合せによって表現できる．

3 × 3

の三次元回転 行列を

M

，平行移動を表す三次元ベクトルを

q

^とす ると，点

p

に回転を施したのちに，平行移動を行った 結果，

M q + p

^となる．

今二つの

body

（剛体）

B

と

B

が棒材

b

によって 接続されている構造を考える．

b

の両端点の座標を

p

¹

= ( p

1,x

, p

1,y

, p

1,z

)

と

p

²

= ( p

2,x

, p

2,y

, p

2,z

)

とす る．剛体

B

^{の回転を表す行列}

M , B

^{の平行移動を表す} ベクトル

q

^とし，

B

^{に対しても同様に}

M

, q

^を定義 する．このとき棒材の長さが変化しないという制約は

M

p

2

+ q

− M p

1

− q

²

= l

²

(5)

と表される．ここで

l

は棒材の長さを表す．この等式 を時間微分することで以下の式が得られる．

( M

p

2

+ q

− M p

1

− q ) · ( R

p

2

+ v

− Rp

1

− v ) = 0 (6)

ここで，

R

^と

R

^は

B, B

に割り当てられた回転速度 行列，

v

^と

v

^は

B, B

に割り当てられた平行移動の速 度ベクトルである．

R, R

^{は歪対称行列}

R=

⎛

⎝ 0 −ωz ωy

ωz 0 −ωx

−ωy ωx 0

⎞

⎠R=

⎛

⎜⎝

0 −ω_z ω_y ω_z 0 −ω_x

−ωy ωx 0

⎞

⎟⎠

(7)

と 表 す こ と が で き る

[6]

．

v = ( v

x

, v

y

, v

z

), v

= ( v

x

, v

y

, v

z

)

とし，更に，

p

i

= 0, M

i

= I

^（

I

^は単 位行列）と仮定して，

(6)

に代入して整理すると以下 の等式が得られる．

( p

2

− p

1

) · ( R

p

2

− Rp

1

+ v

− v ) = 0 (8)

更に，

ω = ( ω

x

, ω

y

, ω

z

)

，

ω

= ( ω

x

, ω

y

, ω

z

)

と定 義し，

B

1

, B

2の

6

次元速度ベクトルを

s = ( ω, v ), s

= ( ω

, v

)

とすると，詳細は省略するが，式

(8)

は，

T ( p

1

, p

2

) · ( s

− s ) = 0 (9)

と書き表すことができる（

[7]

及び

[8]

の

Appendix A

参照）．

T ( p

¹

, p

²

)

は，行列

A =

p

1,x

p

1,y

p

1,z

1 p

2,x

p

2,y

p

2,z

1

の

i, j

^{番目の列で構成される}

2 × 2

行列

A

i,jの行列式 の値を

i, j

の辞書式順序で並べた

6

次元ベクトルのこ とである．

ここで，この等式

(9)

を全ての辺（棒材）について まとめた行列が剛性行列

R

G

(b)

となることが知られ ている

[7].

( G, b)

が無限小剛であるための必要十分条件は，剛 性行列

R

G

(b)

のランクが

D |V |− D

^{となることとい} える

[7].

この剛性行列のランクを最大にするような各辺の埋 め込み

b

を一般的な辺配置と呼ぶことにする．このよ うに，各辺が一般的な配置に埋め込まれることを前提 とし，

( G, b)

が微小変形に対して剛である場合に，あ らためて

body-bar

フレームワーク

( G, b)

は剛である ということとする．

以降の議論では，

d = 3

（つまり

D = 6

）の場合の みを扱うが，一般

d

次元に対しても以降の議論は成 り立つことに注意しておく．

Tay

はこの

body-bar

フ レームワーク

( G, b)

に対して，以下の定理を示して いる

[9].

定理

4

一般的な辺配置（棒配置）

b

における三

-

次元

body-bar

フレームワーク

( G, b)

が極小剛であるため の必要十分条件は，

G = ( V, E )

が

6

個の辺素な全域 木を含むことである．この必要十分条件は，次の二つ の条件のいずれとも等価である．

1.

フレームワークの剛性行列

R ( G, b)

に対して，

rank R ( G, b) = 6 |V | − 6.

2.

次の

(i), (ii)

を満たす

G

の部分グラフ

G

= ( V, E

)

が存在する．

(i) |E

| = 6|V | − 6

かつ，

(ii) ∀F ⊆ E

( F = ∅ )

に対して

|F| ≤ 6 |V ( F ) | − 6.

三次元の

bar-joint

フレームワークには，このような美

しい組合せ的特徴付けが知られていないが，

body-bar

フレームワークは六つの辺素な全域木の和集合によっ てその剛性が特徴付けられるということである．

例えば，ある一般的な辺配置の

body-bar

フレーム ワーク

( G, b)

において，

G = ( V, E )

が図

10

のよう な接続関係にあるとする．

図10 6個の辺素な全域木への分解 Fig. 10 Partition into 6 edge-disjoint frameworks.

このグラフは各剛体間に

5

本ずつのバーが接続して いることを表している．ここで図

10

下のように，こ のグラフ

G

には

6

個の辺素な全域木を詰込むことが 可能である．よって定理

4

の性質より，このフレーム ワークは極小剛であることが分かる．

一般的な辺配置における

body-bar

フレームワーク

( G, b)

のグラフ

G

^は

body-bar

グラフという．そし て，

G

が定理

4

の

2

を満たすとき，

G

は剛であるとい うことにする．

本論文ではその詳細は紹介しないが，ぺブルゲーム アルゴリズムと呼ばれる

body-bar

フレームワークが 剛かどうかを判定する高速なアルゴリズムが知られて いる

[10]

．計算時間は

O ( |V ||E| )

であるが，たんぱく 質剛性判定の応用など多くの場合，

|E| = O (|V |)

で あるので，計算時間は

O (|V |

²

)

である．計算実験など を通して，ほとんどの場合，線形時間で動くと考えら れている．この問題は，グラフに

6

個の辺素な全域木 を詰め込めるかどうかを判定する問題であり，その判 定問題に対しては，ぺブルゲームアルゴリズムより理 論的に効率の良いアルゴリズムが知られている

[11].

しかしながら，ぺブルゲームアルゴリズムは，剛性 判定だけではなく，剛な部分グラフも出力として得ら れること，及び，実際の計算時間も速いことから，た んぱく質機能解析などの応用には，ぺブルゲームアル ゴリズムが用いられている．

三次元における

body-hinge

フレームワークは，各 剛体を頂点集合

V

^{，各ヒンジを辺集合}

E

^{とみなすこ} とで構成されるグラフ

G = ( V, E )

によって表現され る（図

11

）．ここで以下の定理が

Tay

及び

Whiteley

によって示されている

[12], [13].

定理

5

一般的なヒンジ配置

h

をとる三次元

body- hinge

フレームワーク

( G, h)

が剛であることの必要十

図11 body-hingeフレームワークのグラフ表現 Fig. 11 Graph representation of a body-hinge frame-

work.

分条件は，

G

^{における各辺}

E

^を

5

重化してできるグ ラフ

5 G

^に

6

個の辺素な全域木を詰込み可能なことで ある．

panel-hinge

フレームワークとは，

body-hinge

フレー ムワークの

body

（剛体）を

panel

（剛板，つまり二 次元平面に広がりをもつ剛体）に置き換えたフレー ムワークのことである（図

9

）．

panel-hinge

フレーム ワークもそのヒンジ配置

h

とすると，

( G, h)

によって 表現される．その対応するグラフ

G

^を，

panel-hinge

グラフと呼ぶ．

panel-hinge

フレームワークの場合，一つのパネル

（剛板）が表す平面上にそのパネルに接続する全ての ヒンジが存在するので，一般的なヒンジ配置とはいえ ない．しかし，次節で見るように，そのような場合で も定理

5

が拡張できる．

4.

たんぱく質剛性解明と

Panel-hinge

フ レームワーク

原子同士の共有結合は，原子同士の距離を規定し，

更に，ある原子から見て，その原子を中心として，共 有結合でつながっている二つの原子となす角度も定め る（図

12

参照）．図

12(a)

の辺は，両端の二つの原子 が共有結合で結ばれていることを表しており，それに よって原子間の距離が定まる．また，真ん中の原子（

A

または

B

）と共有結合でつながっている二つの原子と なす角度も定まることから，その角度制約によって真 ん中の原子とつながっている原子同士の距離も定まる

（図

12(b)

の灰色の辺）．共有結合を辺とするグラフ

G

（図

12(a))

から得られるグラフ（図

12(b)

）は

2

乗グ ラフ

G

^{2と呼ばれる．}

G = ( V, E )

に対して，

G

^2は

G

と同じ点集合上のグラフで，その辺集合は

E∪{ ( u, v ) | ( u, w ) , ( w, v ) ∈ E

^なる点

w ∈ V

^が存在

}

そうすると，

A

^{と隣接する}

3

点で構成される

4

面 体と，

B

^{と隣接する}

3

点で構成される

4

面体は剛体

(rigid body)

となる．この二つの

4

面体は，共通する

図12 (a)共有結合でつながっている原子．(b)角度制約 によって生じる距離制約が作る新たな辺 Fig. 12 (a) atoms connected by covalent-bond, (b)

an edge generated by angle constraint.

辺によってヒンジでつながっているとみなすことがで きる．この二つの

4

面体のうちの一つの他の

4

面体 に関する相対的な動きはヒンジの周りの回転のみであ る．したがって，共有結合でつながっている原子たち は，三次元の

body-hinge

フレームワークと考えてよ

い．この

body-hinge

フレームワークを表現するグラ

フモデルが

body-hinge

グラフである．剛体（

4

面体）

が点に対応し，二つの剛体がヒンジでつながれている 場合は，剛体を辺で結ぶことによって得られるグラフ である．このフレームワークは，後に述べるように建 築デザインへの応用がある．

分子構造における原子間の力は，共有結合だけでな く，ペプチド結合，水素結合，疎水効果，ファンデル ワールス力などがある．これらの力も剛体間の距離の 制約を与えている．ペプチド結合で結ばれている二つ の原子は共有結合より強力で，一つの剛体と考える．

これを

body-bar

フレームワークで表現すると，原子

を表す

2

点間に

6

本の辺を設けて表現する．剛体は

6

個の自由度があるので，二つの剛体を

6

本の独立な棒 材でつなぐと一つの剛体となるからである．共有結合 でつながっている原子については，原子を表す

2

点間 に

5

本の辺を設けて表現する．二つの剛体間には，ヒ ンジ周りの回転のみの自由度が残るからである．水素 結合の場合，剛体間の制約は，対応する原子間の結合 の力の強さによって，

1

から

5

本の辺を設けて表現す る

[14]

．このように分子を構成する原子を剛体とみて，

原子間の結合や原子間に働く力を棒材を用いて表現す るモデルは，分子フレームワークモデルと呼ばれる．

このように分子構造をフレームワークで表現し，そ の剛性を調べる研究は，

21

世紀に入って盛んに行われ るようになっている．この分子フレームワークのベー スになっているグラフを分子グラフという．共有結合 だけでつながっているグラフモデルも分子グラフと呼 ばれる．このフレームワークは，分子ヒンジフレー ムワーク

(molecular hinge framework)

とも呼ばれる が，一般の位置にある

body-hinge

フレームワークと

異なり，一般の位置にあるフレームワークとはいえな い．というには，図

12(b)

にあるように，各辺はヒン ジに対応するが，原子に対応する点とつながっている 全てのヒンジはその原子と交わりをもっているからで ある．

Tay and Whiteley [15]

によって，次の予想が 立てられていた．

予想

1 [15]

分子構造における原子間の共有結合を 表すグラフ

G

と

G

に対応する一般の位置にある分子 ヒンジフレームワークが与えられているとする．その フレームワークが剛であるのは，

G

^{2の各辺を}

5

重化 したグラフに六つの全域木が存在することである．

この予想はその後

Molecular

予想と呼ばれ，様々な 文献で取り上げられてきた

[16].

この予想が真である ことを前提に剛性判定アルゴリズムが設計され，タ ンパク質の挙動解析ソフトウェアに組み込まれる等，

理論・応用両面から重要な問題であったが（詳しく は

[16]

等を参照），最近，筆者らによって，この予想 が肯定的に解決された

[17]

．そこでは，一般の位置に

ある

panel-hinge

フレームワークの剛性が，一般の位

置にある

body-hinge

フレームワークと等しいことを

証明している．現在では，この予想は分子構造定理 と呼ばれている．分子フレームワークが，どのよう

に

panel-hinge

フレームワークと関係しているかにつ

いて述べよう．共有結合のみで原子間が結合された分 子構造は

G

^の

2

乗グラフ

G

^{2 の三次元フレームワー} ク（分子フレームワーク）としてモデル化することが できることを示したが．分子フレームワークは，射 影双対変換を施すことにより，剛性を保持したまま

panel-hinge

フレームワークとして表現できることが

知られている．

panel-hinge

フレームワークのヒンジ 配置は一般的とはいえないので，定理

5

が適用できな い．しかし，

panel-hinge

フレームワークに対しても，

定理

5

が成立するのではないかという予想は，予想

1

を言い換えたものである．

5.

応 用

以下，たんぱく質の挙動解析と建築デザインへの応 用について，概要を解説する．

5. 1

たんぱく質挙動解析への応用

タンパク質は剛性や立体構造によってその機能が決 まるため，可能な形状変化を予想することは今日の分 子生物学における一大テーマである．タンパク質の原

子数は数千・数万のものもあり，ロボティクスや計算 幾何学で提案されている厳密解法でなく，高速で精度 の良いシミュレーション手法が求められている．たん ぱく質の機能を深く理解するには，その動きを知る 必要があり，医学，創薬，ナノ工学等の分野で極めて 重要である．しかし，たんぱく質の形態変化の速度は 極めて速く，動きを捉えることは困難である．核磁気

共鳴

(NMR)

分光法などのさまざまな生化学分野にお

ける測定法は，いずれも限界があり，極めて多くの時 間を要する．たんぱく質の動きは，分子動力学シミュ レーション（

MD

シミュレーション）によってもモデ ル化される．生物学的に意味のあるたんぱく質の動き は，

0.1

秒から数秒という時間を要するが，

MD

シミュ レーションは，最高速のコンピュータでさえ，

1

ミリ 秒間が限界である

[18], [19]

．近年，たんぱく質データ ベースへの登録数も増加し，そのサイズも増大してい るため，たんぱく質の挙動解析を高速かつ正確に行う 方法の開発は急務である．

組合せ剛性理論の進展と最近の分子構造予想の解決 により，計算機上でたんぱく質の挙動解析を実用時間 で行うことが可能になりつつある．

既に述べたように，分子構造定理は，分子構造の剛 性を決定するためのグラフの頂点と辺の計数条件を与 えている．この結果は高速なぺブルゲームアルゴリズ ムの実装に至り，

FIRST

などのプログラムが開発さ れている（

[16]

）．

MD

シミュレーションが多大な計 算時間を要するのとは対照的に，

FIRST

をサブルー チンとして用いているプログラム

FRODA

は，たん ぱく質の剛部分を剛体とみなして，モンテカルロシ ミュレーションによりたんぱく質動的解析を行ってい るため，極めて高速に動作する

[20]

．組合せ剛性理論 のアルゴリズムの側面からの進展により，関連領域検 出などのぺブルゲームアルゴリズムの拡張版が開発 され，大規模な時間スケールでのたんぱく質の挙動解 析を行う新たな有望な道具が産み出されている．これ らの方法の正当性は，生化学的実験により確認されて いる．同じ方法は，アルツハイマー病の発症に深く関 係しているといわれているタウたんぱく質のメカニ ズムの重要な知見を得ることにも貢献している

[21]

． 他の応用としては，たんぱく質フォールディングと呼 ばれる折りたたみ現象が発生する場所の特定や

[22]

， 後述するアロステリーコミュニケーション

(allostery communication)

の構造的理解がある

[23]

．以下，こ れらの方法について述べる．

たんぱく質フォールディングは，その二つの剛な部 分がそれらをつなぐヒンジ部分で折りたたまれる現象 である（図

13

参照）．それは，触媒作用などの生物機 能を理解する上で極めて重要である．

たんぱく質フォールディングが起きる場所はヒンジ と呼ばれる．ヒンジ箇所は，後述のアロステリーコミュ ニケーションの発生個所を検出する問題と共通のアル ゴリズムである関連領域検出アルゴリズム

(relevant region detection algorithm)

によって求められる

[22]

． そのアルゴリズムは，分子グラフ

G

とその部分グラフ

G

^{を入力とし，}

G

が剛な部分グラフとなるように，

最小本数の辺を

G

^{内に加えて}

G

^とし，

G

^を含む極 大剛成分

C

^を求め，

C − G

を関連領域として出力す るものである．

ヒンジ箇所検出問題では，たんぱく質の分子グラ

G

において，二つの大きな剛成分（剛な部分グラフ）

R

¹

, R

^{2を求める．}

R

^1と

R

²は点素と仮定する．そし て，

R

1

∪ R

2を部分グラフ

G

^{として関連領域検出ア} ルゴリズムを適用する．

G

^は

G

^{が剛となるまで，}

R

1と

R

2の間に辺を加えていくことにより得られる．

そのときに，

R

¹

∪ R

^{2を含む極大な剛成分}

C

^を求め，

C − ( R

¹

∪ R

²

)

をヒンジ箇所として出力する．

たんぱく質において，アロステリック調節

(allosteric

regulation)

とは，たんぱく質の一部（結合部位）に

リガンドと呼ばれる物質（小さな分子）が結合するこ とによって，そのたんぱく質の他の部位に影響を与え る機能を意味する．アロステリー

(allostery)

とは，ギ リシア語で「別の」を意味する

allos

と「形」を意味

する

stereos

から来ている．アロステリック調節は生

図13 折りたたみ現象．(a)の状態から真ん中のヒンジ部 分で折りたたまれ，(b)の状態に変化．[22]

Fig. 13 Folding phenomenon: conformation change from (a) to (b) around the mid part by fold- ing.

物学的に極めて重要な機能で，全ての器官を制御する ための基本的なメカニズムである．たんぱく質のある 特定の部位（アロステリック部位）にリガンドが結合 することにより，たんぱく質の構造変化を引き起こし，

その結果，活性部位と呼ばれる部分の形状に変化を起 こす．活性部位はしばしば，アロステリー部位とは遠 く離れたところに位置している

[24], [25]

．

このように，アロステリーはたんぱく質の活性化を 調節する一つの重要な機構といえる．それは，たんぱ く質を活性状態から不活性状態へ，または不活性状態 から活性状態へと高速に変化させるスイッチの役割を 果たしている．アロステリー調節はたんぱく質の異な る結合部位の間のコミュニケーションを実現している ともいえる（これをアロステリックコミュニケーショ ンと呼ぶ）．アロステリックコミュニケーションは薬 学や分子生物学の分野では重要な研究対象になってい る

[26], [27]

が，離れた位置にある部位どうしの同時的 な構造変化が起きる理由についてはよく理解されてい なかった．

最近

Sljoka

は，このようなアロステリックコミュニ

ケーションが生じる理由を組合せ剛性理論によって説 明することができることを示した

[23]

．以下，その理 由を簡単に説明する．図

14

は，アロステリックコミュ ニケーションの起こる様子を模式的に表している（こ の図は

[23]

によるものである）．図

14(i)

はリガンド が結合していない状態を示している．リガンドがアロ ステリック部位に結合されるとその部分の剛性が変化

し（図

14(ii)

），それがシグナルとなって剛性変化が活

性部位まで伝播する（図

14(iii)

）．それが，結合部位 の剛性の変化（増加）を生じさせ，そこで，リガンド がより結合しやすくなる（図

14(iv)

）．

ア ロ ス テ リ ー 現 象 は ，

G-

た ん ぱ く 質 共 役 受 容 体

(GPCR)

と呼ばれるたんぱく質においてよく見られ

る．

GPCR

は多くの疾患に関与していること，及び 市販薬の数割が

GPCR

を標的としていることから，

注目を集めている．従来の薬の開発は，活性部位を直 接に標的としていたが，最近の新薬開発は，アロステ リック部位を標的にしている．アロステリックコミュ ニケーションによって活性部位の活性状態を変化させ ようとするものである．したがって，アロステリック 部位を見つけることが新しい薬の開発の鍵となる

[28]

．

アロステリーコミュニケーションが実際に起きてい るかどうかは，既に述べた関連領域検出アルゴリズム を少し修正して適用することによって求められる．分

図14 アロステリー現象の説明図 Fig. 14 Illustration of allostery phenomenon.

子フレームワークにおいて，タンパク質の二つのサイ ト

A, B

を考える．ここで，サイトとは分子フレーム ワークに対応する分子グラフを

G = ( V, E )

としたと きの，ある部分点集合

U ⊂ V

^{から誘導される部分グ} ラフ

G ( U ) = ( U, E ( U ))

（

E ( U )

は両端点が

U

^に属す るような全ての辺

e ∈ E

を表す）を意味するものと する．

以下の議論では，分子フレームワークは一般の位置に あると仮定する．分子フレームワークを表現するグラフ

G

に対して，

body-bar

グラフを定義したのと同様に，

分子フレームワークが剛であるとき，グラフ

G

は剛で あるという．分子グラフ

G = ( V, E )

の点集合

V

^の部分 集合

U

から誘導される部分グラフ

G ( U ) = ( U, E ( U ))

（

E ( U )

は両端点が

U

に属するような全ての辺

e ∈ E

を表す）を考える．このとき，定理

4

より，

G ( U )

が剛 であるとは，次の

(i)

，

(ii)

を満たす

G ( U )

の部分グラフ

G

= ( U, E

)

（ただし，

E

⊂ E ( U )

）が存在することで ある．

(i) |E

| = 6 |U | − 6

かつ，

(ii) ∀F ⊆ E

( F = ∅ )

に対して

|F| ≤ 6 |V ( F ) | − 6.

G ( U )

が剛であり，

G ( U )

を真に含む剛な誘導部分 グラフ

G ( U

) ( U

⊃ U )

が存在しないとき，

G ( U )

を

G

^{の剛成分という．今，}

G ( U )

を含む剛成分

G ( U

)

が存在するとき，

G ( U )

の相対的自由度は

0

である と定義する．今，

G ( U )

が剛でなく，かつ

G ( U )

を真 に含む剛成分が存在しないと仮定しよう．このとき，

G ( U )

の相対的自由度（正の値）は次のように定める．

G ( U )

に適当に辺集合

E

を付加して得られるグラフ

G

= ( U, E ( U ) ∪ E

)

の相対的自由度が

0

となるよう な

E

のなかで，

|E

|

の最小値を

G ( U )

の相対的自由 度と定める．

A

^から

B

へのアロステリーコミュニケーションの有 無は，

A, B

^を各々

G

のある点集合から誘導される部 分グラフとして，関連領域検出アルゴリズムを適用す る．

A, B

は

G

の点素な部分グラフと考えてよい．そ して，

A

に辺を付加して剛にすることによって，

B

^の 相対的な自由度が減るかどうかを調べる．そのために，

dof

_AB

= Bmaxp − B

^A

maxp − 6

を計算する．ここで，

Bmaxp

^は

B

の相対的な自由度を表す．

B maxp

^{A は}

A

を剛にした後の

B

の相対的な自由度を表す．

− 6

とあ るのは，三次元のフレームワークは

6

個の自明な動き があるからである．

dof

AB

> 0

なら，

A

^と

B

^はアロ ステリーコミュニケーションがあるといい，

dof

_AB個 の自由度が

A

^から

B

に伝達されたということになる．

dof

_ABは，サイト

A

にリガンドが拘束されることに よって，サイト

B

の相対的自由度が減少するからで ある．

そのための説明図

15

について説明する．このグラフ は分子フレームワークを表しており，辺は剛体をつな ぐヒンジを表している．したがって各辺は

5

重辺であ るとみなす．

8

個の黒丸の点からなる部分グラフ（長さ

8

のサイクル）

A

の相対的自由度を考える．この部分グ ラフだけを見ると，

5 |E| = 40 , 6 |V | − 6 = 42

であり，

A

^{の自由度は}

42 − 40 = 2

となるが，白丸の点とそれ に接続する辺からなるチェイン

B

が

A

につながって おり，そのため，

A ∪ B

^は点数

12

，辺数

13 × 5 = 65

であるので，

A

^{の相対自由度は}

(6|V | − 6) − |E| = 1

である．そこで，

A

^に

1

本の辺を加えると，剛になる．

したがって，

A

^{の関連領域は}

B

^{となる．なお，灰色部} 分の点と接続している辺は，

A

の相対的自由度に影響 を及ぼさない．

図15 相対的自由度についての説明図 Fig. 15 Illustration that explains a relative degree of

freedom.

5. 2

建築デザインへの応用

建築分野においてアルゴリズミック・デザインと呼 ばれる設計手法により生成される形態には，大量の部 材によって構成されるものが多く，組合せ剛性理論の 応用が期待される．

panel-hinge

フレームワークは折 り紙を一般化したものと考えられ，建築デザインへ の応用が期待される．本節では，組合せ剛性理論に基 づいて

panel-hinge

グラフから三次元

panel-hinge

フ レームワークを生成する方法を解説し，形態デザイン への応用が可能であることを示す．グラフ

G

が与えら れたとき，

panel-hinge

フレームワークは，ヒンジ配 置

h

を定めると，

( G, h)

として表現されるが，ヒンジ 配置

h

の選び方に任意性があり，剛なフレームワーク を得るためには具体的なヒンジ配置を考慮する必要が ある．また，組合せ剛性理論は一般的な配置を前提と しているため，形態デザインへの応用を目指す上で，

一般的ではない配置を考慮する必要がある．

まず，用いるパネルは互いに直交する

3

種類のパ ネルに限定した場合について述べる．これは，筆者等

（

[29]

）が最近開発した剛な

panel-hinge

フレームワー クを演繹的に生成する手法に基づいているが，一般の 位置にあるフレームワークのみを対象としているので，

そのままでは剛性を保証していない．本節では，用い るパネルが長方形であり，かつ剛であることが保証さ

れた直交

panel-hinge

フレームワークを演繹的に生成

する手法を説明する．

図

16

の

chain addition

に対応して長方形直交パネ ルの追加をする．

chain addition

は，加える点の数が

図16 chain addition Fig. 16 chain addition.