特定の問題を解決するための便利なデータ構造を特定することは、高性能な最終製品を達成するための主な要因の一つである。 Skienaが説明しているように、ジョブの間違ったデータ構造を選択することは、パフォーマンスの面で悲惨なことがありますが、同様に実行するいくつかの選

除算と征服のルールに基づいて、最初のステップは、便利なデータ構造を特定することによって、多項式時間で解決するのに十分な単純な別のサブ問題に解析問題を分解することです。 ここで、解析アルゴリズムは4つの部分に分割することができます: (1)ユーザーのタンパク質/化学識別子がReactomeに存在するかどうかを確認する(2)現在のものについては、これらが複合体および/またはセットの一部であるかどうか、および種の投影を見つけること、(3)これらが存在する経路（およびスーパー経路）で見つかった識別子を集計し、最後に(4)サンプル識別子と見つかった経路との間の関連がランダムな偶然によるものである可能性を計算するための統計的検定を行う。

さらに、このセクションでは、各部分について詳細に説明して、その特殊性を判断します; 選択されたデータ構造とその改善のために採用されたメカニズムを公開し、各ステップを次のステップに接続して最終的な改善された分析アルゴリ 最適化のためのもう一つの重点ポイントは、各ステップのメモリ使用量であり、充填されたデータ構造をメモリに保持して、それらの上に実装されたデー

Reactomeでのユーザーサンプル識別子検索

Reactomeでの注釈付き物理エンティティ（PE）は、単一のエンティティまたは複合体のいずれかになります。 単一の実体は、タンパク質、小分子、ＲＮＡ、ＤＮＡ、炭水化物、または脂質を含み、一方、複合体は、単一の実体のいずれか、または単一の実体から合成されたポリマーの組 しかし、これらの2つの主要なカテゴリとは別に、Reactomeのキュレーターは関連するエンティティをセットにグループ化することができます。 PEsは、後に反応における入力、出力、触媒または調節剤として使用されるビルディングブロックである。

識別子またはアクセッション番号は、単一のエンティティを明確に参照するために使用されますが、PEsは、メイン識別子、セカンダリ識別子、相互参照、同 メイン識別子スロットは、Reactome(キュレーター)でデータをキュレーションする専門家によって常に手動で注釈が付けられ、他のスロットはキュレーション中に手動で入力するか、リリースプロセス中に自動的に入力することができます。 この戦略により、幅広いリソースの識別子を格納できます: UniProt、ChEBI、Ensembl、miRBase、GenBank/EMBL/DDBJ、RefPep、RefSeq、EntrezGene、OMIM、InterPro、Affymetrix、Agilent、KEGG Compound、Illuminaなど

したがって、分析の最初の部分では、主な要件は、ユーザーのサンプル内の各識別子がReactome内の一つまたは多くのPEsに対応するかどうかを調べるプロセス 識別子は、前述の異なるスロットに格納されている識別子のいずれかと一致する場合、PEに対応します。 実際には、この問題を解決するための最良の方法は、逆のアプローチに従うことです; Reactomeで相互参照される各識別子ごとに対応するすべてのPEsを持つルックアップテーブルを作成します。 結果として、別の重要な要件は、クエリ時間を改善するためにデータをメモリに保持できるように、メモリ使用量を最小限に抑えることです。

優れたデータ構造の選択は、高速ルックアップテーブルを実装し、メモリ使用量を低く保つための要件によって決定されます。 トライは、キーが通常文字列である動的セットまたは連想配列を格納するために使用される順序付けられたツリーデータ構造です。 基数ツリーは、1つの子のみを持つ各ノードがその親とマージされる、スペース最適化されたトライデータ構造です。

一方で、基数ツリーは、共通の接頭辞がデータの重複を避けるために共有されるため、ルックアップテーブルのメモリ使用量が比較的低い（図。 1). 一方、検索キーとデータ構造からのキーとの等価性を比較するコストは、無視することができない支配的なコストになる可能性があります。 基数ツリー文字列ルックアップアルゴリズムは、ツリーノードを反復処理すると、reactomeターゲットセット内の各識別子の長さと存在に制限された識別子の探索時間を保持するため、解析アルゴリズムの本来の目的に適合します。 この結果、検索された識別子がデータ構造に含まれていない場合、文字列のハッシュ値を完全に読み取ることによってすべてのケースで計算する必要があるハッシュメソッドで起こるように、すべてを読み取る必要はありません。

