Network motifs are recurrent and statistically significant subgraphs or patterns of a larger graph. 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.
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.
Definitions Let and be two graphs. Graph is a sub-graph of graph (written as ) if and . If and contains all of the edges with , then is an induced sub-graph of . We call and isomorphic (written as ), if there exists a bijection (one-to-one correspondence) with for all . The mapping is called an isomorphism between and .
When and there exists an isomorphism between the sub-graph and a graph , this mapping represents an appearance of in . The number of appearances of graph in is called the frequency of in . A graph is called recurrent (or frequent) in when its frequency 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 of random graphs corresponding to the null-model associated to . We should choose random graphs uniformly from and calculate the frequency for a particular frequent sub-graph in . If the frequency of in is higher than its arithmetic mean frequency in random graphs , where , we call this recurrent pattern significant and hence treat as a network motif for . For a small graph , the network , and a set of randomized networks , where , the Z-score of the frequency of is given by
where and stand for the mean and standard deviation of the frequency in set , respectively. The larger the , the more significant is the sub-graph 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 (as its null-hypothesis), where 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 for the frequency of is defined as
where indicates the number of randomized networks, is defined over an ensemble of randomized networks, and the Kronecker delta function is one if the condition holds. The concentration of a particular n-size sub-graph in network 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 is defined over the set of all non-isomorphic n-size graphs. Another statistical measurement is defined for evaluating network motifs, 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 the figure illustrates, the first frequency concept considers all matches of a graph in original network. This definition is similar to what we have introduced above. The second concept is defined as the maximum number of edge-disjoint instances of a given graph in original network. And finally, the frequency concept entails matches with disjoint edges and nodes. Therefore, the two concepts and 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 network motif detection algorithm would pass over more candidate sub-graphs if we insist on frequency concepts and .
History The study of network motifs was pioneered by Holland and LeinhardtHolland, P. W., & Leinhardt, S. (1974). The statistical analysis of local structure in social networks. Working Paper No. 44, National Bureau of Economic Research.Holland, P., & Leinhardt, S. (1975). The Statistical Analysis of Local. Structure in Social Networks. Sociological Methodology, David Heise, ed. San Francisco: Josey-Bass.Holland, P. W., & Leinhardt, S. (1976). Local structure in social networks. Sociological methodology, 7, 1-45.Holland, P. W., & Leinhardt, S. (1977). A method for detecting structure in sociometric data. In Social Networks (pp. 411-432). Academic Press. who introduced the concept of a triad census of networks. They introduced methods to enumerate various types of subgraph configurations, and test whether the subgraph counts are statistically different from those expected in random networks.
This idea was further generalized in 2002 by Uri Alon and his group when network motifs were discovered in the gene regulation (transcription) network of the bacteria E. coli and then in a large set of natural networks. Since then, a considerable number of studies have been conducted on the subject. Some of these studies focus on the biological applications, while others focus on the computational theory of network motifs.
The biological studies endeavor to interpret the motifs detected for biological networks. For example, in work following, the network motifs found in E. coli were discovered in the transcription networks of other bacteria as well as yeast and higher organisms. A distinct set of network motifs were identified in other types of biological networks such as neuronal networks and protein interaction networks.
The computational research has focused on improving existing motif detection tools to assist the biological investigations and allow larger networks to be analyzed. Several different algorithms have been provided so far, which are elaborated in the next section in chronological order.
Most recently, the acc-MOTIF tool to detect network motifs was released.
Motif discovery algorithms Various solutions have been proposed for the challenging problem of network motif (NM) discovery. These algorithms can be classified under various paradigms such as exact counting methods, sampling methods, pattern growth methods and so on. However, motif discovery problem comprises two main steps: first, calculating the number of occurrences of a sub-graph and then, evaluating the sub-graph significance. The recurrence is significant if it is detectably far more than expected. Roughly speaking, the expected number of appearances of a sub-graph can be determined by a Null-model, which is defined by an ensemble of random networks with some of the same properties as the original network.
Until 2004, the only exact counting method for NM detection was the brute-force one proposed by Milo et al.. This algorithm was successful for discovering small motifs, but using this method for finding even size 5 or 6 motifs was not computationally feasible. Hence, a new approach to this problem was needed.
Here, a review on computational aspects of major algorithms is given and their related benefits and drawbacks from an algorithmic perspective are discussed.
Classification of algorithms The table below lists the motif discovery algorithms that will be described in this section. They can be divided into two general categories: those based on exact counting and those using statistical sampling and estimations instead. Because the second group does not count all the occurrences of a subgraph in the main network, the algorithms belonging to this group are faster, but they might yield in biased and unrealistic results.
In the next level, the exact counting algorithms can be classified to network-centric and subgraph-centric methods. The algorithms of the first class search the given network for all subgraphs of a given size, while the algorithms falling into the second class first generate different possible non-isomorphic graphs of the given size, and then explore the network for each generated subgraph separately. Each approach has its advantages and disadvantages which are discussed below.
The table also indicates whether an algorithm can be used for directed or undirected networks as well as induced or non-induced subgraphs.
+ Classification of Motif Discovery AlgorithmsCounting MethodBasisNameDirected / UndirectedInduced / Non-InducedExactNetwork-CentricmfinderBothInducedESU (FANMOD)BothInducedKavosh (used in CytoKavosh)BothInducedG-TriesBothInducedPGDUndirectedInducedSubgraph-CentricFPF (Mavisto)BothInducedNeMoFinderUndirectedInducedGrochow–KellisBothBothMODABothBothEstimation / SamplingColor-Coding ApproachN. Alon et al. AlgorithmUndirectedNon-InducedOther ApproachesmfinderBothInducedESU (FANMOD)BothInduced
mfinder Kashtan et al. published mfinder, the first motif-mining tool, in 2004. It implements two kinds of motif finding algorithms: a full enumeration and the first sampling method.
Their sampling discovery algorithm was based on edge sampling throughout the network. This algorithm estimates concentrations of induced sub-graphs and can be utilized for motif discovery in directed or undirected networks. The sampling procedure of the algorithm starts from an arbitrary edge of the network that leads to a sub-graph of size two, and then expands the sub-graph by choosing a random edge that is incident to the current sub-graph. After that, it continues choosing random neighboring edges until a sub-graph of size n is obtained. Finally, the sampled sub-graph is expanded to include all of the edges that exist in the network between these n nodes. When an algorithm uses a sampling approach, taking unbiased samples is the most important issue that the algorithm might address. The sampling procedure, however, does not take samples uniformly and therefore Kashtan et al. proposed a weighting scheme that assigns different weights to the different sub-graphs within network. The underlying principle of weight allocation is exploiting the information of the sampling probability for each sub-graph, i.e. the probable sub-graphs will obtain comparatively less weights in comparison to the improbable sub-graphs; hence, the algorithm must calculate the sampling probability of each sub-graph that has been sampled. This weighting technique assists mfinder to determine sub-graph concentrations impartially.
In expanded to include sharp contrast to exhaustive search, the computational time of the algorithm surprisingly is asymptotically independent of the network size. An analysis of the computational time of the algorithm has shown that it takes for each sample of a sub-graph of size from the network. On the other hand, there is no analysis in on the classification time of sampled sub-graphs that requires solving the graph isomorphism problem for each sub-graph sample. Additionally, an extra computational effort is imposed on the algorithm by the sub-graph weight calculation. But it is unavoidable to say that the algorithm may sample the same sub-graph multiple times – spending time without gathering any information. In conclusion, by taking the advantages of sampling, the algorithm performs more efficiently than an exhaustive search algorithm; however, it only determines sub-graphs concentrations approximately. This algorithm can find motifs up to size 6 because of its main implementation, and as result it gives the most significant motif, not all the others too. Also, it is necessary to mention that this tool has no option of visual presentation. The sampling algorithm is shown briefly: