Aritalab:Lecture/NetworkBiology/Network

Revision as of 06:40, 28 August 2015

学習事項

• グラフの定義
• 生物学と数学／情報科学ではネットワークの取り扱いが異なる

生物学では推移律が成立しない関係をネットワークで取り扱い（相同性など）、その結果を実体に敷衍して解釈する（例えば進化など）

数学／情報科学ではネットワークという構造そのものを研究対象とする

ネットワークとはなにか

グラフ理論では、ネットワークのことをグラフと呼びます。正確なグラフの定義は以下のようになります。

頂点の集合 V と辺の集合 E の間に f : E → V × V という関係を導入した構造 G := ( f , V, E)

辺は頂点を 1 対 1 で結ぶ関係であることに注意してください。多対多を結ぶ辺をもつグラフはハイパーグラフと呼ばれ、Berge などが研究対象にした時期もありましたが、理論的な解析は難しいようです。一般に、グラフ理論では辺や点に数値を割り振ることはおこないません。 頂点に接続する辺の数を次数 (degree) といいます。

K₅完全グラフ 

頂点数 5 で、各頂点が他の全頂点と結ばれたグラフです。いわゆる星形の周りを辺で囲んだ形になります。どの頂点も次数が 4 で、辺を交差させること無く平面に描けないという特徴を持ちます（非平面グラフ）。

K_3,3完全二部グラフ 

頂点数 3 のセット二組の間でのみ、全頂点間に辺があるグラフです。どの頂点も次数は 3 で、非平面グラフです。

• Petersen graph の彩色数が 3 であることを確認する
• 完全二部グラフ K_3,3 が平面に描けないことを確認する

計算機科学では、辺に流量などの重みをつけたとき、グラフではなくネットワークと呼ぶことが多くあります。これはオペレーションズリサーチにおいて流量計画問題などが盛んにおこなわれたことと関係するようです。一般には、流量やコストなど整数や実数を辺に割り振ります。

計算機科学の特徴

• アルゴリズムに重点を置く
• 浮動小数点を用いる実数値ではなく整数値の扱いが多い

生物学では、残念なことに正確な定義はありません。個々の研究者が自分の思い込むネットワークを勝手に提唱し、論文を書いている状態です。そのため、実際の物理化学現象とは全く関係のないネットワークまで研究されています。

生物学における、現実とは乖離したネットワークの例

• 遺伝子ネットワーク
• 相同性ネットワーク
• タンパク質内の近接原子ネットワーク