Polynomial-Time Algorithm for Controllability Test of a Class of Boolean Biological Networks

Various approaches to modeling, analysis, and control synthesis of biological networks such as gene regulatory networks and metabolic networks have been recently developed in the control community as well as the theoretical biology community [1]. In these approaches, it is one of the final goals to develop systematic drug discovery and cancer treatment [2, 3]. Biological networks in general can be expressed by ordinary/partial differential equations with high nonlinearity and high dimensionality. Since such complexities cause difficulties in analysis and control design, various simpler models such as Petri nets, Bayesian networks, Boolean networks, and hybrid systems have been proposed for dealing with complex and large-scale biological networks at the expense of rigorous analysis (see e.g., [4, 5]).This paper discusses the controllability problem of biological networks. In gene regulatory networks, for example, the controllability problem is defined as the problem of determining whether expressions of genes of interest can be arbitrarily controlled by expressions of a specified set of the other genes. As far as we know, two approaches to the controllability analysis of such biological networks have been developed so far: a piecewise affine model-based approach and a Boolean network model-based approach. However, the former approach can be applied to only the class of relatively low-dimensional systems [6, 7].On the other hand, a Boolean network model, where binary state variables are assigned to nodes and the transition rules of the state are given by Boolean functions [8, 9], will be more practical for analysis of large-scale biological networks thanks to its bold simplification. Akutsu et al. have recently discussed the controllability problem of Boolean networks with control nodes and controlled nodes and have proven that this problem is NP-hard in a general setting [10]. Furthermore, they have proposed a polynomial-time algorithm for the classes of networks inc