Cargando…
Polynomial-Time Algorithm for Controllability Test of a Class of Boolean Biological Networks
In recent years, Boolean-network-model-based approaches to dynamical analysis of complex biological networks such as gene regulatory networks have been extensively studied. One of the fundamental problems in control theory of such networks is the problem of determining whether a given substance quan...
Autores principales: | , , |
---|---|
Formato: | Online Artículo Texto |
Lenguaje: | English |
Publicado: |
Springer
2010
|
Materias: | |
Acceso en línea: | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3171361/ https://www.ncbi.nlm.nih.gov/pubmed/20885776 http://dx.doi.org/10.1155/2010/210685 |
_version_ | 1782211745293533184 |
---|---|
author | Kobayashi, Koichi Imura, Jun-Ichi Hiraishi, Kunihiko |
author_facet | Kobayashi, Koichi Imura, Jun-Ichi Hiraishi, Kunihiko |
author_sort | Kobayashi, Koichi |
collection | PubMed |
description | In recent years, Boolean-network-model-based approaches to dynamical analysis of complex biological networks such as gene regulatory networks have been extensively studied. One of the fundamental problems in control theory of such networks is the problem of determining whether a given substance quantity can be arbitrarily controlled by operating the other substance quantities, which we call the controllability problem. This paper proposes a polynomial-time algorithm for solving this problem. Although the algorithm is based on a sufficient condition for controllability, it is easily computable for a wider class of large-scale biological networks compared with the existing approaches. A key to this success in our approach is to give up computing Boolean operations in a rigorous way and to exploit an adjacency matrix of a directed graph induced by a Boolean network. By applying the proposed approach to a neurotransmitter signaling pathway, it is shown that it is effective. |
format | Online Article Text |
id | pubmed-3171361 |
institution | National Center for Biotechnology Information |
language | English |
publishDate | 2010 |
publisher | Springer |
record_format | MEDLINE/PubMed |
spelling | pubmed-31713612011-09-13 Polynomial-Time Algorithm for Controllability Test of a Class of Boolean Biological Networks Kobayashi, Koichi Imura, Jun-Ichi Hiraishi, Kunihiko EURASIP J Bioinform Syst Biol Research Article In recent years, Boolean-network-model-based approaches to dynamical analysis of complex biological networks such as gene regulatory networks have been extensively studied. One of the fundamental problems in control theory of such networks is the problem of determining whether a given substance quantity can be arbitrarily controlled by operating the other substance quantities, which we call the controllability problem. This paper proposes a polynomial-time algorithm for solving this problem. Although the algorithm is based on a sufficient condition for controllability, it is easily computable for a wider class of large-scale biological networks compared with the existing approaches. A key to this success in our approach is to give up computing Boolean operations in a rigorous way and to exploit an adjacency matrix of a directed graph induced by a Boolean network. By applying the proposed approach to a neurotransmitter signaling pathway, it is shown that it is effective. Springer 2010-07-08 /pmc/articles/PMC3171361/ /pubmed/20885776 http://dx.doi.org/10.1155/2010/210685 Text en Copyright © 2010 Koichi Kobayashi et al. https://creativecommons.org/licenses/by/4.0/This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. |
spellingShingle | Research Article Kobayashi, Koichi Imura, Jun-Ichi Hiraishi, Kunihiko Polynomial-Time Algorithm for Controllability Test of a Class of Boolean Biological Networks |
title | Polynomial-Time Algorithm for Controllability Test of a Class of Boolean Biological Networks |
title_full | Polynomial-Time Algorithm for Controllability Test of a Class of Boolean Biological Networks |
title_fullStr | Polynomial-Time Algorithm for Controllability Test of a Class of Boolean Biological Networks |
title_full_unstemmed | Polynomial-Time Algorithm for Controllability Test of a Class of Boolean Biological Networks |
title_short | Polynomial-Time Algorithm for Controllability Test of a Class of Boolean Biological Networks |
title_sort | polynomial-time algorithm for controllability test of a class of boolean biological networks |
topic | Research Article |
url | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3171361/ https://www.ncbi.nlm.nih.gov/pubmed/20885776 http://dx.doi.org/10.1155/2010/210685 |
work_keys_str_mv | AT kobayashikoichi polynomialtimealgorithmforcontrollabilitytestofaclassofbooleanbiologicalnetworks AT imurajunichi polynomialtimealgorithmforcontrollabilitytestofaclassofbooleanbiologicalnetworks AT hiraishikunihiko polynomialtimealgorithmforcontrollabilitytestofaclassofbooleanbiologicalnetworks |