dorsal/arxiv
View SchemaComparing Protein Interaction Networks via a Graph Match-and-Split Algorithm
| Authors | Manikandan Narayanan, Richard M. Karp |
|---|---|
| Categories | |
| ArXiv ID | q-bio/0702001 |
| URL | https://arxiv.org/abs/q-bio/0702001 |
Abstract
We present a method that compares the protein interaction networks of two species to detect functionally similar (conserved) protein modules between them. The method is based on an algorithm we developed to identify matching subgraphs between two graphs. Unlike previous network comparison methods, our algorithm has provable guarantees on correctness and efficiency. Our algorithm framework also admits quite general connectivity and local matching criteria that define when two subgraphs match and constitute a conserved module. We apply our method to pairwise comparisons of the yeast protein network with the human, fruit fly and nematode worm protein networks, using a lenient criterion based on connectedness and matching edges, coupled with a betweenness clustering heuristic. We evaluate the detected conserved modules against reference yeast protein complexes using sensitivity and specificity measures. In these evaluations, our method performs competitively with and sometimes better than two previous network comparison methods. Further under some conditions (proper homolog and species selection), our method performs better than a popular single-species clustering method. Beyond these evaluations, we discuss the biology of a couple of conserved modules detected by our method. We demonstrate the utility of network comparison for transferring annotations from yeast proteins to human ones, and validate the predicted annotations.
{
"annotation_id": "93137c10-b54f-4df8-8abb-b761eb51479c",
"date_created": "2026-03-02T18:01:35.573000Z",
"date_modified": "2026-03-02T18:01:35.573000Z",
"file_hash": "82c6664b95e83192516e499eb1d151033d37c16143139c6841ed11ce7bc5e1c2",
"private": false,
"record": {
"abstract": "We present a method that compares the protein interaction networks of two\nspecies to detect functionally similar (conserved) protein modules between\nthem. The method is based on an algorithm we developed to identify matching\nsubgraphs between two graphs. Unlike previous network comparison methods, our\nalgorithm has provable guarantees on correctness and efficiency. Our algorithm\nframework also admits quite general connectivity and local matching criteria\nthat define when two subgraphs match and constitute a conserved module.\n We apply our method to pairwise comparisons of the yeast protein network with\nthe human, fruit fly and nematode worm protein networks, using a lenient\ncriterion based on connectedness and matching edges, coupled with a betweenness\nclustering heuristic. We evaluate the detected conserved modules against\nreference yeast protein complexes using sensitivity and specificity measures.\nIn these evaluations, our method performs competitively with and sometimes\nbetter than two previous network comparison methods. Further under some\nconditions (proper homolog and species selection), our method performs better\nthan a popular single-species clustering method. Beyond these evaluations, we\ndiscuss the biology of a couple of conserved modules detected by our method. We\ndemonstrate the utility of network comparison for transferring annotations from\nyeast proteins to human ones, and validate the predicted annotations.",
"arxiv_id": "q-bio/0702001",
"authors": [
"Manikandan Narayanan",
"Richard M. Karp"
],
"categories": [
"q-bio.MN"
],
"title": "Comparing Protein Interaction Networks via a Graph Match-and-Split Algorithm",
"url": "https://arxiv.org/abs/q-bio/0702001"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "89e02d19-e356-4201-9963-c22987b1f135",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}