Tuyển tập các báo cáo nghiên cứu về sinh học được đăng trên tạp chí sinh học Journal of Biology đề tài: Research Article Polynomial-Time Algorithm for Controllability Test of a Class of Boolean Biological Networks | Hindawi Publishing Corporation EURASIP Journal on Bioinformatics and Systems Biology Volume 2010 Article ID210685 12 pages doi 2010 210685 Research Article Polynomial-Time Algorithm for Controllability Test of a Class of Boolean Biological Networks Koichi Kobayashi 1 Jun-Ichi Imura 2 and Kunihiko Hiraishi1 1 School of Information Science Japan Advanced Institute of Science and Technology Nomi Ishikawa 923-1292 Japan 2 Graduate School of Information Science and Engineering Tokyo Institute of Technology Oh-okayama Tokyo 152-8552 Japan Correspondence should be addressed to Koichi Kobayashi k-kobaya@ Received 12 April 2010 Accepted 17 June 2010 Academic Editor Ilya Shmulevich Copyright 2010 Koichi Kobayashi et al. 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. 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. 1. Introduction Various approaches to modeling analysis and control
