We propose a biologically motivated quantity, twinness , to evaluate local similarity between nodes in a network. The twinness of a pair of nodes is the number of connected, labeled subgraphs of size n in which the two nodes possess identical neighbours. The graph animal algorithm is used to estimate twinness for each pair of nodes (for subgraph sizes n =4 to n =12 ) in four different protein interaction networks (PINs). These include an Escherichia coli PIN and three Saccharomyces cerevisiae PINs — each obtained using state-of-the-art high-throughput methods. In almost all cases, the average twinness of node pairs is vastly higher than that expected from a null model obtained by switching links. For all n , we observe a difference in the ratio of type inlMMLBox twins (which are unlinked pairs) to type inlMMLBox twins (which are linked pairs) distinguishing the prokaryote E. coli from the eukaryote S. cerevisiae . Interaction similarity is expected due to gene duplication, and whole genome duplication paralogues in S. cerevisiae have been reported to co-cluster into the same complexes. Indeed, we find that these paralogous proteins are over-represented as twins compared to pairs chosen at random. These results indicate that twinness can detect ancestral relationships from currently available PIN data.
%0 Journal Article
%1 Penner2008Node
%A Penner, O.
%A Sood, V.
%A Musso, G.
%A Baskerville, K.
%A Grassberger, P.
%A Paczuski, M.
%D 2008
%J Physica A: Statistical Mechanics and its Applications
%K protein\_interaction, proteins networks biological-networks
%N 14
%P 3801--3810
%R 10.1016/j.physa.2008.02.043
%T Node similarity within subgraphs of protein interaction networks
%U http://dx.doi.org/10.1016/j.physa.2008.02.043
%V 387
%X We propose a biologically motivated quantity, twinness , to evaluate local similarity between nodes in a network. The twinness of a pair of nodes is the number of connected, labeled subgraphs of size n in which the two nodes possess identical neighbours. The graph animal algorithm is used to estimate twinness for each pair of nodes (for subgraph sizes n =4 to n =12 ) in four different protein interaction networks (PINs). These include an Escherichia coli PIN and three Saccharomyces cerevisiae PINs — each obtained using state-of-the-art high-throughput methods. In almost all cases, the average twinness of node pairs is vastly higher than that expected from a null model obtained by switching links. For all n , we observe a difference in the ratio of type inlMMLBox twins (which are unlinked pairs) to type inlMMLBox twins (which are linked pairs) distinguishing the prokaryote E. coli from the eukaryote S. cerevisiae . Interaction similarity is expected due to gene duplication, and whole genome duplication paralogues in S. cerevisiae have been reported to co-cluster into the same complexes. Indeed, we find that these paralogous proteins are over-represented as twins compared to pairs chosen at random. These results indicate that twinness can detect ancestral relationships from currently available PIN data.
@article{Penner2008Node,
abstract = {{We propose a biologically motivated quantity, twinness , to evaluate local similarity between nodes in a network. The twinness of a pair of nodes is the number of connected, labeled subgraphs of size n in which the two nodes possess identical neighbours. The graph animal algorithm is used to estimate twinness for each pair of nodes (for subgraph sizes n =4 to n =12 ) in four different protein interaction networks (PINs). These include an Escherichia coli PIN and three Saccharomyces cerevisiae PINs — each obtained using state-of-the-art high-throughput methods. In almost all cases, the average twinness of node pairs is vastly higher than that expected from a null model obtained by switching links. For all n , we observe a difference in the ratio of type inlMMLBox twins (which are unlinked pairs) to type inlMMLBox twins (which are linked pairs) distinguishing the prokaryote E. coli from the eukaryote S. cerevisiae . Interaction similarity is expected due to gene duplication, and whole genome duplication paralogues in S. cerevisiae have been reported to co-cluster into the same complexes. Indeed, we find that these paralogous proteins are over-represented as twins compared to pairs chosen at random. These results indicate that twinness can detect ancestral relationships from currently available PIN data.}},
added-at = {2019-06-10T14:53:09.000+0200},
author = {Penner, O. and Sood, V. and Musso, G. and Baskerville, K. and Grassberger, P. and Paczuski, M.},
biburl = {https://www.bibsonomy.org/bibtex/260ac86dd79d9bf756da0820609e6486a/nonancourt},
citeulike-article-id = {3424081},
citeulike-linkout-0 = {http://dx.doi.org/10.1016/j.physa.2008.02.043},
day = 01,
doi = {10.1016/j.physa.2008.02.043},
interhash = {56a0f29880578feb567a962d77170d46},
intrahash = {60ac86dd79d9bf756da0820609e6486a},
issn = {03784371},
journal = {Physica A: Statistical Mechanics and its Applications},
keywords = {protein\_interaction, proteins networks biological-networks},
month = jun,
number = 14,
pages = {3801--3810},
posted-at = {2008-10-17 12:26:31},
priority = {3},
timestamp = {2019-07-31T13:50:37.000+0200},
title = {{Node similarity within subgraphs of protein interaction networks}},
url = {http://dx.doi.org/10.1016/j.physa.2008.02.043},
volume = 387,
year = 2008
}