Motifs in Biological Networks

Biological networks provide great potential to understand how cells function. Motifs in biological networks, frequent topological patterns, represent key structures through which biological networks operate. Studying motifs answers important biological questions. Finding motifs in biological networks remains to be a computationally challenging task as the sizes of the motif and the underlying network grow. Several algorithms exist in the literature to solve this problem. This chapter discusses the biological significance of network motifs, motivation behind solving the motif detection problem and the key challenges of this problem. We discuss different formulations of motif detection problem based on several orthogonal perspectives that change the problem definition as well as solution significantly. The first perspective considers the number of input networks involved (i.e., one or more than one networks). The second perspective focuses on the labeling (i.e., labeled or unlabeled) of the nodes and edges of the input network. The third one considers different frequency definitions of counting motif instances (i.e., F1, F2, and F3) in a network. The fourth perspective describes whether the underlying network is directed or undirected. The last one considers motif detection under different types of network models (i.e., deterministic, probabilistic, or dynamic model). As a case study for each formulation, we briefly discuss important existing methods from the literature. Finally, we conclude with future research directions.