These tools will no longer be maintained as of December 31, 2024. Archived website can be found here. PubMed4Hh GitHub repository can be found here. Contact NLM Customer Service if you have questions.


Pubmed for Handhelds

PUBMED FOR HANDHELDS

Search MEDLINE/PubMed

  • Title: Efficient and robust prediction algorithms for protein complexes using Gomory-Hu trees.
    Author: Mitrofanova A, Farach-Colton M, Mishra B.
    Journal: Pac Symp Biocomput; 2009; ():215-26. PubMed ID: 19209703.
    Abstract:
    Two-Hybrid (Y2H) Protein-Protein interaction (PPI) data suffer from high False Positive and False Negative rates, thus making searching for protein complexes in PPI networks a challenge. To overcome these limitations, we propose an efficient approach which measures connectivity between proteins not by edges, but by edge-disjoint paths. We model the number of edge-disjoint paths as a network flow and efficiently represent it in a Gomory-Hu tree. By manipulating the tree, we are able to isolate groups of nodes sharing more edge-disjoint paths with each other than with the rest of the network, which are our putative protein complexes. We examine the performance of our algorithm with Variation of Information and Separation measures and show that it belongs to a group of techniques which are robust against increased false positive and false negative rates. We apply our approach to yeast , mouse, worm, and human Y2H PPI networks, where it shows promising results. On yeast network, we identify 38 statistically significant protein clusters, 20 of which correspond to protein complexes and 16 to functional modules.
    [Abstract] [Full Text] [Related] [New Search]