ネットワークモチーフ

Type of sub-graph

ネットワークモチーフとは、より大きなグラフにおける、統計的に有意な反復的な サブグラフまたはパターンです。生物学的ネットワーク、社会的ネットワーク、技術的ネットワーク（例：コンピュータネットワークや電気回路）など、あらゆるネットワークは、多様なサブグラフを含むグラフとして表現できます。^[要出典]

ネットワークモチーフとは、特定のネットワーク内、あるいは複数のネットワーク間で繰り返されるサブグラフです。頂点間の相互作用の特定のパターンによって定義されるこれらのサブグラフはそれぞれ、特定の機能が効率的に実現される枠組みを反映している可能性があります。実際、モチーフが特に重要なのは、主に機能特性を反映している可能性があるためです。近年、複雑なネットワークの構造設計原理を解明するための有用な概念として、モチーフは大きな注目を集めています。^{[ 1 ]ネットワーク}モチーフはネットワークの機能的能力に関する深い洞察を提供する可能性がありますが、その検出は計算的に困難です。^[要出典]

定義

G = (V, E)とG′ = (V′, E′)を2つのグラフとします。グラフG ′は、 V′ ⊆ VかつE′ ⊆ E ∩ (V′ × V′)である場合にグラフG′のサブグラフです ( G′ ⊆ Gと表記) 。G′ ⊆ GかつG′に、 u, v ∈ V′となる辺⟨u, v⟩ ∈ E がすべて含まれる 場合、G′はGの誘導サブグラフです。すべてのu , v ∈ V′に対して、 ⟨u, v⟩ ∈ E′ ⇔ ⟨f ( u), f(v)⟩ ∈ E となる一対一対応f :V′ → Vが存在する場合、 G′ と G は同型( G′ ↔ G と表記)であるという写像fはGとG′間の同型写像と呼ばれる。^[2]

G″ ⊂ Gであり、サブグラフG″とグラフG′の間に同型性がある場合、このマッピングはG′がGに出現することを表します。 GにおけるグラフG′の出現回数は、 G ′のGにおける 頻度F _Gと呼ばれます。グラフの頻度F _G (G′)が定義済みのしきい値またはカットオフ値を超える場合、そのグラフはGにおいて再帰的(または頻繁) であると呼ばれます。このレビューでは、パターンと頻繁サブグラフという用語を同じ意味で使用します。 Gに関連付けられたヌルモデルに対応するランダムグラフのアンサンブルΩ(G)が存在します。Ω (G)からN 個のランダムグラフを均一に選択し、 Gにおける 特定の頻繁サブグラフG′の頻度を計算する必要があります。 GにおけるG′の頻度がN 個のランダムグラフR _i ( 1 ≤ i ≤ N )におけるその算術平均頻度よりも高い場合、この再帰パターンは重要であると呼び、したがってG′ をGのネットワークモチーフとして扱います。小さなグラフG′、ネットワークG、およびランダムネットワークの集合R(G)⊆Ω(R)（ただしR(G) = N）の場合、G′の頻度のZスコアは次のように与えられる。

${\displaystyle Z(G^{\prime })={\frac {F_{G}(G^{\prime })-\mu _{R}(G^{\prime })}{\sigma _{R}(G^{\prime })}}}$

ここで、μ _R (G′)とσ _R (G′)はそれぞれ集合R(G)における頻度の平均値と標準偏差を表す。 ^{[3] [4] [5] [6] [7] [8]} Z(G′) が大きいほど、サブグラフG′がモチーフとして有意である。あるいは、モチーフ検出において考慮できる統計的仮説検定の別の指標としてp値がある。これはF _R (G′) ≥ F _G (G′)（その帰無仮説として） の確率として与えられ 、 F _R (G′)はランダム化ネットワークにおける G' の頻度を示す。^[6] p値が閾値（通常 0.01 または 0.05）未満のサブグラフは有意なパターンとして扱われる。G ′の頻度のp値は次のように定義される。

${\displaystyle P(G^{\prime })={\frac {1}{N}}\sum _{i=1}^{N}\delta (c(i))\quad c(i):F_{R}^{i}(G^{\prime })\geq F_{G}(G^{\prime })}$

グラフ内のサブグラフの異なる出現。(M1 – M4) は、グラフ (a) 内のサブグラフ (b) の異なる出現です。頻度概念F ₁の場合、集合 M1、M2、M3、M4 はすべての一致を表すため、F ₁ = 4です。F ₂の場合、2つの集合 M1、M4 または M2、M3 のいずれかが一致の可能性があり、F ₂ = 2です。最後に、頻度概念F ₃の場合、一致 (M1 ～ M4) の1つだけが許可されるため、F ₃ = 1 です。ネットワーク要素の使用が制限されるにつれて、これら3つの頻度概念の頻度は減少します。

ここで、Nはランダム化ネットワークの数、iはランダム化ネットワークの集合で定義され、クロネッカーのデルタ関数δ(c(i))は条件c(i)が成り立つ場合に1となる。ネットワークGにおける特定のnサイズ部分グラフG′の集中度^{[9] [10]}とは、ネットワークにおけるその部分グラフの出現頻度とnサイズ非同型部分グラフの出現頻度の比を指し、次のように定式化される。

${\displaystyle C_{G}(G^{\prime })={\frac {F_{G}(G^{\prime })}{\sum _{i}F_{G}(G_{i})}}}$

ここで、インデックスi は、すべての非同型nサイズグラフの集合上で定義されます。ネットワークモチーフを評価するための別の統計的測定法が定義されていますが、既知のアルゴリズムではほとんど使用されていません。この測定法は2008年にPicardらによって導入され、上記で暗黙的に使用されているガウス正規分布ではなく、ポアソン分布を使用しています。 ^[11]

さらに、サブグラフ頻度という3つの具体的な概念が提案されている。^[12]図に示すように、最初の頻度概念F _{1 は}、元のネットワーク内のグラフのすべての一致を考慮します。この定義は、上で紹介したものと同様です。2番目の概念F ₂は、元のネットワーク内の特定のグラフのエッジが互いに素なインスタンスの最大数として定義されます。そして最後に、頻度概念F ₃は、互いに素なエッジとノードとの一致を伴います。したがって、2つの概念F ₂とF _{3 は}グラフの要素の使用を制限し、推測できるように、ネットワーク要素の使用に制限を課すことでサブグラフの頻度は低下します。結果として、頻度概念F ₂とF ₃を重視すると、ネットワークモチーフ検出アルゴリズムはより多くの候補サブグラフを無視することになります。^[要出典]

歴史

ネットワークモチーフの研究は、ネットワークのトライアドセンサスの概念を提唱したホランドとラインハルト^{[13] [14] [15] [16]}によって開拓されました。彼らは、様々な種類のサブグラフ構成を列挙し、そのサブグラフ数がランダムネットワークで予想される数と統計的に異なるかどうかを検定する手法を導入しました。^[要出典]

この考え方は、2002年にUri Alonと彼のグループ^{[17]によって、大腸菌の遺伝子制御（}転写）ネットワーク、そしてその後、多くの自然ネットワークにおいてネットワークモチーフが発見されたことで、さらに一般化されました。それ以来、このテーマに関する多くの研究が行われてきました。これらの研究の中には、生物学的応用に焦点を当てたものもあれば、ネットワークモチーフの計算理論に焦点を当てたものもあります。^[要出典]

生物学研究では、生物学的ネットワークで検出されたモチーフの解釈が試みられています。例えば、その後の研究^{[17]では、}大腸菌で発見されたネットワークモチーフが、他の細菌^[18]や酵母^{[19] [20]}、さらに高等生物^{[21 ] [22]の転写ネットワークでも発見されました。[23]}神経細胞ネットワークやタンパク質相互作用ネットワークなど、他の種類の生物学的ネットワークにおいても、独自のネットワークモチーフ群が同定されました。^{[5] [24] [25]}

計算科学研究は、生物学的研究を支援し、より大規模なネットワークの解析を可能にするために、既存のモチーフ検出ツールの改良に重点を置いてきました。これまでにいくつかの異なるアルゴリズムが提供されており、次節では時系列順に詳しく説明します。^[要出典]

最近では、ネットワークモチーフを検出するための acc-MOTIF ツールがリリースされました。

モチーフ発見アルゴリズム

ネットワークモチーフ（NM）発見という難題に対して、様々な解決策が提案されてきました。これらのアルゴリズムは、厳密な計数法、サンプリング法、パターン成長法など、様々なパラダイムに分類できます。しかし、モチーフ発見問題は主に2つのステップで構成されます。まず、サブグラフの出現回数を計算し、次にサブグラフの有意性を評価します。出現回数が予想をはるかに上回っている場合、その出現は有意であると判断されます。大まかに言えば、サブグラフの出現回数の期待値は、ヌルモデルによって決定できます。ヌルモデルは、元のネットワークと同じ特性を持つランダムネットワークのアンサンブルによって定義されます。^[要出典]

2004年まで、NM検出のための唯一の正確な計数法は、Miloら^[3]によって提案された総当たり法でした。このアルゴリズムは小さなモチーフの発見には成功しましたが、サイズが5または6のモチーフの発見にこの方法を使用することは計算的に不可能でした。そのため、この問題に対する新たなアプローチが必要でした。^[要出典]

ここでは、主要なアルゴリズムの計算面についてレビューし、アルゴリズムの観点から見たそれらの関連する利点と欠点について説明します。^{[引用が必要]}

アルゴリズムの分類

以下の表は、このセクションで説明するモチーフ発見アルゴリズムの一覧です。これらは、正確なカウントに基づくものと、代わりに統計的サンプリングと推定値を用いるものの2つの一般的なカテゴリに分けられます。後者のグループは、メインネットワークにおけるサブグラフの出現をすべてカウントしないため、このグループに属するアルゴリズムは高速ですが、偏った非現実的な結果をもたらす可能性があります。^[要出典]

次のレベルでは、正確な計数アルゴリズムはネットワーク中心型とサブグラフ中心型の2つの方法に分類できます。前者のアルゴリズムは、与えられたネットワークから与えられたサイズのすべてのサブグラフを探索します。一方、後者のアルゴリズムは、まず与えられたサイズで異なる非同型グラフを生成し、生成されたサブグラフごとにネットワークを個別に探索します。それぞれのアプローチには長所と短所があり、以下で説明します。^[要出典]

この表は、アルゴリズムが有向ネットワークまたは無向ネットワーク、誘導サブグラフまたは非誘導サブグラフに使用できるかどうかも示しています。^{[引用が必要]}

モチーフ発見アルゴリズムの分類

カウント方法	基礎	名前	有向 / 無向	誘発性 / 非誘発性
ちょうど	ネットワーク中心	mfinder	両方	誘発された
		ESU (ファンモード)	両方	誘発された
		Kavosh（CytoKavoshで使用）	両方	誘発された
		Gトライ	両方	誘発された
		PGD	無指向性	誘発された
	サブグラフ中心	FPF（マビスト）	両方	誘発された
		ネモファインダー	無指向性	誘発された
		グロチョウ・ケリス	両方	両方
		モダ	両方	両方
推定/サンプリング	色分けアプローチ	N. Alonらによるアルゴリズム	無指向性	非誘発性
	その他のアプローチ	mfinder	両方	誘発された
		ESU (ファンモード)	両方	誘発された

mfinder

Kashtanらは2004年に最初のモチーフマイニングツールであるmfinderを発表しました。^[9]これは、完全列挙法と最初のサンプリング法という2種類のモチーフ検索アルゴリズムを実装しています。

彼らのサンプリング発見アルゴリズムは、ネットワーク全体のエッジサンプリングに基づいていました。このアルゴリズムは、誘導されたサブグラフの集中を推定し、有向または無向ネットワークでのモチーフ発見に利用できます。アルゴリズムのサンプリング手順は、サイズ 2 のサブグラフにつながるネットワークの任意のエッジから開始し、現在のサブグラフに接続するランダムなエッジを選択してサブグラフを拡張します。その後、サイズ n のサブグラフが得られるまで、ランダムに隣接エッジを選択し続けます。最後に、サンプリングされたサブグラフは、ネットワーク内のこれら n 個のノード間に存在するすべてのエッジを含むように拡張されます。アルゴリズムがサンプリング手法を使用する場合、偏りのないサンプルを取得することが、アルゴリズムが対処する最も重要な問題です。ただし、サンプリング手順では均一にサンプルが取得されないため、Kashtanらは、ネットワーク内の異なるサブグラフに異なる重みを割り当てる重み付けスキームを提案しました。^[9]重み付けの基本的な原理は、各サブグラフのサンプリング確率の情報を利用することです。つまり、確率の高いサブグラフは、確率の低いサブグラフと比較して、比較的低い重みを取得します。したがって、アルゴリズムは、サンプリングされた各サブグラフのサンプリング確率を計算する必要があります。この重み付け手法は、mfinderがサブグラフの集中度を公平に決定するのに役立ちます。

網羅的探索との際立った対照を含むように拡張されたこのアルゴリズムの計算時間は、驚くべきことに、ネットワークのサイズとは漸近的に独立している。アルゴリズムの計算時間の分析は、ネットワークからのサイズnのサブグラフの各サンプルに対してO(n ⁿ )かかることを示している。一方、^{[9]では、各サブグラフサンプルの}グラフ同型性を解くことを必要とする、サンプリングされたサブグラフの分類時間に関する分析はない。さらに、サブグラフの重み計算によって、アルゴリズムに追加の計算負荷がかかる。しかし、アルゴリズムが同じサブグラフを複数回サンプリングする可能性があり、情報を収集せずに時間を費やす可能性があると言うことは避けられない。^[10]結論として、サンプリングの利点を活用することで、このアルゴリズムは網羅的探索アルゴリズムよりも効率的に動作するが、サブグラフの集中を近似的にしか決定しない。このアルゴリズムは主な実装によりサイズ6までのモチーフを見つけることができ、その結果、他のすべてのモチーフではなく、最も重要なモチーフを与える。また、このツールには視覚的な表示オプションがないことにも留意する必要があります。サンプリングアルゴリズムは簡単に説明します。

mfinder
定義: E sは選択されたエッジの集合です。V sはE内のエッジが接するすべてのノードの集合です。
VとEを空集合として初期化します。 1. ランダムな辺e 1 = (v i , v j )を選択する。E s = {e 1 }、V s = {v i , v j } を更新する。 2. E sのすべての隣接辺のリストLを作成する。LからV sのメンバー間のすべての辺を除外する。 3. Lからランダムな辺e = {v k ,v l }を選択する。E s = E s ⋃ {e }、V s = V s ⋃ {v k , v l }を更新する。 4. nノードのサブグラフが完成するまで（|V s | = nまで）手順2～3を繰り返します。 5. 選択したnノードのサブグラフをサンプリングする確率を計算します。

FPF（マビスト）

SchreiberとSchwöbbermeyer ^[12]は、入力ネットワークの頻繁なサブグラフを抽出するためのフレキシブルパターンファインダー（FPF）というアルゴリズムを提案し、 Mavistoというシステムに実装しました。^[26]彼らのアルゴリズムは、頻度概念F ₂とF ₃に適用できる下向き閉包性を利用しています。下向き閉包性は、サブグラフのサイズが増加するとサブグラフの頻度が単調に減少することを主張していますが、この特性は頻度概念F ₁には必ずしも当てはまりません。FPFは、異なるグラフ（またはパターン）を表すノードで構成されるパターンツリー（図を参照）に基づいています。各ノードの親は、その子ノードのサブグラフです。言い換えると、各パターンツリーのノードに対応するグラフは、その親ノードのグラフに新しいエッジを追加することによって拡張されます。

FPFアルゴリズムにおけるパターンツリーの図。^[12]

まず、FPFアルゴリズムは、パターンツリーのルートにあるサブグラフのすべての一致情報を列挙し、保持します。次に、ターゲットグラフ内の一致するエッジによってサポートされている1つのエッジを追加することで、パターンツリー内の前のノードの子ノードを1つずつ構築し、一致に関する以前のすべての情報を新しいサブグラフ（子ノード）に拡張しようとします。次のステップでは、現在のパターンの頻度が事前定義されたしきい値よりも低いかどうかを判断します。頻度が低く、下方閉包が成立する場合、FPFはそのパスを放棄し、ツリーのこの部分をさらにトラバースしません。その結果、不要な計算が回避されます。この手順は、トラバースするパスがなくなるまで続けられます。

このアルゴリズムの利点は、頻度の低いサブグラフを考慮せず、列挙プロセスをできるだけ早く終了しようとすることです。そのため、パターンツリー内の有望なノードにのみ時間を費やし、他のすべてのノードを破棄します。 追加の利点として、パターンツリーの概念により、パターンツリーの各パスを個別にトラバースできるため、FPF を並列に実装して実行できます。 ただし、下方閉包はF ₁には適用できないため、 FPF は頻度概念F ₂およびF ₃に最も役立ちます。 ただし、アルゴリズムを並列に実行する場合、パターンツリーはF ₁に対して依然として実用的です。 このアルゴリズムのもう 1 つの利点は、このアルゴリズムの実装にモチーフ サイズ制限がないため、改善しやすいことです。FPF (Mavisto) の疑似コードを以下に示します。

マヴィスト
データ:グラフG、ターゲットパターンサイズt、頻度概念F 結果:最大頻度を持つ サイズtのパターンのRを設定します。
R ← φ、f max ← 0 P ←サイズ1の開始パターンp1 M p 1 ← Gにおけるp 1のすべての一致 P ≠ φ の場合、  P max ← Pから最大サイズのパターンをすべて選択します。  P ← P maxから最大頻度のパターンを選択  Ε =拡張ループ(G, p, M p )  各パターンp ∈ E   F = F 1 の場合、 f ←サイズ(M p )  それ以外の場合 f ← 最大独立集合(F, M p )  終わり   サイズ(p) = t の場合   f = f max の 場合 、R ← R ⋃ {p }  それ以外の場合、 f > f max であれば R ← {p }; f max ← f  終わり  それ以外   F = F 1 または f ≥ f max の場合、 P ← P ⋃ {p }  終わり  終わり  終わり 終わり

ESU (ファンモード)

Kashtanら ^[9]によるサンプリングバイアスは、NM発見問題に対するより優れたアルゴリズムの設計に大きな推進力を与えました。Kashtanらは重み付けスキームを用いてこの欠点を解決しようとしましたが、この方法は実行時間に望ましくないオーバーヘッドをもたらし、実装も複雑化しました。このツールは視覚的なオプションをサポートし、時間に関して効率的なアルゴリズムであるため、最も有用なツールの一つです。しかし、ツールの実装方法により、サイズが9以上のモチーフを検索できないため、モチーフサイズに制限があります。

Wernicke ^[10]は、 mfinder [9]を大幅に改善したRAND-ESUというアルゴリズムを紹介した。^{[9]このアルゴリズムは、正確な列挙アルゴリズム}ESUに基づいており、 FANMODというアプリケーションとして実装されている。^[10] RAND-ESUは、有向ネットワークと無向ネットワークの両方に適用できる NM 発見アルゴリズムで、ネットワーク全体で不偏ノード サンプリングを効果的に利用し、サブグラフを複数回過剰にカウントすることを防ぐ。さらに、RAND-ESU は、ランダム ネットワークのアンサンブルを Null モデルとして使用する代わりに、サブグラフの重要性を決定するためのDIRECTという新しい分析手法を使用する。 DIRECT法は、ランダム ネットワークを明示的に生成せずにサブグラフの集中度を推定する。^[10]経験的に、サブグラフの集中度が非常に低い場合は、ランダム ネットワーク アンサンブルに比べて DIRECT 法の方が効率的である。ただし、高度に集中したサブグラフの場合は、古典的な Null モデルの方がDIRECT法よりも高速である。 ^{[3] [10]}以下では、ESUアルゴリズムの詳細を説明し、このアルゴリズムをサブグラフの濃度を推定するRAND-ESUに効率的に変更する方法を示します。

