Journal
IET SYSTEMS BIOLOGY
Volume 14, Issue 4, Pages 171-189Publisher
INST ENGINEERING TECHNOLOGY-IET
DOI: 10.1049/iet-syb.2020.0004
Keywords
computational complexity; graph theory; biology; search problems; network size; motif size; network motif discovery; biological networks; network composition; recurrent patterns; over-represented patterns; local properties; search space; subgraph isomorphism check; NP-complete problem; NP-complete problem; exact census; design principles; background algorithms; runtime efficiency; space requirement
Categories
Funding
- Department of Science and Technology, Government of India
Ask authors/readers for more resources
Network motifs are recurrent and over-represented patterns having biological relevance. This is one of the important local properties of biological networks. Network motif discovery finds important applications in many areas such as functional analysis of biological components, the validity of network composition, classification of networks, disease discovery, identification of unique subunits etc. The discovery of network motifs is a computationally challenging task due to the large size of real networks, and the exponential increase of search space with respect to network size and motif size. This problem also includes the subgraph isomorphism check, which is Nondeterministic Polynomial (NP)-complete. Several tools and algorithms have been designed in the last few years to address this problem with encouraging results. These tools and algorithms can be classified into various categories based on exact census, mapping, pattern growth, and so on. In this study, critical aspects of network motif discovery, design principles of background algorithms, and their functionality have been reviewed with their strengths and limitations. The performances of state-of-art algorithms are discussed in terms of runtime efficiency, scalability, and space requirement. The future scope, research direction, and challenges of the existing algorithms are presented at the end of the study.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available