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

Descripción completa

Detalles Bibliográficos
Autores principales: Kobayashi, Koichi, Imura, Jun-Ichi, Hiraishi, Kunihiko
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