アルゴリズムESUとRAND-ESUはかなり単純なので、実装も簡単です。ESU はまず、サイズkのすべての誘導サブグラフの集合を見つけ、この集合をS _kとします。ESUは再帰関数として実装できます。この関数の実行は、ESU ツリーと呼ばれる深さkのツリー構造として表示できます(図を参照)。各 ESU ツリー ノードは、連続する 2 つの集合 SUB および EXT を伴う再帰関数の状態を示します。 SUB は、ターゲット ネットワーク内で隣接し、サイズ|SUB| ≤ kの部分サブグラフを確立するノードを参照します。|SUB| = kの場合、アルゴリズムは誘導された完全なサブグラフを見つけたので、S _k = SUB ∪ S _kとなります。ただし、 |SUB| < kの場合、アルゴリズムは SUB を拡張してカーディナリティkを達成する必要があります。これは、次の 2 つの条件を満たすすべてのノードを含む EXT セットによって行われます。第 1 に、EXT 内の各ノードは SUB 内の少なくとも 1 つのノードに隣接している必要があります。第 2 に、それらの数値ラベルは SUB の最初の要素のラベルよりも大きくなければなりません。最初の条件は、SUB ノードの拡張によって接続されたグラフが生成されることを保証し、2 番目の条件は ESU-Tree のリーフ (図を参照) を区別できるようにします。その結果、過剰カウントが防止されます。EXT セットは静的セットではないため、各ステップで、2 つの条件に違反しない新しいノードがいくつか追加される可能性があることに注意してください。ESU の次のステップでは、ESU-Tree のリーフに配置されたサブグラフを非同型サイズkのグラフ クラスに分類します。その結果、ESU はサブグラフの頻度と集中を決定します。この段階は、グラフ同型性テストを実行して各サブグラフを分類するMcKay のnautyアルゴリズム^{[27] [28]を使用するだけで実装されています。したがって、ESU は、再帰アルゴリズムによってターゲット グラフ内のすべての誘導された}kサイズのサブグラフのセットを見つけ、効率的なツールを使用してそれらの頻度を決定します。

RAND-ESUを実装する手順は非常に簡単で、 FANMODの主な利点の 1 つです。 ESUアルゴリズムを変更して、ESU ツリーの各レベルに確率値0 ≤ p _d ≤ 1を適用し、レベルd-1にあるノードの各子ノードを確率p _dでトラバースするようにESUに義務付けることで、ESUツリーのリーフの一部のみを探索することができます。 この新しいアルゴリズムはRAND-ESUと呼ばれます。明らかに、すべてのレベルでp _d = 1の場合、 RAND-ESUはESUのように動作します。p _d = 0の場合、アルゴリズムは何も見つけません。 この手順により、ESU ツリーの各リーフを訪れる機会が同じになり、ネットワーク全体のサブグラフが偏りなくサンプリングされることに注意してください。各リーフを訪れる確率はΠ _d p _dであり、これはすべての ESU ツリーのリーフで同一です。したがって、この方法はネットワークからサブグラフが偏りなくサンプリングされることを保証します。それにもかかわらず、 1 ≤ d ≤ kの場合のp _dの値を決定することは、サブグラフ濃度の正確な結果を得るために専門家が手動で決定する必要がある別の問題です。^[8]この問題に対する明確な処方箋はありませんが、Wernicke は p_d 値の決定に役立つ可能性のある一般的な観察をいくつか提供しています。 要約すると、RAND-ESU は、不偏サンプリング法をサポートする誘導サブグラフの場合に NM を発見するための非常に高速なアルゴリズムです。 メインのESUアルゴリズムとFANMODツールは誘導サブグラフを発見するためのものとして知られていますが、 ESUに簡単な変更を加えることで、非誘導サブグラフも見つけることができるようになります。ESU (FANMOD)の疑似コードを以下に示します。

ESU (FANMOD) の列挙
サブグラフの列挙(G,k) 入力:グラフG = (V, E)と整数1 ≤ k ≤ |V|。 出力: G内のすべてのサイズk のサブグラフ。 各頂点v∈V に対して  VExtension ← {u ∈ N({v}) | u > v }   ExtendSubgraph ({v}, VExtension, v)を呼び出す エンドフォー
サブグラフを拡張します(Vサブグラフ、VExtension、v) |VSubgraph| = k の場合、G[VSubgraph]を出力し、 VExtension ≠ ∅ で あるが  VExtensionから任意に選択した頂点wを削除します。  VExtension′ ← VExtension ∪ {u ∈ N excl (w, VSubgraph) | u > v }   ExtendSubgraph (VSubgraph ∪ {w}, VExtension′, v)を呼び出す 戻る

ネモファインダー

Chenら ^[29]は、 SPIN ^[30]の考え方を応用したNeMoFinderと呼ばれる新しいNM発見アルゴリズムを紹介した。これは、頻出木を抽出し、それを非同型グラフ^{[8]に拡張するものである。NeMoFinder}は、頻出サイズnの木を利用して入力ネットワークをサイズnのグラフの集合に分割し、頻出木をエッジごとに拡張して頻出サイズnのサブグラフを見つけ、完全なサイズn_のグラフKnを得る。このアルゴリズムは無向ネットワークでNMを見つけ、誘導サブグラフの抽出だけに限定されない。さらに、NeMoFinderは正確な列挙アルゴリズムであり、サンプリング法に基づいていない。Chenらが主張するように、NeMoFinderは比較的大きなNMの検出に適用可能であり、例えば著者らが主張するように、 S. cerevisiae（酵母）PPIネットワーク全体からサイズ12までのNMを見つけることができる。 ^[31]

NeMoFinderは主に3つのステップから構成される。まず、頻出するサイズnのツリーを見つけ、次に繰り返されるサイズnのツリーを利用してネットワーク全体をサイズnのグラフのコレクションに分割し、最後にサブグラフの結合操作を実行して頻出するサイズnのサブグラフを見つける。^[29]最初のステップでは、アルゴリズムはすべての非同型サイズnのツリーと、ツリーからネットワークへのマッピングを検出する。 2番目のステップでは、これらのマッピングの範囲を使用して、ネットワークをサイズnのグラフに分割する。 このステップまで、NeMoFinderと正確な列挙方法の間に違いはない。 ただし、非同型サイズnのグラフの大部分がまだ残っている。NeMoFinderは、前のステップで取得した情報を使用して、非ツリーサイズnのグラフを列挙するためのヒューリスティックを活用する。 アルゴリズムの主な利点は、以前に列挙されたサブグラフから候補サブグラフを生成する3番目のステップにある。この新しいサイズn のサブグラフの生成は、それぞれの前のサブグラフを、いとこサブグラフと呼ばれるそのサブグラフ自体からの派生サブグラフと結合することによって行われます。これらの新しいサブグラフには、前のサブグラフと比較して 1 つの追加エッジが含まれます。ただし、新しいサブグラフの生成にはいくつかの問題があります。グラフからいとこを導出する明確な方法がなく、サブグラフをそのいとこ同士で結合すると、特定のサブグラフを複数回生成するという冗長性が生じ、いとこの決定は、結合操作で閉じられない隣接行列の標準表現によって行われます。NeMoFinderは、無向グラフとして表現されるタンパク質間相互作用ネットワークのみを対象に、サイズ 12 までのモチーフに対して効率的なネットワーク モチーフ検索アルゴリズムです。また、複雑ネットワークや生物学的ネットワークの分野で非常に重要な有向ネットワークでは機能しません。NeMoFinder の擬似コードを以下に示します。

ネモファインダー

入力： G - PPI ネットワーク; N - ランダム化されたネットワークの数。 K - 最大ネットワークモチーフサイズ; F - 周波数しきい値; S - 一意性のしきい値。 出力： U - 繰り返しとユニークなネットワーク モチーフ セット。 D ← ∅ ; モチーフサイズk が3からKの 場合、  T ← FindRepeatedTrees (k) ;  GD k ←グラフパーティション(G, T)  D ← D ∪ T ;  D′ ← T ;  i ← k ;   D′ ≠ ∅ かつ i ≤ k × (k - 1) / 2の ときは  D′ ← FindRepeatedGraphs (k, i, D′) ;  D ← D ∪ D′ ;  i ← i + 1 ;  終了しながら 終わりのために カウンタiを 1からNまで実行 する  G rand ← RandomizedNetworkGeneration () ;  各 g∈D に対して  GetRandFrequency (g, Grand ) ;  終わりのために 終わりのために U ← ∅ ; 各 g∈D に対して  s ← GetUniqunessValue (g) ;   s ≥ S ならば  U ← U ∪ {g };  終了の場合 終わりのために Uを返します。

グロチョウ・ケリス

Grochow と Kellis ^[32]は、サブグラフの出現を列挙する正確なアルゴリズムを提案した。このアルゴリズムはモチーフ中心のアプローチに基づいており、クエリ グラフと呼ばれる特定のサブグラフの頻度は、クエリ グラフからより大きなネットワークへのすべての可能なマッピングを検索することによって徹底的に決定される。モチーフ中心の方法は、ネットワーク中心の方法と比較して、いくつかの有益な機能があると主張されている^[32]。まず、サブグラフ列挙の複雑さが増すのを回避できる。また、列挙の代わりにマッピングを使用することで、同型性テストの改善が可能になる。このアルゴリズムは非効率的な正確な列挙アルゴリズムであるため、著者らは、対称性の破れ条件と呼ばれる高速な方法を導入して、アルゴリズムのパフォーマンスを向上させた。単純なサブグラフ同型性テスト中に、サブグラフがクエリ グラフの同じサブグラフに複数回マッピングされる可能性がある。Grochow–Kellis (GK) アルゴリズムでは、対称性の破れを使用してこのような複数のマッピングを回避している。ここでは、GK アルゴリズムと、冗長な同型性テストを排除する対称性の破れ条件を紹介します。

(a)グラフ G、(b) (a) に示されている G のすべての自己同型性の図解。集合 AutG から、(c) の SymG によって与えられた G の対称性破れ条件の集合を得ることができる。AutG の最初の写像のみが SynG 条件を満たす。結果として、同型性拡張モジュールで SymG を適用することで、アルゴリズムはネットワーク内のマッチング可能な各サブグラフを G に一度だけ列挙する。SynG は任意のグラフ G に対して必ずしも一意の集合ではないことに注意されたい。

GKアルゴリズムは、与えられたクエリグラフからネットワークへのマッピングの集合全体を、主に2つのステップで発見します。まず、クエリグラフの対称性破れ条件を計算します。次に、分枝限定法を用いて、クエリグラフからネットワークへのマッピングのうち、関連する対称性破れ条件を満たすすべての可能なマッピングを見つけようとします。GKアルゴリズムにおける対称性破れ条件の使用例を図に示します。

上で述べたように、対称性の破壊技法は、対称性のためにサブグラフを複数回検索する時間を費やすのを防ぐ単純なメカニズムです。^{[32] [33]}対称性の破壊条件を計算するには、特定のクエリグラフのすべての自己同型を見つける必要があることに注意してください。グラフの自己同型問題に対する効率的な（または多項式時間の）アルゴリズムはありませんが、この問題は実際には McKay のツールによって効率的に解決できます。^{[27] [28]}主張されているように、NM 検出で対称性の破壊条件を使用すると、実行時間を大幅に節約できます。さらに、^{[32] [33]の結果から、対称性の破壊条件を使用すると、無向ネットワークと比較して、特に有向ネットワークで高い効率が得られることがわかります。 GK アルゴリズムで使用される対称性の破壊条件は、} ESUアルゴリズムが EXT セットと SUB セットのラベルに適用する制限に似ています。結論として、GKアルゴリズムは、大規模で複雑なネットワークにおける与えられたクエリグラフの出現回数を正確に計算し、対称性の破れ条件を利用することでアルゴリズムの性能を向上させます。また、GKアルゴリズムは実装においてモチーフのサイズに制限がなく、潜在的にあらゆるサイズのモチーフを発見できる既知のアルゴリズムの一つです。

色分けアプローチ

NM発見の分野におけるほとんどのアルゴリズムは、ネットワークの誘導サブグラフを見つけるために使用されます。2008年、Noga Alonら ^[34] は、非誘導サブグラフを見つけるためのアプローチも導入しました。彼らの手法は、PPIネットワークなどの無向ネットワークにも適用できます。また、非誘導木と木幅が制限されたサブグラフもカウントします。この手法は、最大10のサイズのサブグラフに適用されます。

このアルゴリズムは、 n 個の頂点を持つネットワークG内のk = O(logn)個の頂点を持つツリーTの非誘導発生数を次のようにカウントします。

1. 色分け。入力ネットワークGの各頂点をk色のうちの1色で独立かつ均一にランダムに色付けします。
2. 計数。動的計画法を用いて、各頂点が一意の色を持つTの非誘導的出現回数を計数する。このステップの詳細については、^{[34]を参照のこと。}
3. 上記の2つのステップをO(e ^k )回繰り返し、 Tの出現回数を合計して、 GにおけるTの出現回数を推定します。

利用可能なPPIネットワークは完全かつエラーフリーとは程遠いため、このアプローチはそのようなネットワークにおけるNM発見に適しています。Grochow-Kellisアルゴリズムとこのアルゴリズムは非誘導サブグラフでよく使用されますが、Alonらによって導入されたアルゴリズムはGrochow-Kellisアルゴリズムよりも処理時間が短いことは特筆に値します。^[34]

モダ

Omidiら ^{[35]は、無向ネットワークにおける誘導および非誘導NM発見に適用可能な、} MODAという新しいモチーフ検出アルゴリズムを紹介した。これは、Grochow-Kellisアルゴリズムのセクションで説明したモチーフ中心のアプローチに基づいている。クエリ検索アルゴリズムとしても機能するため、MODAやGKアルゴリズムなどのモチーフ中心のアルゴリズムを区別することは非常に重要である。この機能により、このようなアルゴリズムは、単一のモチーフクエリ、またはより大きなサイズの少数のモチーフクエリ（特定のサイズのすべての可能なサブグラフではない）を見つけることができる。可能な非同型サブグラフの数はサブグラフのサイズとともに指数的に増加するため、大きなサイズのモチーフ（10よりも大きい場合も）の場合、すべての可能なサブグラフを探すネットワーク中心のアルゴリズムは問題に直面します。モチーフ中心のアルゴリズムも、すべての可能性のある大きなサイズのサブグラフを発見する際に問題を抱えているが、少数のサブグラフを見つけられることは重要な特性となることがある。

MODAアルゴリズムは、拡張ツリーと呼ばれる階層構造を用いて、与えられたサイズのNMを体系的に抽出することができます。これは、 FPFと同様に、見込みのないサブグラフの列挙を回避します。MODAは、頻繁にサブグラフにつながる可能性のある潜在的なクエリ（または候補サブグラフ）を考慮します。MODAはツリー構造を使用する点でFPFに似ていますが、拡張ツリーは頻度概念F _{1 の}計算にのみ適用できます。次に説明するように、このアルゴリズムの利点は、非ツリークエリグラフに対してサブグラフ同型性テストを実行しないことです。さらに、アルゴリズムの実行時間を短縮するためにサンプリング法を利用しています。

主要なアイデアは次のとおりです。簡単な基準により、サイズ k のグラフからネットワークへのマッピングを、その同じサイズのスーパーグラフに一般化できます。たとえば、k個のノードを持つグラフGのネットワークへのマッピングf(G)があり、もう 1 つのエッジ&langu, v⟩を持つ同じサイズのグラフG′があるとします。ネットワークにエッジ⟨f _G (u), f _G (v)⟩がある場合、f _GはG′ をネットワークにマッピングします。結果として、グラフのマッピング セットを利用して、サブグラフ同型性テストを実行せずに、O(1)時間で単純に同じ順序のスーパーグラフの頻度を決定できます。アルゴリズムは、サイズ k の最小接続クエリ グラフから巧妙に開始し、サブグラフ同型性を介してネットワークでのマッピングを見つけます。その後、グラフ サイズを保存しながら、以前に検討したクエリ グラフをエッジごとに拡張し、上記のようにこれらの拡張されたグラフの頻度を計算します。拡張プロセスは、完全なグラフK _{k (} k(k-1) ⁄ 2エッジで完全に接続) に到達するまで継続されます。

上で説明したように、このアルゴリズムはまずネットワーク内のサブツリーの頻度を計算し、次にサブツリーをエッジごとに拡張します。このアイデアを実装する 1 つの方法は、各kの拡張ツリーT _kと呼ばれます。図は、サイズ 4 のサブグラフの拡張ツリーを示しています。T _{k は}実行プロセスを整理し、階層的にクエリ グラフを提供します。厳密に言えば、拡張ツリーT _kは単なる有向非巡回グラフ(DAG) であり、そのルート番号kは拡張ツリー内に存在するグラフ サイズを示し、その他の各ノードには個別のkサイズのクエリ グラフの隣接行列が含まれます。T kの最初のレベルのノードはすべて個別のkサイズのツリーであり、 T _{k を深く}走査することで、各レベルで 1 つのエッジを持つクエリ グラフが拡張されます。ノード内のクエリ グラフは、ノードの子にあるクエリ グラフの、エッジが 1 つ異なるサブグラフ_{です。T k}内の最長パスは(k ² -3k+4)/2拡張木の生成は^、[35]で説明されている簡単なルーチンで行うことができます。

MODA はT _{k を}走査し、 T _kの最初のレベルからクエリ ツリーを抽出するときに、マッピング セットを計算し、次のステップのためにこれらのマッピングを保存します。T _kからの非ツリー クエリの場合、アルゴリズムはT _k内の親ノードに関連付けられたマッピングを抽出し、これらのマッピングのどれが現在のクエリ グラフをサポートできるかを決定します。このプロセスは、アルゴリズムが完全なクエリ グラフを取得するまで続行されます。クエリ ツリー マッピングは、Grochow–Kellis アルゴリズムを使用して抽出されます。非ツリー クエリ グラフの頻度を計算するために、アルゴリズムはO(1)ステップを実行する単純なルーチンを使用します。さらに、MODA は、ネットワーク内の各ノードのサンプリングがノード次数に線形比例するサンプリング方法を活用します。確率分布は、複雑ネットワークの分野でよく知られている Barabási-Albert 優先接続モデルとまったく同じです。^[36]このアプローチでは近似値が生成されますが、サブグラフは高度に接続されたノードの周りに集約されるため、結果は異なる実行でほぼ安定しています。^[37] MODAの擬似コードを以下に示します。

4ノードクエリグラフの展開木T4の図。第1レベルには非同型kサイズ木があり、各レベルで親グラフに辺が追加されて子グラフが形成される。第2レベルには、2つの代替辺を持つグラフがあり、赤い破線で示されている。実際、このノードは2つの同型な展開グラフを表している。^[35]

モダ
入力: G : 入力グラフ、k : サブグラフのサイズ、Δ : 閾値 出力:頻繁サブグラフリスト: すべての頻繁なkサイズサブグラフのリスト 注: F G :入力グラフGにおけるGからのマッピングの集合 T kを取得 する  G′ = Get-Next-BFS (T k ) // G′はクエリグラフである  |E(G′)| = (k – 1)の場合   マッピングモジュール(G′, G)を呼び出す  それ以外   列挙モジュール(G′, G, T k )を呼び出す  終了の場合   F 2を保存   |F G | > Δならば  G′を頻繁サブグラフリストに追加する  終了の場合 |E(G')| = (k – 1)/2になるまで 頻繁なサブグラフリストを返す

カヴォシュ

最近導入されたKavosh ^[38]と呼ばれるアルゴリズムは、メインメモリの使用効率の向上を目的としています。Kavoshは、有向ネットワークと無向ネットワークの両方においてNMの検出に使用できます。列挙の基本的な考え方は、GKアルゴリズムやMODAアルゴリズムに似ており、まず特定のノードが参加しているkサイズのサブグラフをすべて見つけ、次にそのノードを削除し、残りのノードに対してこのプロセスを繰り返すというものです。^[38]

特定のノードを含むサイズkのサブグラフをカウントするために、最大深度 k を持ち、このノードをルートとし、近隣関係に基づいたツリーが暗黙的に構築されます。各ノードの子には、入力隣接ノードと出力隣接ノードの両方が含まれます。ツリーを降りるために、特定の子は上位レベルに含まれていない場合にのみ含めることができるという制限付きで、各レベルで子が選択されます。可能な限り低いレベルまで降りた後、ツリーは再び上昇し、子孫の以前のパスで訪問されたノードは未訪問のノードとみなされるという条件で、このプロセスが繰り返されます。ツリーを構築する際の最後の制限は、特定のツリーのすべての子は、ツリーのルートのラベルよりも大きな数値ラベルを持つ必要があるということです。子のラベルに対する制限は、サブグラフの過剰カウントを回避するためにGKおよびESUアルゴリズムが使用する条件に似ています。

サブグラフを抽出するためのプロトコルは、整数の合成を利用します。サイズkのサブグラフを抽出するには、整数k-1のすべての可能な合成を考慮する必要があります。 k-1の合成は、k-1 を正の整数の和として表現するすべての可能な方法で構成されます。加数の順序が異なる和は、異なるとみなされます。合成はk ₂、k ₃、...、k _mと表現でき、ここでk ₂ + k ₃ + ... + k _m = k-1 です。合成に基づいてサブグラフを数えるために、ツリーのi番目のレベルからk _iノードが選択され、サブグラフのノードになります ( i = 2,3,...,m )。選択されたk-1 個のノードとルートのノードによって、ネットワーク内のサブグラフが定義されます。対象ネットワークにおいてマッチとして含まれるサブグラフを発見した後、対象ネットワークに応じて各クラスのサイズを評価できるようにするために、KavoshはFANMODと同様にnautyアルゴリズム^{[27] [28]}を用いる。Kavoshアルゴリズムの列挙部は以下の通りである。

