Network motifs in integrated cellular networks of transcription-regulation and protein-protein interaction

Abstract

Genes and proteins generate molecular circuitry that enables the cell to process information and respond to stimuli. A major challenge is to identify characteristic patterns in this network of interactions that may shed light on basic cellular mechanisms. Previous studies have analyzed aspects of this network, concentrating on either transcription-regulation or protein-protein interactions. Here we search for composite network motifs: characteristic network patterns consisting of both transcription-regulation and protein-protein interactions that recur significantly more often than in random networks. To this end we developed algorithms for detecting motifs in networks with two or more types of interactions and applied them to an integrated data set of protein-protein interactions and transcription regulation in Saccharomyces cerevisiae. We found a two-protein mixed-feedback loop motif, five types of three-protein motifs exhibiting coregulation and complex formation, and many motifs involving four proteins. Virtually all four-protein motifs consisted of combinations of smaller motifs. This study presents a basic framework for detecting the building blocks of networks with multiple types of interactions.

Fig. 1.

The randomization procedure. (a) Extended node degree and edge profile. Nodes represent proteins; black, bidirected edges represent PPIs; and red, directed edges represent TRIs. Extended node degrees: a, one PPI, one outgoing TRI, and two ingoing TRIs; b, two PPIs and one outgoing TRI; c, one PPI and one outgoing TRI; d, two PPIs, one outgoing TRI, and two ingoing TRIs. Examples for edge profiles: (a,b), one PPI and one ingoing TRI; (b,a), one PPI and one outgoing TRI; (a,d), one outgoing TRI and one ingoing TRI; (b,d), one PPI. The edge profile of (d,c) is equivalent to that of (a,b). (b) The four-point-switchability condition. If edge profile (s₁,t₁) = edge profile (s₂,t₂) and edge profile (s₁,t₂) = edge profile (s₂,t₁), then edges can be switched as exemplified. For clarity, each edge color represents a type of edge profile. Note that if (s₁,t₁; s₂,t₂) are switchable, then so are (s₁,t₂;s₂,t₁), (t₁,s₁;t₂,s₂), and (t₂,s₁;t₁,s₂). Switch-ability is considered only for cases in which all four nodes are distinct and at least one edge profile is not empty.

Fig. 2.

All possible interaction patterns between two connected proteins. A node represents a gene and its protein product; a red, directed edge represents a TRI; and a black bidirected edge represents a PPI.

Fig. 3.

Four-protein network motifs discovered in the stringent network. (a) Motifs that can be represented as combinations of three-protein network motifs. When there is more than one possible way to generate a four-protein motif, the combination involving the more abundant three-protein motifs is presented. The three-protein motif of a mixed-feedback loop between coregulating proteins (Table 2, motif E) was not included here, because by itself it is a combination of two other three-protein motifs. Dangling motifs, where a fourth node is connected to only one of the nodes of the three-protein motif, are not presented. A three-protein motif may appear more than once in a combination that yields a four-protein motif [e.g., entry (A,D)]. (b) Motifs that cannot be constructed from three-protein motifs. i, the bi-fan motif; ii, a motif containing a feed-forward loop; iii–vi, motifs that appear as extensions of smaller network motifs, for which one of the PPIs in each smaller motif (Left) is extended to a series of PPIs by means of an intermediate protein (Right). A node represents a gene and its protein product; a red, directed edge represents a TRI; and a black, bidirected edge represents a PPI.