Bioinformatics Vol. 19 no. 15 2003
pages 1869-1874
© 2003 Oxford University Press
Greedily building protein networks with confidence
CuraGen Corporation, 555 Long Wharf Drive, New Haven, CT 06511, USA
Received on May 1, 2003
; revised on July 15, 2003
; accepted on July 15, 2003
Motivation: With genome sequences complete for human and model organisms, it is essential to understand how individual genes and proteins are organized into biological networks. Much of the organization is revealed by proteomics experiments that now generate torrents of data. Extracting relevant complexes and pathways from high-throughput proteomics data sets has posed a challenge, however, and new methods to identify and extract networks are essential. We focus on the problem of building pathways starting from known proteins of interest.
Results: We have developed an efficient, greedy algorithm, SEEDY, that extracts biologically relevant biological networks from protein–protein interaction data, building out from selected seed proteins. The algorithm relies on our previous study establishing statistical confidence levels for interactions generated by two-hybrid screens and inferred from mass spectrometric identification of protein complexes. We demonstrate the ability to extract known yeast complexes from high-throughput protein interaction data with a tunable parameter that governs the trade-off between sensitivity and selectivity. DNA damage repair pathways are presented as a detailed example. We highlight the ability to join heterogeneous data sets, in this case protein–protein interactions and genetic interactions, and the appearance of cross-talk between pathways caused by re-use of shared components.
Significance and comparison: The significance of the SEEDY algorithm is that it is fast, running time O[(E + V) log V] for V proteins and E interactions, a single adjustable parameter controls the size of the pathways that are generated, and an associated P-value indicates the statistical confidence that the pathways are enriched for proteins with a coherent function. Previous approaches have focused on extracting sub-networks by identifying motifs enriched in known biological networks. SEEDY provides the complementary ability to perform a directed search based on proteins of interest.
Availability: SEEDY software (Perl source), data tables and confidence score models (R source) are freely available from the author.
Contact: jbader{at}bme.jhu.edu
* Present Address: Department of Biomedical Engineering, Johns Hopkins University, 3400 N. Charles St, Baltimore, MD 21218, USA
CiteULike 
Connotea 
Del.icio.us What's this?
This article has been cited by other articles:
|
|
 |
|
  V. Pihur, S. Datta, and S. Datta Reconstruction of genetic association networks from microarray data: a partial least squares approach Bioinformatics, February 15, 2008; 24(4): 561 - 568. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
C. L. Myers and O. G. Troyanskaya Context-sensitive data integration and prediction of biological networks Bioinformatics, September 1, 2007; 23(17): 2322 - 2330. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 C. Prieto and J. De Las Rivas APID: Agile Protein Interaction DataAnalyzer. Nucleic Acids Res., July 1, 2006; 34(Web Server issue): W298 - W302. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 M. Krauthammer, C. A. Kaufmann, T. C. Gilliam, and A. Rzhetsky Molecular triangulation: Bridging linkage and molecular-network information for identifying candidate genes in Alzheimer's disease PNAS, October 19, 2004; 101(42): 15148 - 15153. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 P. JORGENSEN, B.-J. BREITKREUTZ, K. BREITKREUTZ, C. STARK, G. LIU, M. COOK, J. SHAROM, J.L. NISHIKAWA, T. KETELA, D. BELLOWS, et al. Harvesting the Genome's Bounty: Integrative Genomics Cold Spring Harb Symp Quant Biol, January 1, 2003; 68(0): 431 - 444. [Abstract] [PDF]
|
|