カヴォシュの列挙
Enumerate_Vertex(G, u, S, 余り, i) 入力: G : 入力グラフu : ルート頂点S : 選択 ( S = { S 0 ,S 1 ,...,S k-1 } はすべてのS iの集合の配列)残り: 選択される残りの頂点の数i : ツリーの現在の深さ。出力: uをルートとするグラフGのすべてのkサイズの部分グラフ。         もし Remainder = 0 ならreturn else ValList ← Validate (G, S i-1 , u) n i ← Min (|ValList|, Remainder) for k i = 1 to n i do C ← Initial_Comb (ValList, k i ) (最初の頂点の組み合わせの選択をそれに従って行う) repeat S i ← C Enumerate_Vertex (G, u, S, Remainder-k i , i+1) Next_Comb (ValList, k i ) (次の頂点の組み合わせの選択をそれに従って行う) until C = NILL end for for each v ∈ ValList do Visited[v] ← false end for end if
検証(G, 親, u) 入力: G : 入力グラフ、親: 最終レイヤーの選択された頂点、u : ルート頂点。 出力:現在のレベルの有効な頂点。 ValList ← NILL for each v ∈ Parents do for each w ∈ Neighbor[u] do if label[u] < label[w] AND NOT Visited[w] then Visited[w] ← true ValList = ValList + w end if end for end for return ValList

最近、このソフトウェア用にCytoKavosh ^[39]と呼ばれるCytoscapeプラグインが開発されました。

Gトライ

2010年に、ペドロ・リベイロとフェルナンド・シルバは、 g-trieと呼ばれるサブグラフのコレクションを格納するための新しいデータ構造を提案した。^[40]このデータ構造は概念的にはプレフィックスツリーに似ており、サブグラフをその構造に従って格納し、これらのサブグラフのそれぞれがより大きなグラフ内で出現する場所を見つける。このデータ構造の注目すべき点の1つは、ネットワークモチーフの発見において、メインネットワーク内のサブグラフを評価する必要があることである。そのため、ランダムネットワーク内でメインネットワークにないサブグラフを見つける必要がない。これは、ランダムネットワーク内のすべてのサブグラフを導出するアルゴリズムの中で時間のかかる部分の一つになり得る。

g-トライは、グラフのコレクションを格納できる多方向ツリーです。各ツリー ノードには、単一のグラフ頂点と、それに対応する祖先ノードへのエッジに関する情報が格納されます。ルートからリーフへのパスは、1 つのグラフに対応します。g-トライ ノードの子孫は、共通のサブグラフを共有します。g-トライの構築については、 ^[40]で詳しく説明されています。g-トライの構築後、カウント部分が行われます。カウント プロセスの主な考え方は、すべての可能なサブグラフをバックトラックすることですが、同時に同型性テストを実行します。このバックトラッキング手法は、MODAアルゴリズムやGKアルゴリズムなどの他のモチーフ中心のアプローチで採用されている手法と基本的に同じです。共通のサブ構造を利用するということは、特定の時点で、いくつかの異なる候補サブグラフに部分的な同型一致があるという意味です。

上記のアルゴリズムの中で、G-Triesが最も高速です。しかし、メモリを過剰に使用するという欠点があり、平均的なメモリを搭載したパソコンでは、発見可能なモチーフのサイズが制限される可能性があります。

ParaMODAとNemoMap

ParaMODA ^[41]と NemoMap ^[42]は、それぞれ2017年と2018年に公開された高速アルゴリズムです。他の多くのアルゴリズムほどスケーラブルではありません。^[43]

比較

以下の表と図は、上記のアルゴリズムを異なる標準ネットワーク上で実行した結果を示しています。これらの結果は対応する情報源^{[35] [38] [40]}から引用されているため、個別に扱う必要があります。

3ノードから9ノードまでのサブグラフに対するGrochow–Kellis、mfinder、FANMOD、FPF、MODAの実行時間。^[35]

5つの異なるネットワーク上の3ノードから最大9ノードまでのサブグラフに対するGrochow–Kellis、FANMOD、G-Trieの実行時間。^[40]

ネットワーク	サイズ	国勢調査オリジナルネットワーク			ランダムネットワーク上の平均国勢調査
		ファンモッド	GK	Gトライ	ファンモッド	GK	Gトライ
イルカ	5	0.07	0.03	0.01	0.13	0.04	0.01
	6	0.48	0.28	0.04	1.14	0.35	0.07
	7	3.02	3.44	0.23	8.34	3.55	0.46
	8	19.44	73.16	1.69	67.94	37.31	4.03
	9	100.86	2984.22	6.98	493.98	366.79	24.84
回路	6	0.49	0.41	0.03	0.55	0.24	0.03
	7	3.28	3.73	0.22	3.53	1.34	0.17
	8	17.78	48.00	1.52	21.42	7.91	1.06
社交	3	0.31	0.11	0.02	0.35	0.11	0.02
	4	7.78	1.37	0.56	13.27	1.86	0.57
	5	208.30	31.85	14.88	531.65	62.66	22.11
酵母	3	0.47	0.33	0.02	0.57	0.35	0.02
	4	10.07	2.04	0.36	12.90	2.25	0.41
	5	268.51	34.10	12.73	400.13	47.16	14.98
力	3	0.51	1.46	0.00	0.91	1.37	0.01
	4	1.38	4.34	0.02	3.01	4.40	0.03
	5	4.68	16.95	0.10	12.38	17.54	0.14
	6	20.36	95.58	0.55	67.65	92.74	0.88
	7	101.04	765.91	3.36	408.15	630.65	5.17

3つの異なるネットワーク上の3ノードから最大10ノードまでのサブグラフに対するmfinder、FANMOD、Mavisto、Kavoshの実行時間。^[38]

	サイズ →	3	4	5	6	7	8	9	10
ネットワーク↓	アルゴリズム ↓
大腸菌	カヴォシュ	0.30	1.84	14.91	141.98	1374.0	13173.7	121110.3	1120560.1
	ファンモッド	0.81	2.53	15.71	132.24	1205.9	9256.6	-	-
	マヴィスト	13532	-	-	-	-	-	-	-
	Mファインダー	31.0	297	23671	-	-	-	-	-
電子	カヴォシュ	0.08	0.36	8.02	11.39	77.22	422.6	2823.7	18037.5
	ファンモッド	0.53	1.06	4.34	24.24	160	967.99	-	-
	マヴィスト	210.0	1727	-	-	-	-	-	-
	Mファインダー	7	14	109.8	2020.2	-	-	-	-
社交	カヴォシュ	0.04	0.23	1.63	10.48	69.43	415.66	2594.19	14611.23
	ファンモッド	0.46	0.84	3.07	17.63	117.43	845.93	-	-
	マヴィスト	393	1492	-	-	-	-	-	-
	Mファインダー	12	49	798	181077	-	-	-	-

確立されたモチーフとその機能

遺伝子制御ネットワークにおけるネットワークモチーフの解明に、多くの実験研究が費やされてきました。これらのネットワークは、生物学的シグナルに応答して細胞内でどの遺伝子が発現するかを制御します。ネットワークは、遺伝子がノード、有向エッジが、ある遺伝子がコードする転写因子（DNAに結合する調節タンパク質）による別の遺伝子の制御を表すように定義されます。つまり、ネットワークモチーフとは、互いの転写速度を制御する遺伝子のパターンです。転写ネットワークを解析すると、細菌からヒトまで、多様な生物で同じネットワークモチーフが繰り返し出現することがわかります。例えば、大腸菌と酵母の転写ネットワークは、ほぼネットワーク全体を構成する3つの主要なモチーフファミリーで構成されています。有力な仮説は、ネットワークモチーフが進化過程によって収束的に独立して選択されたというものである^{[44] [45]。}これは、遺伝子の変化速度に比べて、進化の時間スケールでは制御相互作用の生成または除去が速いためである^{[44] [45] [46]。}さらに、生細胞におけるネットワークモチーフによって生成されるダイナミクスに関する実験は、それらが特徴的な動的機能を有することを示している。これは、ネットワークモチーフが生物にとって有益な遺伝子制御ネットワークの構成要素として機能していることを示唆している。

転写ネットワークにおける共通ネットワークモチーフに関連する機能は、理論的にも実験的にも、いくつかの研究プロジェクトによって探求され、実証されてきました。以下は、最も一般的なネットワークモチーフとそれらに関連する機能の一部です。

負の自己調節（NAR）

自己調節モチーフの模式図

大腸菌において最も単純かつ豊富なネットワークモチーフの一つは、転写因子（TF）が自身の転写を抑制する負の自己制御である。このモチーフは2つの重要な機能を果たすことが示された。第一の機能は応答加速である。NARは理論的にも実験的にもシグナルへの応答を加速することが示された^{[47] 。これは最初に合成転写ネットワーク[48]}において示され、その後、大腸菌のSOS DNA修復システムにおいて自然界で実証された^[49] 。第二の機能は、自己制御遺伝子産物濃度の確率的ノイズに対する安定性を高め、異なる細胞間のタンパク質レベルのばらつきを低減することである^{[50] [51] [52] 。}

正の自己調節（PAR）

正の自己調節（PAR）は、転写因子が自身の産生速度を高めるときに起こります。NARモチーフとは逆に、このモチーフは単純な調節に比べて応答時間を遅くします。^[53]強いPARの場合、このモチーフは細胞集団におけるタンパク質レベルの二峰性分布につながる可能性があります。^[54]

フィードフォワードループ（FFL）

フィードフォワードモチーフの模式図

このモチーフは多くの遺伝子システムや生物でよく見られます。このモチーフは3つの遺伝子と3つの調節相互作用から構成されます。標的遺伝子 C は2つの TF A と B によって調節され、さらに TF B も TF A によって調節されます。各調節相互作用は正または負のいずれかであるため、FFL モチーフは8種類ある可能性があります。^[55]これら8種類のうち2種類、すなわちコヒーレントなタイプ 1 FFL (C1-FFL) (すべての相互作用が正) とインコヒーレントなタイプ 1 FFL (I1-FFL) (A は C を活性化し、さらに C を抑制する B も活性化) は、大腸菌と酵母の転写ネットワークにおいて他の6種類よりもはるかに多く見られます。^{[55] [56]}回路の構造に加えて、A と B からのシグナルがCプロモーターによって統合される方法も考慮する必要があります。ほとんどの場合、FFL はAND ゲート(C のアクティブ化には A と B が必要) またはOR ゲート(C のアクティブ化には A または B のいずれかで十分) のいずれかですが、他の入力機能も可能です。

