タンパク質相互作用グラフの分割のためのマルコフクラスタリングと親和性伝播

背景：タンパク質相互作用に関するゲノムスケールデータは、一般に、数百または数千のタンパク質が互いにリンクされている大きなネットワークまたはグラフとして表されます。タンパク質はグループまたは複合体で機能する傾向があるため、重要な目標は、これらのグラフからタンパク質複合体を確実に識別することでした。このタスクは、相互作用グラフ内の密に接続された領域を検出することを目的としたクラスタリング手順を使用して一般的に実行されます。豊富なクラスタリングアルゴリズムが存在し、その一部はこの問題に適用されています。このコンテキストで最も成功したクラスタリング手順の1つは、マルコフクラスターアルゴリズム（MCL）です。これは、最近、他の多くの手順を上回ることが示されました。アフィニティ伝播（AP）と呼ばれる新しい有望なクラスタリング手順は、最近特に効果的であり、さまざまな問題の他の方法よりもはるかに高速であることが示されましたが、分割タンパク質相互作用グラフにはまだ適用されていません。 結果：この作業では、アフィニティ伝播（AP）とマルコフクラスタリング（MCL）手順のパフォーマンスを比較します。この目的のために、S。cervisiaeの手でキュレーションされた408のタンパク質複合体からのタンパク質間相互作用の非加重ネットワークを導き出し、注釈付き複合体のリコールにおける2つのクラスタリングアルゴリズムの性能を評価します。そうすることで、これらのパラメーターの最適値を選択するために各アルゴリズムのパラメーター空間がサンプリングされ、アルゴリズムの堅牢性は、相互作用がランダムに追加またはノイズをシミュレートするために、複雑なリコールのレベルを定量化することにより評価されます。加重タンパク質相互作用グラフのパフォーマンスを評価するために、2つのアルゴリズムを、ゲノムスケール精製実験から派生したS. cerevisiaeの連結タンパク質相互作用ネットワークと、リンクのさまざまな割合がランダムに行われているこのネットワークのバージョンにも適用されます。シャッフル。 結論：私たちの分析は、MCL手順が騒音に対して大幅に耐性があり、APアルゴリズムよりも堅牢に動作することを示しています。APがテストした非加重グラフバージョンの大部分で深刻な収束問題を示しているのに対し、MCLは騒音レベルのレベルとして有意義なクラスターを特定し続けているため、APが非加重タンパク質相互作用グラフでは、非加重タンパク質相互作用グラフにとっては劇的です。グラフでは増加します。したがって、MCLは、バイナリ相互作用ネットワークからタンパク質複合体を識別するための選択方法のままです。

BACKGROUND: Genome scale data on protein interactions are generally represented as large networks, or graphs, where hundreds or thousands of proteins are linked to one another. Since proteins tend to function in groups, or complexes, an important goal has been to reliably identify protein complexes from these graphs. This task is commonly executed using clustering procedures, which aim at detecting densely connected regions within the interaction graphs. There exists a wealth of clustering algorithms, some of which have been applied to this problem. One of the most successful clustering procedures in this context has been the Markov Cluster algorithm (MCL), which was recently shown to outperform a number of other procedures, some of which were specifically designed for partitioning protein interactions graphs. A novel promising clustering procedure termed Affinity Propagation (AP) was recently shown to be particularly effective, and much faster than other methods for a variety of problems, but has not yet been applied to partition protein interaction graphs. RESULTS: In this work we compare the performance of the Affinity Propagation (AP) and Markov Clustering (MCL) procedures. To this end we derive an unweighted network of protein-protein interactions from a set of 408 protein complexes from S. cervisiae hand curated in-house, and evaluate the performance of the two clustering algorithms in recalling the annotated complexes. In doing so the parameter space of each algorithm is sampled in order to select optimal values for these parameters, and the robustness of the algorithms is assessed by quantifying the level of complex recall as interactions are randomly added or removed to the network to simulate noise. To evaluate the performance on a weighted protein interaction graph, we also apply the two algorithms to the consolidated protein interaction network of S. cerevisiae, derived from genome scale purification experiments and to versions of this network in which varying proportions of the links have been randomly shuffled. CONCLUSION: Our analysis shows that the MCL procedure is significantly more tolerant to noise and behaves more robustly than the AP algorithm. The advantage of MCL over AP is dramatic for unweighted protein interaction graphs, as AP displays severe convergence problems on the majority of the unweighted graph versions that we tested, whereas MCL continues to identify meaningful clusters, albeit fewer of them, as the level of noise in the graph increases. MCL thus remains the method of choice for identifying protein complexes from binary interaction networks.