ネットワークモチーフ

ネットワーク モチーフは、より大きなグラフの反復的で統計的に重要な サブグラフまたはパターンです。生物学的ネットワーク、ソーシャル ネットワーク、テクノロジ ネットワーク (コンピュータ ネットワークや電気回路など) など、すべてのネットワークは、さまざまなサブグラフを含むグラフとして表現できます。

ネットワークモチーフは、特定のネットワーク内、またはさまざまなネットワーク間で繰り返されるサブグラフです。頂点間の特定の相互作用パターンによって定義されるこれらのサブグラフはそれぞれ、特定の機能が効率的に達成されるフレームワークを反映している可能性があります。実際、モチーフが特に重要なのは、主に機能特性を反映している可能性があるためです。モチーフは最近^{[いつ? ] 、}複雑なネットワークの構造設計原理を明らかにするための有用な概念として大きな注目を集めています。^[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 })}$

ここで、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 _{3 は}、互いに素なエッジとノードとの一致を伴います。したがって、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ツールがリリースされました。^[26]

ネットワーク モチーフ (NM) の発見という困難な問題に対して、さまざまなソリューションが提案されています。これらのアルゴリズムは、正確なカウント方法、サンプリング方法、パターン成長方法など、さまざまなパラダイムに分類できます。ただし、モチーフの発見問題は、2 つの主なステップで構成されます。最初にサブグラフの出現回数を計算し、次にサブグラフの重要性を評価します。再発が予想されるよりもはるかに多い場合、その再発は重要です。大まかに言えば、サブグラフの予想される出現回数は、元のネットワークと同じ特性を持つランダム ネットワークのアンサンブルによって定義される Null モデルによって決定できます。

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

ここでは、主要なアルゴリズムの計算面についてレビューし、アルゴリズムの観点から見た関連する利点と欠点について説明します。

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

次のレベルでは、正確なカウント アルゴリズムは、ネットワーク中心の方法とサブグラフ中心の方法に分類できます。最初のクラスのアルゴリズムは、指定されたネットワークで指定されたサイズのすべてのサブグラフを検索しますが、2 番目のクラスに分類されるアルゴリズムは、最初に指定されたサイズのさまざまな非同型グラフを生成し、次に生成されたサブグラフごとにネットワークを個別に探索します。各アプローチには、以下で説明する利点と欠点があります。

表には、アルゴリズムが有向ネットワークまたは無向ネットワーク、および誘導サブグラフまたは非誘導サブグラフに使用できるかどうかも示されています。詳細については、提供されている Web リンクまたはラボ アドレスを参照してください。

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

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

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

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

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

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

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

Wernicke ^{[10] は、} mfinder ^[9 ]を大幅に改善したRAND-ESUというアルゴリズムを発表しました。このアルゴリズムは、正確な列挙アルゴリズム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は再帰関数として実装できます。この関数の実行は、深さkのツリー構造として表示でき、ESU ツリーと呼ばれます (図を参照)。各 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アルゴリズム^{[28] [29]}を使用するだけで実装されています。したがって、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)の疑似コードを以下に示します。

Chen et al. ^{[30] は、} NeMoFinderと呼ばれる新しい NM 発見アルゴリズムを発表しました。これは、 SPIN ^[31]の考え方を応用して頻出木を抽出し、その後非同型グラフに拡張します。^[8] NeMoFinder は、頻出サイズ n 木を使用して入力ネットワークをサイズnグラフのコレクションに分割し、その後、頻出木をエッジごとに拡張して頻出サイズ n サブグラフを見つけて、完全なサイズnグラフK _nを取得します。このアルゴリズムは、無向ネットワークで NM を見つけ、誘導サブグラフのみの抽出に限定されません。さらに、NeMoFinder は正確な列挙アルゴリズムであり、サンプリング方法に基づいていません。Chen et al.が主張するように、NeMoFinder は比較的大きな NM の検出に適用でき、たとえば、著者らが主張するように、 S. cerevisiae (酵母) PPI ネットワーク全体からサイズ 12 までの NM を見つけることができます。^[32]

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

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

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

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

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

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

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

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

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

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

主なアイデアは次のとおりです。単純な基準により、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 のエッジで構成され、ルートから完全なグラフを保持するリーフ ノードまでのパスです。拡張ツリーの生成は^、[36]で説明されている簡単なルーチンで行うことができます。

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

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

特定のノードを含むサイズ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アルゴリズム^{[28] [29]}を採用する。Kavoshアルゴリズムの列挙部分を以下に示す。

最近、このソフトウェア用にCytoKavosh ^[40]と呼ばれるCytoscapeプラグインが開発されました。これはCytoscapeウェブページ[1] から入手できます。

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

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

前述のアルゴリズムの中では、G-Triesが最も高速です。ただし、このアルゴリズムの欠点はメモリを過剰に使用することであり、平均的なメモリを持つパソコンでは、検出可能なモチーフのサイズが制限される可能性があります。

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

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

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

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

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

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

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

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

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

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

このモチーフは、単一の調節因子が追加の調節なしに遺伝子セットを制御するときに発生します。これは、遺伝子が協力して特定の機能を実行し、常に同期して活性化する必要がある場合に役立ちます。相互作用の強度を調整することで、制御する遺伝子の一時的な発現プログラムを作成できます。^[67]

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

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

ネットワークモチーフの興味深い一般化として、活動モチーフは、ネットワーク内のノードとエッジに定量的な特徴が注釈付けされたときに見つかる過剰発生パターンです。たとえば、代謝経路のエッジに、対応する遺伝子発現の大きさやタイミングが注釈付けされている場合、基礎となるネットワーク構造を考えると、いくつかのパターンは過剰発生しています。^[70]

位相的サブ構造の保存の背後にある仮定（時には暗黙的、時には暗黙的ではない）は、それが特定の機能的重要性を持つということである。この仮定は最近疑問視されている。一部の著者は、バイファンモチーフなどのモチーフはネットワークのコンテキストに応じて多様性を示す可能性があり、したがって、^[71]モチーフの構造が必ずしも機能を決定するわけではないと主張している。ネットワーク構造が必ずしも機能を示すわけではないことは確かである。これは以前からある考え方であり、例としてSinオペロンを参照のこと。^[72]

モチーフ機能の分析のほとんどは、モチーフが単独で機能しているかどうかを調べることで行われている。最近の研究^[73]は、ネットワークのコンテキスト、つまりモチーフとネットワークの残りの部分とのつながりが、ローカル構造のみから機能について推論するには重要すぎるという良い証拠を提供している。引用された論文では、観察されたデータに対する批判や代替説明もレビューされている。単一のモチーフモジュールがネットワークのグローバルダイナミクスに与える影響の分析は、 ^[74]で研究されている。さらに最近の別の研究では、生物学的ネットワークの特定のトポロジカルな特徴が、標準的なモチーフの一般的な出現を自然に引き起こすことが示唆されており、モチーフの構造がネットワークの動作への機能的貢献のために選択されたことの証拠として、出現頻度が妥当であるかどうかが疑問視されている。^{[75] [76]}

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

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