(a) A global map of conserved protein machineries (dense clusters and paths, denoted by arbitrary iDs) in the alignment of the PPi networks of yeast, worm, and fly. Clusters with high overlap (>15%) that share an enriched function are grouped together into regions (squares colored by the enriched function; color legend is omitted for simplicity). Solid links indicate overlapping regions; their thickness is proportional to the of shared proteins. hashed links indicate conserved paths connecting different clusters.

(b) (c)

(b) Aligning yeast and bacterial networks suggests that DnA replication (yeast proteins Rfc2/3/4/5 and bacterial protein dnaX; shaded in green) and protein degradation (yeast proteins Rpt1/2/3/4/5 and bacterial proteins ftsh, lon, and clpX; shaded in purple) are functionally linked. This conserved region also sheds light on the function of the bacterial protein hP1026 (circled in red). its inclusion in this region, interaction with the bacterial replication machinery (dnaX), and placement opposite of the yeast replication proteins all point to its involvement in DnA replication.

(c) interaction prediction.
The yeast proteins Gle2 and
Mad3 (circled in red) are not
known to interact. however,
the interaction of their
sequence-similar proteins
(y54G9A. 6 and Bub- 1 in worm
and Bub3 and Bub1 in fly)
and their inclusion in a conserved
subnetwork suggest that
the interaction is conserved
in yeast as well. Adapted from
Sharan et al. 32 and Kelley et al. 17

 

querying applications. Color coding was originally developed by Alon et al. 2 for searching for structured size-k subgraphs, such as simple paths and trees, within a graph. Its complexity is 2O(k) m, where m is the size of the searched graph. Color coding is based on the idea that by randomly assigning k distinct colors to the vertices of the graph, the task of finding a simple subgraph translates to that of finding a colorful

subgraph, namely, one spanning k
distinct colors. For certain classes of
tree-like subgraphs, the subsequent
search can be efficiently implemented
using dynamic programming. Since a
particular subgraph need not be col-
orful in a specific color assignment,
multiple color assignments should be
considered to retrieve a desired sub-
graph with high probability. Precisely,
the probability that a graph of size k is
colorful is k!/kk > e−k; hence, in expecta-
tion, ek iterations of the algorithm suf-
fice to detect the desired subgraph.