Toward accurate reconstruction of functional protein networks

Abstract

Genome-scale screening studies are gradually accumulating a wealth of data on the putative involvement of hundreds of genes/proteins in various cellular responses or functions. A fundamental challenge is to chart out the protein pathways that underlie these systems. Previous approaches to the problem have either employed a local optimization criterion, aiming to infer each pathway independently, or a global criterion, searching for the overall most parsimonious subnetwork. Here, we study the trade-off between the two approaches and present a new intermediary scheme that provides explicit control over it. We demonstrate its utility in the analysis of the apoptosis network in humans, and the telomere length maintenance (TLM) system in yeast. Our results show that in the majority of real-life cases, the intermediary approach provides the most plausible solutions. We use a new set of perturbation experiments measuring the role of essential genes in telomere length regulation to further study the TLM network. Surprisingly, we find that the proteasome plays an important role in telomere length regulation through its associations with transcription and DNA repair circuits.

Figure 1

Method overview. (A) Illustration of the network construction problem. We are given a network of interacting proteins, a subset of phenotype-related proteins (terminal nodes), and an anchor point (root node). The goal is to construct a subnetwork composed of signaling-regulatory pathways that lead from the phenotype-related set to the anchor point. We use three approaches for reconstructing these subnetworks––local optimization using the shortest path algorithm, global optimization using the Steiner tree algorithm and the intermediate approach using the Charikar-α algorithm. (B) Theoretical approximation bounds are displayed for the global, local and combined objectives. k is the number of terminal nodes. In this figure, we use an α value of 0.25. In the general case (0⩽α⩽0.5), Charikar-α provide bounds of O(k^1–α), O(k^½+α), and O(k^{max{1–α,½+α}}) for the global, local and combined objectives respectively (Supplementary information).

Figure 2

Performance of the different approaches on the apoptosis data. Presented measures include functional coherence (fraction of functionally coherent pathways) and predictive score (the ability to recover unannotated APT proteins, measured using the Jaccard index). The percentage of non-terminal nodes (i.e. proteins not on the APT set) in the models is presented in the inset, with methods ordered similarly to the main figure.

Figure 3

The proteasome's role in telomere length regulation. Green nodes: TLM proteins, the mutants of which have elongated telomeres; blue nodes: TLM proteins, the mutants of which have short telomeres; yellow nodes: essential proteins that showed a short TLM phenotype in our new experimental data set. Beige nodes, TLM protein from the literature, the effect (short or long) of which on telomere length is not readily available; red nodes: protein products of essential genes (not on the TLM list); gray nodes: protein products of non-essential genes and not on the TLM list; purple node: the TELOMERE anchor node. (A) The mediator complex and the proteasome. Green frame: mediator complex components; red frame: proteasome subunits; blue frame: Est1/3 components of the telomerase. (B) DNA repair components and the proteasome. Green frame: Slx5(Hex3)–Slx8 complex; red frame: proteasome subunits; light blue frame: KEOPS complex; pink frame: MRX complex; yellow frame: ribonuclease H2 subunits. (C) Telomere Southern blot of the essential genes RGR1, PRE2, RPN6, RPN12 and RPT3 from the DAmP Yeast Library. DNA was digested with XhoI and probed with telomeric sequences and with unique genomic sequences used as markers (Askree et al, 2004). A red line marks the telomere size of the wild-type strain.