コヒーレント型1FFL（C1-FFL）

^{ANDゲートを備えたC1-FFLは、理論的[55]}および大腸菌のアラビノース系を用いた実験的^[57]の両方において、「符号感受性遅延」要素と持続性検出器の機能を持つことが示された。これは、このモチーフが、短い信号パルスは応答を生成しないが、持続信号は短い遅延後に応答を生成するパルスフィルタリングを提供できることを意味する。持続パルスの終了時に出力が遮断されるのは高速である。大腸菌の鞭毛系で実証されたように、応答が高速で遮断が遅延する和ゲートの場合、逆の挙動が現れる。^[58]遺伝子制御ネットワークにおけるC1-FFLのde novo進化は、理想的な短い信号パルスをフィルタリングするための選択に応じて計算的に実証されているが、非理想的なノイズに対しては、異なるトポロジーを持つダイナミクスベースのフィードフォワード制御システムが代わりに採用された。^[59]

非一貫性型1FFL（I1-FFL）

I1-FFLはパルス発生器および応答加速器である。I1-FFLの2つのシグナル経路は反対方向に作用し、一方の経路はZを活性化し、もう一方はそれを抑制します。抑制が完了すると、パルス状のダイナミクスにつながります。また、I1-FFLがNARモチーフと同様に応答加速器として機能できることが実験的に実証されています。違いは、I1-FFLは転写因子遺伝子に限らず、任意の遺伝子の応答を高速化できることです。^[60] I1-FFLネットワークモチーフには追加の機能が割り当てられました。理論的にも実験的にも、I1-FFLは合成^[61]システムと天然システムの両方で非単調な入力関数を生成できることが示されました。^[62]最後に、遺伝子産物の非コヒーレントなフィードフォワード制御を組み込んだ発現ユニットは、DNAテンプレートの量への適応を提供し、構成的プロモーターの単純な組み合わせよりも優れている場合があります。^[63]フィードフォワード制御は負のフィードバックよりも優れた適応を示し、 RNA干渉に基づく回路はDNAテンプレート量の変動に対して最も堅牢であった。^[63]遺伝子制御ネットワークにおけるI1-FFLのde novo進化は、パルスを生成するための選択に応答して計算的に実証されており、I1-FFLは、リプレッサーを活性化するのが入力ではなく出力である代替モチーフと比較して、進化的にアクセスしやすいが、優れているわけではない。^[64]

マルチ出力FFL

場合によっては、同一の調節因子XとYが、同じシステム内の複数のZ遺伝子を制御する。相互作用の強度を調整することで、このモチーフは遺伝子活性化の時間的順序を決定することが示された。これは大腸菌の鞭毛系において実験的に実証された。^[65]

シングル入力モジュール（SIM）

このモチーフは、単一の調節因子が追加の調節なしに複数の遺伝子群を制御する場合に発生します。これは、遺伝子が協調的に特定の機能を果たしており、常に同期して活性化される必要がある場合に有用です。相互作用の強度を調整することで、制御対象遺伝子の時間的発現プログラムを作成できます。^[66]

文献では、SIMの一般化として多入力モジュール（MIM）が提案されている。しかし、SIMとMIMの正確な定義は矛盾の原因となっている。生物学的ネットワークにおける標準的なモチーフに直交的な定義を与え、それらを列挙するアルゴリズム、特にSIM、MIM、Bi-Fan（2x2 MIM）を提供する試みがある。^[67]

高密度重複レギュロン（DOR）

このモチーフは、複数の調節因子が、多様な調節組み合わせを持つ遺伝子群を複合的に制御する場合に出現する。このモチーフは、大腸菌において、炭素利用、嫌気性増殖、ストレス応答など、様々なシステムで発見されている。^{[17] [22]}このモチーフの機能をより深く理解するためには、複数の入力が遺伝子によってどのように統合されるかについて、より多くの情報を得る必要がある。Kaplanら^[68]は、大腸菌における糖利用遺伝子の入力機能をマッピングし、多様な形状を示している。

活動モチーフ

ネットワークモチーフの興味深い一般化として、活動モチーフとは、ネットワーク内のノードとエッジに定量的な特徴が付与された際に見られる過剰出現パターンである。例えば、代謝経路のエッジに、対応する遺伝子発現の強度やタイミングが付与されている場合、その基盤となるネットワーク構造を考慮すると、一部のパターンは過剰出現していることがわかる。^[69]

批判

位相的サブ構造の保存の背後にある仮定（時にはより暗黙的、時にはより暗黙的ではない）は、それが特定の機能的重要性を持つというものです。この仮定は最近疑問視されています。一部の研究者は、バイファンモチーフのようなモチーフはネットワークのコンテキストに応じて多様性を示す可能性があり、したがって^[70]モチーフの構造が必ずしも機能を決定するわけではないと主張しています。実際、C. elegans脳コネクトームにおけるモチーフを「無色ノード」（機能タグのないノード）として解析したところ、偶然と比較してモチーフの豊富さに有意な差は見られませんでした^[71] 。しかし、ノードにネットワークにおける機能的役割に応じて色を割り当てると（例えば、感覚ニューロン、運動ニューロン、または介在ニューロンに異なる色を割り当てる）、特定の色のモチーフは偶然に予想されるよりも有意に多く使用されることがわかり、モチーフの機能的役割を反映しています^[72] 。例えば、特定のバイファンモチーフは有意に高い頻度で出現しますが、他の色のバイファンモチーフはそうではありません。^[72] 有色モチーフの数は色の数に応じて指数関数的に増加するため、有意な偏りを持つ有色モチーフの探索は、少数の色（ノードタイプ）に対してのみ実行できます。ネットワーク構造が必ずしも機能を示すとは限りません。これは以前から存在する考え方であり、別の例としてSinオペロンが挙げられます。^[73]

モチーフ機能の解析は、ほとんどの場合、モチーフが単独で機能しているかどうかに注目して行われている。最近の研究^[74]は、ネットワークのコンテキスト、すなわちモチーフとネットワークの他の部分とのつながりが、局所的な構造のみから機能に関する推論を導き出すには重要すぎるという確かな証拠を提供している。引用された論文では、観測データに対する批判や代替的な説明も検討されている。単一のモチーフモジュールがネットワークの全体的ダイナミクスに与える影響の解析は^[75]で研究されている。さらに最近の別の研究では、生物学的ネットワークの特定の位相的特徴が、標準的なモチーフの共通の出現を自然に引き起こすことが示唆されており、モチーフの構造がネットワークの動作への機能的貢献のために選択されたことの合理的な証拠となるかどうかが疑問視されている。^{[76] [77]}

参照

• クリーク（グラフ理論）
• グラフィカルモデル

参考文献

