Network motif

All networks, including biological networks, social networks, technological networks (e.g., computer networks and electrical circuits) and more, can be represented as graphs, which include a wide variety of subgraphs. One important local property of networks are so-called network motifs, which are defined as recurrent and statistically significant sub-graphs or patterns.1. Pick a random edge e1 = (vi, vj). Update Es = {e1}, Vs = {vi, vj}Result: Set R of patterns of size t with maximum frequency.P ←start pattern p1 of size 1Input: A graph G = (V, E) and an integer 1 ≤ k ≤ |V|.if |VSubgraph| = k then output G and returnG - PPI network;Output: Frequent Subgraph List: List of all frequent k-size sub-graphsInput: G: Input graph u: Root vertex S: selection (S = { S0,S1,...,Sk-1} is an array of the set of all Si) Remainder: number of remaining vertices to be selected i: Current depth of the tree.Output: all k-size sub-graphs of graph G rooted in u.Input: G: input graph, Parents: selected vertices of last layer, u: Root vertex.Output: Valid vertices of the current level. All networks, including biological networks, social networks, technological networks (e.g., computer networks and electrical circuits) and more, can be represented as graphs, which include a wide variety of subgraphs. One important local property of networks are so-called network motifs, which are defined as recurrent and statistically significant sub-graphs or patterns. Network motifs are sub-graphs that repeat themselves in a specific network or even among various networks. Each of these sub-graphs, defined by a particular pattern of interactions between vertices, may reflect a framework in which particular functions are achieved efficiently. Indeed, motifs are of notable importance largely because they may reflect functional properties. They have recently gathered much attention as a useful concept to uncover structural design principles of complex networks. Although network motifs may provide a deep insight into the network’s functional abilities, their detection is computationally challenging. Let G = (V, E) and G′ = (V′, E′) 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 exists 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 FG of G′ in G. A graph is called recurrent (or frequent) in G, when its frequency FG(G′) is above a predefined threshold or cut-off value. We use 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 Ri, 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 R(G) = N, the Z-Score that has been defined by the following formula: Z ( G ′ ) = F G ( G ′ ) − μ R ( G ′ ) σ R ( G ′ ) {displaystyle Z(G^{prime })={frac {F_{G}(G^{prime })-mu _{R}(G^{prime })}{sigma _{R}(G^{prime })}}} 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 FR(G′) ≥ FG(G′) (as its null-hypothesis), where FR(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 P ( G ′ ) = 1 N ∑ i = 1 N δ ( c ( i ) ) ; c ( i ) : F R i ( G ′ ) ≥ F G ( G ′ ) {displaystyle P(G^{prime })={frac {1}{N}}sum _{i=1}^{N}delta (c(i));c(i):F_{R}^{i}(G^{prime })geq F_{G}(G^{prime })} 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 C G ( G ′ ) = F G ( G ′ ) ∑ i F G ( G i ) {displaystyle C_{G}(G^{prime })={frac {F_{G}(G^{prime })}{sum _{i}F_{G}(G_{i})}}}