Network Motif - Definition

Definition

Let and be two graphs, graph G′ is a sub-graph of graph G (written as G′ ⊆ G) if V′ ⊆ V and E′ ⊆ E ∩ (V′ × V′). If G′ ⊆ G and G′ contains all of the edges ‹u, v› ∈ E with u, v ∈ V′, then G′ is an induced sub-graph of G. We call G′ and G isomorphic (written as G′ ↔ G), if there exists a bijection (one-to-one) f:V′ → V with ‹u, v› ∈ E′ ⇔ ‹f(u), f(v)› ∈ E for all u, v ∈ V′. The mapping f is called an isomorphism between G and G′.

When G″ ⊂ G and there exist an isomorphism between the sub-graph G″ and a graph G′, this mapping represents an appearance of G′ in G. The number of appearances of graph G′ in G is called the frequency F_G of G′ in G. A graph is called recurrent (or frequent) in G, when its frequency F_G(G′) is above a predefined threshold or cut-off value. We used terms pattern and frequent sub-graph in this review interchangeably. There is an ensemble Ω(G) of random graphs corresponding to the null-model associated to G. We should choose N random graphs uniformly from Ω(G) and calculate the frequency for a particular frequent sub-graph G′ in G. If the frequency of G′ in G is higher than its arithmetic mean frequency in N random graphs R_i, where 1 ≤ i ≤ N, we call this recurrent pattern significant and hence treat G′ as a network motif for G. For a small graph G′, the network G and a set of randomized networks R(G) ⊆ Ω(R), where, the Z-Score that has been defined by the following formula:

where μ_R(G′) and σ_R(G′) stand for mean and standard deviation frequency in set R(G), respectively. The larger the Z(G′), the more significant is the sub-graph G′ as a motif. Alternatively, another measurement in statistical hypothesis testing that can be considered in motif detection is the P-Value, given as the probability of F_R(G′) ≥ F_G(G′) (as its null-hypothesis), where F_R(G′) indicates the frequency of G' in a randomized network. A sub-graph with P-value less than a threshold (commonly 0.01 or 0.05) will be treated as a significant pattern. The P-value is defined as

Where N indicates number of randomized networks, i is defined over an ensemble of randomized networks and the Kronecker delta function δ(c(i)) is one if the condition c(i) holds. The concentration of a particular n-size sub-graph G′ in network G refers to the ratio of the sub-graph appearance in the network to the total n-size non-isomorphic sub-graphs’ frequencies, which is formulated by

where index i is defined over the set of all non-isomorphic n-size graphs. Another statistical measurement is defined for evaluating NMs, but it is rarely used in known algorithms. This measurement is introduced by Picard et al. in 2008 and used the Poisson distribution, rather than the Gaussian normal distribution that is implicitly being used above.

In addition, three specific concepts of sub-graph frequency have been proposed. As figure illustrates, the first frequency concept F₁ considers all matches of a graph in original network. This definition is similar to what we have introduced above. The second concept F₂ is defined as the maximum number of edge-disjoint instances of a given graph in original network. And finally, the frequency concept F₃ entails matches with disjoint edges and nodes. Therefore, the two concepts F₂ and F₃ restrict the usage of elements of the graph, and as can be inferred, the frequency of a sub-graph declines by imposing restrictions on network element usage. As a result, a NM detection algorithm would pass over more candidate sub-graphs if we insist on frequency concepts F₂ and F₃.