要約すると、特定の識別子の基数ツリールックアップアルゴリズムに従ってツリーノードに到達すると、Pesへの参照の有無は、関連する識別子がデータベースに存在するかどうかを示します….. 実際には、言及された”PEへの参照”は、実際には分析の次の部分のために選択されたデータ構造内のノードへのポインタです。

Reactomeは、それが参照するPEs、特にタンパク質のためのUniProtと化学エンティティのためのChEBIのための一意の一次識別子を使用します。

Reactomeは、それが参照するPEs したがって、ユーザーがこれらの参照系を使用してデータセットを送信する場合、PEsへのマッピングは簡単です。 しかし、頻繁なユーザーの要求に続いて、我々はまた、非一意の識別子、特に遺伝子名を持つ入力データを受け入れます。 これらは、潜在的に複数のPEsにマッピングされます。 したがって、ツリー内の各ターゲットノードには、次のデータ構造への複数のポインタが含まれる可能性があります。

トラバース複合体/セット組成と種投影

特定の識別子の関連する単一のエンティティに到達することは、分析の第二ステップの始まりです。 これらの単一のエンティティが複合体の一部である場合、それらは分析のこのステップのターゲットでもあります。 単一の実体と複合体のほかに、集合と呼ばれる別のタイプのPEがあり、複合体とともに考慮されるべきである。 セットは、互いに相互作用していないが、セットが使用されている状況で機能的に同等である二つ以上のエンティティのグループの抽象表現であり、例えば、それぞれが潜在的に反応を触媒することができる酵素のファミリーの複数のメンバーである。 さらに、複合体と集合は、問題の複雑さを成長させるはるかに精巧な構造を表すために、他の複合体と集合を含むこともできます。

別の具体的な要件は、ヒトのためのより完全なReactome注釈の恩恵を受けるために、識別子が提供されている種とは独立してホモサピエンスの結果を収集するために種の投影を行う可能性である。 そのためには、Reactomeで注釈された種のオルソログを考慮する必要があります。 オルソログは、種分化によって共通の祖先から進化した異なる種の実体である。

このステップの最後の要件は、提出された識別子とReactomeで使用されている識別子との間の識別子マッピングを追跡して、単一のエンティティをキュレーションすることです。uniprot accessions for proteins、ensembl identifier for genes、chebi identifiers for small molecules、miRBase for microRNAs。 このマッピングの重要な部分は、前のステップの基数ツリーに識別子として既知の相互参照を含めることから始まりましたが、マッピング自体はこのステ

分析のこのステップのための露出された要件を要約すると、選択されたデータ構造は、エンティティ構成問題、種オルソログ投影およびエンティティマ 有向グラフは、グラフ、またはエッジによって接続されたノードのセットであり、エッジには方向が関連付けられています。 いくつかのノード（a、b、c、d）を持つグラフGに対して、Gがaからbへの矢印とbからcへの別の矢印を持つ場合、合成グラフg2はaからcへの矢印を持 Gがaからbへの矢印、bからcへの別の矢印、さらにcからdへの別の矢印を持つ場合、構成グラフG3はaからdへの矢印を持ちます。

種 図2a)およびそれらのすべてを相互接続して、すべてのオルソログノードを連結する(図2a)。 2b)投影要件が満たされるより大きなグラフを作成します。 最終的なグラフにおけるノードの一意性のために、ノードが一つ以上の構造化エンティティの一部である場合、それが含まれている構造と同じくらい他のグラフノードを指すエッジが含まれているため、構造化エンティティは簡単にモデル化されます。 最後に、グラフの各ノードがそれに関連するエンティティ主識別子を含む場合（図１ ４）。 図２ｃ）に示すように、主な識別子以外の識別子を表す基数ツリーノードから到達すると、この関連付けは、分析が終了すると、必要なマッピングとして結果の一部として提供されるために格納される。

Pはタンパク質であり、Cは複合体であり、Sは集合であり、素数ノードは同じであるが、他の種については同じである。 一つの種のグラフ。 二種の間のbの関係。 cベースノードコンテンツ

図のグラフ。 図２Ａは、３つのタンパク質（Ｐ１、Ｐ２およびＰ３）、２つの複合体（Ｃ１およびＣ２）、および２つのセット（Ｓ１およびＳ２）を示す。 ノードからノードへのエッジをたどることによって、S2はP2またはP3のいずれかであり、形式的には次のように表されます。 C1は、S2からのエッジのために、潜在的に2つの複合体である複合体である：{P1、P2}または{P1、P3}、として表される。 この分解に続いて、S1はその後であり、最後にC2は次のようになります。

たとえば、p3と一致する識別子が処理され、グラフ内の対応するノードが基数ツリーから到達すると、グラフを横断してノードS2、C1、S1、C2に到達す 同様に、標的タンパク質がＰ１である場合、グラフエッジに続く到達可能なノードは、Ｃ１、Ｓ１およびＣ２である。 両方の実施例では、各標的タンパク質は、横断されたノードによって表される複合体および集合の一部である。

グラフを使用すると、分析アルゴリズムのコストが向上し、メモリ内分析を構築する上で重要なことは、特定のメイン識別子のノードが一度だけメ さらに、アルゴリズムの最終的なノード反復回数は、特定の識別子の関連エンティティによって制限され、データベースベースのアプローチで行われるように、大量のデータに対するクエリと中間結果のマージを回避します。

上記の基数ツリーについては、グラフはアルゴリズムが次の分析ステップに進むことを可能にする戦略も必要です。 この場合、一つまたは複数の経路に直接関連するエンティティを表す各グラフノードは、それが存在する異なる場所と同様に、以下のデータ構造へのリンクを含むことになる。 現在の分析ステップでは、ターゲット識別子に関連付けられた各エンティティが検出されますが、最終的な結果と統計計算のために、次のサブセクショ

結果経路組織への集約

前のステップで直接的または間接的にヒットしたすべてのPEは、1つまたは複数の経路に関連付けられています。

結果は、経路組織への集約

各経路の有意性を計算するために、所与のユーザサンプルについて、経路ごとに見出される実体の数を決定することが不可欠である。 オントロジーのような階層におけるReactome経路の親子組織のために、エンティティが特定の経路に存在する場合、トップレベルの経路に到達するまで（すなわち、再帰的な方法でそのスーパー経路にも存在する。 タンパク質が”炭水化物の代謝”に存在する場合、それは”代謝”にも存在する）。

前に説明した要件を考慮すると、このステップをモデル化するための優れたデータ構造は、各ノードが経路を表し、その親と子へのリンクを含む二重リン 3). ツリー内のノードがヒットすると、アクションはルートまで再帰的に伝播することができます。 メモリフットプリントを減らすために、結果計算のための識別子、名前およびプレースホルダのみが各ノードに保持されます。

Reactomeのイベント階層を表す二重リンクツリー。 ルートノードは種を定義し、その子はReactomeの異なる経路とサブ経路を表します。 各ノードには、経路識別子、名前、キュレーションされたエンティティの合計、およびユーザーのサンプルで見つかったエンティティの数が含まれています

結果の収集を高速化するための便利なデータ構造であり、統計結果の優れた保持者であることとは別に、分析が終了すると、このデータ構造をファイルにシリアル化して結果を永続化することもできます。 さらに、ファイルをトークンに関連付けることで、サーバー側で結果をフィルタリングできるようにするより細かいメソッドを簡単に作成でき、軽量のクライ このシナリオでは、クライアントは最初の分析が完了するとトークンを保持でき、ユーザーのニーズに応じて、関連するトークンを参照するサーバーに複数の要求を

解析結果統計計算

過剰表現分析における基本的な仮説は、与えられた経路内の差動発現遺伝子の割合が、ランダムに予想される遺伝子の割合を超えている場合、関連する経路を検出できるということである。 したがって、分析方法の第四および最後のステップは、統計計算を含む。 このステップでは、二重リンクツリーが目的に完全に適合するため、追加のデータ構造は必要ありません。

p値は、与えられたサンプルの各ヒット経路の統計的有意性および分析が行われた背景を示す。

p値は、与えられたサンプルの各ヒット経路の統計的有意性および分析が行われた背景を示す。 Reactomeでは、統計的有意性を計算するために使用される方法は二項検定です。 P値とともに、偽発見率（FDR）は偽陽性を推定するのに役立ち、Benjamini-Hochbergアプローチを使用して計算されます。 前述したように、我々は以前に公開されたように基本的なアルゴリズムを維持しながら、Reactome経路解析の性能を最適化することに焦点を当ててきました。