1. Masoudi-Nejad A, Schreiber F, Razaghi MK Z (2012). 「生物学的ネットワークの構成要素：主要なネットワークモチーフ発見アルゴリズムのレビュー」IET Systems Biology . 6 (5): 164– 74. doi :10.1049/iet-syb.2011.0011. PMID  23101871.
2. Diestel, Reinhard (2005).グラフ理論（第3版）. ベルリン: Springer. ISBN 978-3-540-26182-7。
3. Milo R, Shen-Orr SS, Itzkovitz S, Kashtan N, Chklovskii D, Alon U (2002). 「ネットワークモチーフ：複雑ネットワークのシンプルな構成要素」. Science . 298 (5594): 824– 827. Bibcode :2002Sci...298..824M. CiteSeerX 10.1.1.225.8750 . doi :10.1126/science.298.5594.824. PMID  12399590. S2CID  9884096. 
4. Albert R, Barabási AL (2002). 「複雑ネットワークの統計力学」Reviews of Modern Physics . 74 (1): 47– 49. arXiv : cond-mat/0106096 . Bibcode :2002RvMP...74...47A. CiteSeerX 10.1.1.242.4753 . doi :10.1103/RevModPhys.74.47. S2CID  60545. 
5. Milo R, Itzkovitz S, Kashtan N, Levitt R, Shen-Orr S, Ayzenshtat I, Sheffer M, Alon U (2004). 「設計され進化したネットワークのスーパーファミリー」. Science . 303 (5663): 1538– 1542. Bibcode :2004Sci...303.1538M. doi :10.1126/science.1089167. PMID  15001784. S2CID  14760882.
6. Schwöbbermeyer, H (2008). 「ネットワークモチーフ」. Junker BH, Schreiber F (編). 『生物学的ネットワークの分析』. ホーボーケン、ニュージャージー州: John Wiley & Sons. pp.  85– 108.
7. Bornholdt, S; Schuster, HG (2003).グラフとネットワークハンドブック：ゲノムからインターネットまで. p. 417. Bibcode :2003hgnf.book.....B. {{cite encyclopedia}}:|journal=無視されました (ヘルプ)
8. Ciriello G, Guerra C (2008). 「タンパク質間相互作用ネットワークにおけるモチーフ発見のためのモデルとアルゴリズムのレビュー」. Briefings in Functional Genomics and Proteomics . 7 (2): 147– 156. doi : 10.1093/bfgp/eln015 . PMID  18443014.
9. Kashtan N, Itzkovitz S, Milo R, Alon U (2004). 「サブグラフ濃度の推定とネットワークモチーフの検出のための効率的なサンプリングアルゴリズム」.バイオインフォマティクス. 20 (11): 1746– 1758. doi : 10.1093/bioinformatics/bth163 . PMID  15001476.
10. Wernicke S (2006). 「ネットワークモチーフの効率的な検出」. IEEE/ACM Transactions on Computational Biology and Bioinformatics . 3 (4): 347– 359. Bibcode :2006ITCBB...3..347W. CiteSeerX 10.1.1.304.2576 . doi :10.1109/tcbb.2006.51. PMID  17085844. S2CID  6188339. 
11. Picard F, Daudin JJ, Schbath S , Robin S (2005). 「ネットワークモチーフの例外性の評価」J. Comp. Bio . 15 (1): 1– 20. CiteSeerX 10.1.1.475.4300 . doi :10.1089/cmb.2007.0137. PMID  18257674. 
12. Schreiber F, Schwöbbermeyer H (2005). 「ネットワークにおけるモチーフの解析のための頻度概念とパターン検出」Transactions on Computational Systems Biology III . Lecture Notes in Computer Science. Vol. 3737. pp.  89– 104. CiteSeerX 10.1.1.73.1130 . doi :10.1007/11599128_7. ISBN  978-3-540-30883-6。
13. Holland, PW, & Leinhardt, S. (1974). 社会ネットワークにおける局所構造の統計的分析. ワーキングペーパーNo.44, 全米経済研究所.
14. Holland, P., & Leinhardt, S. (1975). 『地域構造の統計分析：社会学的方法論』David Heise編. サンフランシスコ: Josey-Bass.
15. Holland, PW, & Leinhardt, S. (1976). 社会ネットワークにおけるローカル構造. 社会学的方法論, 7, 1-45.
16. Holland, PW, & Leinhardt, S. (1977). 社会測定データの構造検出法. Social Networks (pp. 411-432). Academic Press.
17. Shen-Orr SS, Milo R, Mangan S, Alon U (2002年5月). 「大腸菌の転写制御ネットワークにおけるネットワークモチーフ」Nat. Genet . 31 (1): 64–8 . doi : 10.1038/ng881 . PMID  11967538. S2CID  2180121.
18. Eichenberger P, Fujita M, Jensen ST, et al. (2004年10月). 「枯草菌の胞子形成過程における単一分化細胞型の遺伝子転写プログラム」. PLOS Biology . 2 (10) e328. doi : 10.1371/journal.pbio.0020328 . PMC 517825. PMID  15383836 . 
19. Milo R, Shen-Orr S, Itzkovitz S, Kashtan N, Chklovskii D, Alon U (2002年10月). 「ネットワークモチーフ：複雑ネットワークのシンプルな構成要素」. Science . 298 (5594): 824–7 . Bibcode :2002Sci...298..824M. CiteSeerX 10.1.1.225.8750 . doi :10.1126/science.298.5594.824. PMID  12399590. S2CID  9884096. 
20. Lee TI, Rinaldi NJ, Robert F, et al. (2002年10月). 「Saccharomyces cerevisiaeにおける転写制御ネットワーク」. Science . 298 (5594): 799– 804. Bibcode :2002Sci...298..799L. doi :10.1126/science.1075090. PMID  12399584. S2CID  4841222.
21. Odom DT, Zizlsperger N, Gordon DB, et al. (2004年2月). 「HNF転写因子による膵臓および肝臓遺伝子発現の制御」. Science . 303 (5662): 1378–81 . Bibcode :2004Sci...303.1378O. doi :10.1126/science.1089769. PMC 3012624. PMID 14988562  . 
22. Boyer LA, Lee TI, Cole MF, et al. (2005年9月). 「ヒト胚性幹細胞における中核転写制御回路」. Cell . 122 (6): 947–56 . doi :10.1016/j.cell.2005.08.020. PMC 3006442. PMID 16153702  . 
23. Iranfar N, Fuller D, Loomis WF (2006年2月). 「GBFとLagCを介したフィードフォワードループによるDictyosteliumにおける凝集後遺伝子の転写制御」. Dev. Biol . 290 (2): 460–9 . doi : 10.1016/j.ydbio.2005.11.035 . PMID  16386729.
24. Ma'ayan A, Jenkins SL, Neves S, et al. (2005年8月). 「哺乳類細胞ネットワークにおけるシグナル伝播中の制御パターンの形成」. Science . 309 (5737): 1078–83 . Bibcode :2005Sci...309.1078M. doi :10.1126/science.11 ​​08876. PMC 3032439. PMID 16099987  . 
25. Ptacek J, Devgan G, Michaud G, et al. (2005年12月). 「酵母におけるタンパク質リン酸化の包括的解析」(PDF) . Nature (投稿原稿). 438 (7068): 679– 84. Bibcode :2005Natur.438..679P. doi :10.1038/nature04187. PMID  16319894. S2CID  4332381.
26. Schreiber F, Schwobbermeyer H (2005). 「MAVisto：ネットワークモチーフ探索ツール」.バイオインフォマティクス. 21 (17): 3572– 3574. doi : 10.1093/bioinformatics/bti556 . PMID  16020473.
27. McKay BD (1981). 「実用グラフ同型性」. Congressus Numerantium . 30 : 45–87 . arXiv : 1301.1493 . Bibcode :2013arXiv1301.1493M.
28. McKay BD (1998). 「同型性のない網羅的生成」. Journal of Algorithms . 26 (2): 306– 324. doi :10.1006/jagm.1997.0898.
29. Chen J, Hsu W, Li Lee M, et al. (2006). NeMoFinder: メソスケールネットワークモチーフを用いたゲノムワイドなタンパク質間相互作用の解析. 第12回ACM SIGKDD国際知識発見・データマイニング会議. ペンシルベニア州フィラデルフィア. pp.  106– 115.
30. Huan J, Wang W, Prins J, et al. (2004). SPIN: グラフデータベースからの最大頻出サブグラフのマイニング. 第10回ACM SIGKDD国際会議「知識発見とデータマイニング」. pp.  581– 586.
31. Uetz P, Giot L, Cagney G, et al. (2000). 「Saccharomyces cerevisiaeにおけるタンパク質間相互作用の包括的解析」. Nature . 403 (6770): 623– 627. Bibcode :2000Natur.403..623U. doi :10.1038/35001009. PMID  10688190. S2CID  4352495.
32. Grochow JA, Kellis M (2007). サブグラフ列挙と対称性破壊を用いたネットワークモチーフ発見(PDF) . RECOMB. pp.  92– 106. doi :10.1007/978-3-540-71681-5_7.
33. Grochow JA (2006). タンパク質相互作用ネットワークの構造と進化について(PDF) . 修士論文, マサチューセッツ工科大学, 電気工学・コンピュータサイエンス学科.
34. Alon N; Dao P; Hajirasouliha I; Hormozdiari F; Sahinalp SC (2008). 「カラーコーディングによる生体分子ネットワークモチーフのカウントと発見」.バイオインフォマティクス. 24 (13): i241 – i249 . doi :10.1093/bioinformatics/btn163. PMC 2718641. PMID 18586721  .  
35. Omidi S, Schreiber F, Masoudi-Nejad A (2009). 「MODA：生物学的ネットワークにおけるネットワークモチーフ発見のための効率的なアルゴリズム」Genes Genet Syst . 84 (5): 385– 395. doi : 10.1266/ggs.84.385 . PMID  20154426.
36. Barabasi AL, Albert R (1999). 「ランダムネットワークにおけるスケーリングの出現」. Science . 286 (5439): 509– 512. arXiv : cond-mat/9910332 . Bibcode :1999Sci...286..509B. doi :10.1126/science.286.5439.509. PMID  10521342. S2CID  524106.
37. Vázquez A, Dobrin R, Sergi D, et al. (2004). 「複雑ネットワークにおける大規模属性と局所的相互作用パターンの位相的関係」. PNAS . 101 (52): 17940– 17945. arXiv : cond-mat/0408431 . Bibcode :2004PNAS..10117940V. doi : 10.1073/pnas.0406024101 . PMC 539752. PMID  15598746 . 
38. カシャニ ZR、アフラビアン H、エラヒ E、ノウザリ＝ダリーニ A、アンサリ ES、アサディ S、モハマディ S、シュライバー F、マスーディ＝ネジャド A (2009)。 「Kavosh: ネットワーク モチーフを見つけるための新しいアルゴリズム」。BMCバイオインフォマティクス。10 (318) 318.土井: 10.1186/1471-2105-10-318。PMC 2765973。PMID  19799800。 
39. Ali Masoudi-Nejad; Mitra Anasariola; Ali Salehzadeh-Yazdi; Sahand Khakabimamaghani (2012). 「CytoKavosh: 大規模生物学的ネットワークにおけるネットワークモチーフを見つけるためのCytoscapeプラグイン」. PLOS ONE . 7 (8) e43287. Bibcode :2012PLoSO...743287M. doi : 10.1371/journal.pone.0043287 . PMC 3430699. PMID  22952659 . 
40. Ribeiro P, Silva F (2010). G-Tries: ネットワークモチーフを発見するための効率的なデータ構造. ACM 25th Symposium On Applied Computing - Bioinformatics Track. Sierre, Switzerland. pp.  1559– 1566.^{[永久リンク切れ]}
41. Mbadiwe, Somadina; Kim, Wooyoung (2017年11月). 「ParaMODA: PPIネットワークにおけるモチーフ中心のサブグラフパターン検索の改善」. 2017 IEEE International Conference on Bioinformatics and Biomedicine (BIBM) . pp.  1723– 1730. doi :10.1109/BIBM.2017.8217920. ISBN 978-1-5090-3050-7. S2CID  5806529。
42. Huynh, Tien; Mbadiwe, Somadina; Kim, Wooyoung (2018). 「NemoMap: 改良型モチーフ中心ネットワークモチーフ発見アルゴリズム」. Advances in Science, Technology and Engineering Systems Journal . 3 (5): 186– 199. doi : 10.25046/aj030523 . 2023年2月4日時点のオリジナルよりアーカイブ。2020年9月11日閲覧。
43. Patra, Sabyasachi; Mohapatra, Anjali (2020). 「生物学的ネットワークにおけるネットワークモチーフ発見のためのツールとアルゴリズムのレビュー」. IET Systems Biology . 14 (4): 171– 189. doi : 10.1049/iet-syb.2020.0004 . ISSN  1751-8849. PMC 8687426. PMID 32737276  . 
44. Babu MM, Luscombe NM, Aravind L, Gerstein M, Teichmann SA (2004年6月). 「転写制御ネットワークの構造と進化」. Current Opinion in Structural Biology . 14 (3): 283–91 . CiteSeerX 10.1.1.471.9692 . doi :10.1016/j.sbi.2004.05.004. PMID  15193307. 
45. Conant GC, Wagner A (2003年7月). 「遺伝子回路の収束進化」. Nat. Genet . 34 (3): 264–6 . doi :10.1038/ng1181. PMID  12819781. S2CID  959172.
46. Dekel E, Alon U (2005年7月). 「タンパク質発現レベルの最適化と進化的チューニング」. Nature 436 ( 7050): 588–92 . Bibcode :2005Natur.436..588D. doi :10.1038/nature03842. PMID  16049495. S2CID  2528841.
47. Zabet NR (2011年9月). 「負のフィードバックと遺伝子の物理的限界」. Journal of Theoretical Biology . 284 (1): 82– 91. arXiv : 1408.1869 . Bibcode :2011JThBi.284...82Z. CiteSeerX 10.1.1.759.5418 . doi :10.1016/j.jtbi.2011.06.021. PMID  21723295. S2CID  14274912. 
48. Rosenfeld N, Elowitz MB, Alon U (2002年11月). 「負の自己調節は転写ネットワークの応答時間を短縮する」. J. Mol. Biol . 323 (5): 785–93 . CiteSeerX 10.1.1.126.2604 . doi :10.1016/S0022-2836(02)00994-4. PMID  12417193. 
49. Camas FM, Blázquez J, Poyatos JF (2006年8月). 「遺伝子ネットワークにおける応答の自律的および非自律的制御」Proc. Natl. Acad. Sci. USA . 103 (34): 12718–23 . Bibcode :2006PNAS..10312718C. doi : 10.1073/pnas.0602119103 . PMC 1568915 . PMID  16908855. 
50. Becskei A, Serrano L (2000年6月). 「遺伝子ネットワークの安定性を自動制御によって制御する」. Nature 405 ( 6786 ): 590–3 . Bibcode :2000Natur.405..590B. doi :10.1038/35014651. PMID  10850721. S2CID  4407358.
51. Dublanche Y, Michalodimitrakis K, Kümmerer N, Foglierini M, Serrano L (2006). 「転写負のフィードバックループにおけるノイズ：シミュレーションと実験的解析」Mol. Syst. Biol . 2 (1) 41. doi :10.1038/msb4100081. PMC 1681513. PMID 16883354  . 
52. Shimoga V, White J, Li Y, Sontag E, Bleris L (2013). 「合成哺乳類トランスジーン負性自己調節」. Mol. Syst. Biol . 9 670. doi :10.1038/msb.2013.27. PMC 3964311. PMID  23736683 . 
53. 前田雄三、佐野正之（2006年6月）「正のフィードバックを伴う合成遺伝子ネットワークの制御ダイナミクス」J. Mol. Biol . 359 (4): 1107–24 . doi :10.1016/j.jmb.2006.03.064. PMID  16701695.
54. Becskei A, Séraphin B, Serrano L (2001年5月). 「真核生物遺伝子ネットワークにおける正のフィードバック：段階的応答から二値応答への変換による細胞分化」. EMBO J. 20 ( 10): 2528–35 . doi :10.1093/emboj/20.10.2528. PMC 125456. PMID  11350942 . 
55. Mangan S, Alon U (2003年10月). 「フィードフォワードループネットワークモチーフの構造と機能」Proc. Natl. Acad. Sci. USA . 100 (21): 11980–5 . Bibcode :2003PNAS..10011980M. doi : 10.1073/pnas.2133841100 . PMC 218699. PMID 14530388  . 
56. Ma HW, Kumar B, Ditges U, Gunzer F, Buer J, Zeng AP (2004). 「大腸菌の拡張転写制御ネットワークとその階層構造およびネットワークモチーフの解析」Nucleic Acids Res . 32 (22): 6643–9 . doi :10.1093/nar/gkh1009. PMC 545451. PMID 15604458  . 
57. Mangan S, Zaslaver A, Alon U (2003年11月). 「コヒーレントフィードフォワードループは転写ネットワークにおいて符号感受性遅延要素として機能する」J. Mol. Biol . 334 (2): 197– 204. CiteSeerX 10.1.1.110.4629 . doi :10.1016/j.jmb.2003.09.049. PMID  14607112. 
58. Kalir S, Mangan S, Alon U (2005). 「SUM入力関数を用いたコヒーレントフィードフォワードループは大腸菌における鞭毛発現を延長させる」Mol. Syst. Biol . 1 (1) 2005.0006: E1 – E6 . doi :10.1038/msb4100010. PMC 1681456 . PMID  16729041.  
59. Xiong, Kun; Lancaster, Alex K.; Siegal, Mark L.; Masel, Joanna (2019年6月3日). 「フィードフォワード制御は、固有ノイズがある場合、トポロジーではなくダイナミクスを介して適応的に進化する」Nature Communications . 10 (1): 2418. Bibcode :2019NatCo..10.2418X. doi :10.1038/s41467-019-10388-6. PMC 6546794. PMID  31160574 . 
60. Mangan S, Itzkovitz S, Zaslaver A, Alon U (2006年3月). 「非コヒーレントなフィードフォワードループは大腸菌のガルシステムの応答時間を加速する」. J. Mol. Biol . 356 (5): 1073–81 . CiteSeerX 10.1.1.184.8360 . doi :10.1016/j.jmb.2005.12.003. PMID  16406067. 
61. Entus R, Aufderheide B, Sauro HM (2007年8月). 「3つの非コヒーレントフィードフォワードモチーフに基づく生物濃度センサーの設計と実装」. Syst Synth Biol . 1 (3): 119– 28. doi :10.1007/s11693-007-9008-6. PMC 2398716. PMID 19003446  . 
62. Kaplan S, Bren A, Dekel E, Alon U (2008). 「非コヒーレントなフィードフォワードループは遺伝子に対して非単調な入力関数を生成する可能性がある」Mol. Syst. Biol . 4 (1) 203. doi :10.1038/msb.2008.43. PMC 2516365. PMID  18628744 . 
63. Bleris L, Xie Z, Glass D, Adadey A, Sontag E, Benenson Y (2011). 「合成非コヒーレントフィードフォワード回路は、遺伝子テンプレートの量に応じて適応を示す」Mol. Syst. Biol . 7 (1) 519. doi :10.1038/msb.2011.49. PMC 3202791. PMID 21811230  . 
64. Xiong, Kun; Gerstein, Mark; Masel, Joanna (2021年11月5日). 「進化的アクセシビリティの違いが、同等に効果的などの調節モチーフがパルスを生成するために進化するかを決定する」. Genetics . 219 (3​​) iyab140. doi :10.1093/genetics/iyab140. PMC 8570775. PMID 34740240  . 
65. Kalir S, McClure J, Pabbaraju K, et al. (2001年6月). 「生細菌の発現動態解析による鞭毛経路における遺伝子の順序づけ」. Science . 292 (5524): 2080–3 . doi :10.1126/science.1058758. PMID  11408658. S2CID  14396458.
66. Zaslaver A, Mayo AE, Rosenberg R, et al. (2004年5月). 「代謝経路におけるジャストインタイム転写プログラム」. Nat. Genet . 36 (5): 486–91 . doi : 10.1038/ng1348 . PMID  15107854.
67. Konagurthu AS, Lesk AM (2008). 「調節ネットワークにおける単一および複数の入力モジュール」. Proteins . 73 (2): 320– 324. doi :10.1002/prot.22053. PMID  18433061. S2CID  35715566.
68. Kaplan S, Bren A, Zaslaver A, Dekel E, Alon U (2008年3月). 「多様な2次元入力関数が細菌の糖遺伝子を制御する」Mol. Cell . 29 (6): 786–92 . doi :10.1016/j.molcel.2008.01.021. PMC 2366073. PMID 18374652  . 
69. Chechik G, Oh E, Rando O, Weissman J, Regev A, Koller D (2008年11月). 「活性モチーフは酵母代謝ネットワークの転写制御におけるタイミング原理を明らかにする」Nat. Biotechnol . 26 (11): 1251–9 . doi :10.1038/nbt.1499. PMC 2651818. PMID 18953355  . 
70. Ingram PJ, Stumpf MP, Stark J (2006). 「ネットワークモチーフ：構造は機能を決定しない」. BMC Genomics . 7 108. doi : 10.1186/1471-2164-7-108 . PMC 1488845. PMID  16677373 . 
71. M , Alon U, Chklovskii DB (2004). 「C. elegans脳における計算モジュールの探索」BMC Biology 2 25. doi : 10.1186 /1741-7007-2-25 . PMC 539283. PMID  15574204. 
72. Qian J, Hintze A, Adami C (2011). 「色付きモチーフはC. elegans脳の計算構成要素を明らかにする」. PLOS ONE . 6 (3) e17013. arXiv : 1012.3641 . Bibcode :2011PLoSO...617013Q. doi : 10.1371/journal.pone.0017013 . PMC 3049772. PMID 21408227  . 
73. Voigt CA, Wolf DM, Arkin AP (2005年3月). 「枯草菌のsinオペロン：進化可能なネットワークモチーフ」. Genetics . 169 (3): 1187– 202. doi :10.1534/genetics.104.031955. PMC 1449569. PMID 15466432.  2023年2月4日時点のオリジナルよりアーカイブ。 2011年2月26日閲覧。 
74. Knabe JF, Nehaniv CL, Schilstra MJ (2008). 「モチーフは進化した機能を反映するのか？—遺伝子制御ネットワークサブグラフトポロジーの収束進化はない」BioSystems . 94 ( 1–2 ): 68– 74. Bibcode :2008BiSys..94...68K. doi :10.1016/j.biosystems.2008.05.012. PMID  18611431.
75. Taylor D, Restrepo JG (2011). 「合併と成長におけるネットワーク接続：モジュール追加の最適化」. Physical Review E. 83 ( 6) 066112: 66112. arXiv : 1102.4876 . Bibcode :2011PhRvE..83f6112T. doi :10.1103/PhysRevE.83.066112. PMID :  21797446. S2CID  : 415932.{{cite journal}}: CS1 maint: article number as page number (link)
76. Konagurthu, Arun S.; Lesk, Arthur M. (2008年4月23日). 「調節ネットワークにおける単一および複数の入力モジュール」.タンパク質：構造、機能、およびバイオインフォマティクス. 73 (2): 320– 324. doi :10.1002/prot.22053. PMID  18433061. S2CID  35715566.
77. Konagurthu AS, Lesk AM (2008). 「生物学的ネットワークにおけるモチーフの分布パターンの起源について」BMC Syst Biol . 2 73. doi : 10.1186/1752-0509-2-73 . PMC 2538512. PMID  18700017 . 

外部リンク

• ネットワークモチーフを検出できるソフトウェアツール
• 生物物理学ウィキ ネットワークモチーフ
• FANMOD: 高速ネットワークモチーフ検出ツール
• MAVisto: ネットワークモチーフ分析および可視化ツール
• ネモファインダー
• グロチョウ・ケリス
• モダ
• カヴォシュ
• サイトカヴォッシュ
• Gトライ
• acc-MOTIF検出ツール^{[永久リンク切れ]}

Retrieved from "https://en.wikipedia.org/w/index.php?title=Network_motif&oldid=1321448483"