Polynomial-time controllability analysis of Boolean networks

This paper discusses the controllability problem of Boolean networks with inputs (control nodes) and outputs (controlled nodes). An algorithm for testing controllability is in general NP-hard, and the existing polynomial-time algorithm is limited to a class of tree-structure networks. In this paper,...

Full description

Saved in:
Bibliographic Details
Main Authors: Kobayashi, K., Imura, J.-i., Hiraishi, K.
Format: Conference Proceeding
Language:English
Subjects:
Biological control systems
Biological system modeling
Biology
Boolean functions
Controllability
Large-scale systems
Polynomials
Sufficient conditions
Testing
Tree graphs
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:This paper discusses the controllability problem of Boolean networks with inputs (control nodes) and outputs (controlled nodes). An algorithm for testing controllability is in general NP-hard, and the existing polynomial-time algorithm is limited to a class of tree-structure networks. In this paper, based on a sufficient condition for controllability, a polynomial-time algorithm is proposed. The proposed algorithm is applicable to a wider class of large-scale Boolean networks compared with the existing algorithm. The key idea in our approach is to use an adjacency matrix of a directed graph induced by a Boolean network, and Boolean operations are not focused. The effectiveness of the proposed approach is shown by an example of a biological network.
ISSN:0743-1619
2378-5861
DOI:10.1109/ACC.2009.5160280