Polynomial-Time Algorithm for Controllability Test of a Class of Boolean Biological Networks. (8th July 2010)

• Record Type: Journal Article
• Authors: Kobayashi Kobayashi, Koichi Koichi; Imura Imura, Jun-Ichi Jun-Ichi; Hiraishi Hiraishi, Kunihiko Kunihiko
• Other Names: Shmulevich Shmulevich Ilya Ilya Academic Editor.
• Is Part Of: EURASIP journal on bioinformatics and systems biology. Volume 2010(2010)
• Publication Date: 2010-07-08
• Subjects: Bioinformatics -- Periodicals; Systems biology -- Periodicals; Systems Biology; Signal Processing, Computer-Assisted; Bio-informatique; Biologie systémique; Bioinformatics; Systems biology; Systems Biology; Bioinformatics; Electronic journals; Periodical; Fulltext; Internet Resources; Periodicals; Periodicals; 570.285
• DOI: 10.1155/2010/210685
• Languages: English
• ISSNs: 1687-4145

Abstract

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