Building blocks of biological networks: a review on major network motif discovery algorithms

摘要

In recent years, there has been a great interest in studying different aspects of complex networks in a range of fields. One important local property of networks is network motifs, recurrent and statistically significant sub-graphs or patterns, which assists researchers in the identification of functional units in the networks. Although network motifs may provide a deep insight into the network's functional abilities, their detection is computationally challenging. Therefore several algorithms have been introduced to resolve this computationally hard problem. These algorithms can be classified under various paradigms such as exact counting methods, sampling methods, pattern growth methods and so on. Here, the authors will give a review on computational aspects of major algorithms and enumerate their related benefits and drawbacks from an algorithmic perspective.