SECOIA：コンテキストに敏感なランダムウォークとネットワークコンダクタンスの最小化を通じて、有意性強化ネットワーククエリ

背景：ネットワーククエリアルゴリズムは、経路や分子複合体などの既知の機能モジュールに類似した大規模な生物学的ネットワークで保存されたネットワークモジュールを識別する計算手段を提供します。ネットワーククエリアルゴリズムの2つの主な課題は、クエリとターゲットグラフの間の潜在的な同型性を検出し、クエリ結果の生物学的意義を確保するための高い計算の複雑さです。 結果：この論文では、ネットワーク比較のためにコンテキストに敏感なランダムウォーク（CSRW）モデルを利用し、ターゲットネットワーク内の潜在的な一致のネットワークコンダクタンスを最小化することにより、これらの問題に効果的に対処するアルゴリズムを照会する新しいネットワークをクエリする新しいネットワークであるSequoiaを提案します。シーケンスの比較とアライメントに広く使用されているペアの隠されたマルコフモデル（ペア-HMM）に触発されたCSRWモデルは、ノードの挿入と削除を説明することにより、異なるグラフ間のノード間対応を正確に評価できます。提案されたアルゴリズムは、CSRWスコアに基づいて高スコアネットワーク領域を識別し、その後、特定されたサブネットワークのネットワークコンダクタンスを最大限に削減することにより拡張されます。 結論：実際のPPIネットワークと既知の分子複合体に基づくパフォーマンス評価は、セコイアが既存の方法を上回り、クエリ結果の生物学的意義を明確に強化することを示しています。ソースコードとデータセットは、http：//www.ece.tamu.edu/~bjyoon/sequoiaからダウンロードできます。

BACKGROUND: Network querying algorithms provide computational means to identify conserved network modules in large-scale biological networks that are similar to known functional modules, such as pathways or molecular complexes. Two main challenges for network querying algorithms are the high computational complexity of detecting potential isomorphism between the query and the target graphs and ensuring the biological significance of the query results. RESULTS: In this paper, we propose SEQUOIA, a novel network querying algorithm that effectively addresses these issues by utilizing a context-sensitive random walk (CSRW) model for network comparison and minimizing the network conductance of potential matches in the target network. The CSRW model, inspired by the pair hidden Markov model (pair-HMM) that has been widely used for sequence comparison and alignment, can accurately assess the node-to-node correspondence between different graphs by accounting for node insertions and deletions. The proposed algorithm identifies high-scoring network regions based on the CSRW scores, which are subsequently extended by maximally reducing the network conductance of the identified subnetworks. CONCLUSIONS: Performance assessment based on real PPI networks and known molecular complexes show that SEQUOIA outperforms existing methods and clearly enhances the biological significance of the query results. The source code and datasets can be downloaded from http://www.ece.tamu.edu/~bjyoon/SEQUOIA .