%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 }