Cargando…

Review of tools and algorithms for network motif discovery in biological networks

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 netwo...

Descripción completa

Detalles Bibliográficos
Autores principales: Patra, Sabyasachi, Mohapatra, Anjali
Formato: Online Artículo Texto
Lenguaje:English
Publicado: The Institution of Engineering and Technology 2020
Materias:
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC8687426/
https://www.ncbi.nlm.nih.gov/pubmed/32737276
http://dx.doi.org/10.1049/iet-syb.2020.0004
_version_ 1784618169892077568
author Patra, Sabyasachi
Mohapatra, Anjali
author_facet Patra, Sabyasachi
Mohapatra, Anjali
author_sort Patra, Sabyasachi
collection PubMed
description 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.
format Online
Article
Text
id pubmed-8687426
institution National Center for Biotechnology Information
language English
publishDate 2020
publisher The Institution of Engineering and Technology
record_format MEDLINE/PubMed
spelling pubmed-86874262022-02-16 Review of tools and algorithms for network motif discovery in biological networks Patra, Sabyasachi Mohapatra, Anjali IET Syst Biol Review Article 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. The Institution of Engineering and Technology 2020-08-01 /pmc/articles/PMC8687426/ /pubmed/32737276 http://dx.doi.org/10.1049/iet-syb.2020.0004 Text en © 2020 The Institution of Engineering and Technology https://creativecommons.org/licenses/by/3.0/This is an open access article published by the IET under the Creative Commons Attribution License (http://creativecommons.org/licenses/by/3.0/ (https://creativecommons.org/licenses/by/3.0/) )
spellingShingle Review Article
Patra, Sabyasachi
Mohapatra, Anjali
Review of tools and algorithms for network motif discovery in biological networks
title Review of tools and algorithms for network motif discovery in biological networks
title_full Review of tools and algorithms for network motif discovery in biological networks
title_fullStr Review of tools and algorithms for network motif discovery in biological networks
title_full_unstemmed Review of tools and algorithms for network motif discovery in biological networks
title_short Review of tools and algorithms for network motif discovery in biological networks
title_sort review of tools and algorithms for network motif discovery in biological networks
topic Review Article
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC8687426/
https://www.ncbi.nlm.nih.gov/pubmed/32737276
http://dx.doi.org/10.1049/iet-syb.2020.0004
work_keys_str_mv AT patrasabyasachi reviewoftoolsandalgorithmsfornetworkmotifdiscoveryinbiologicalnetworks
AT mohapatraanjali reviewoftoolsandalgorithmsfornetworkmotifdiscoveryinbiologicalnetworks