Integer Programming-Based Approach to Attractor Detection and Control of Boolean Networks

Tatsuya AKUTSU  Yang ZHAO  Morihiro HAYASHIDA  Takeyuki TAMURA  

IEICE TRANSACTIONS on Information and Systems   Vol.E95-D   No.12   pp.2960-2970
Publication Date: 2012/12/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.E95.D.2960
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Fundamentals of Information Systems
Boolean networks,  genetic networks,  attractors,  integer programming,  nonlinear discrete systems,  

Full Text: PDF(425.8KB)>>
Buy this Article

The Boolean network (BN) can be used to create discrete mathematical models of gene regulatory networks. In this paper, we consider three problems on BNs that are known to be NP-hard: detection of a singleton attractor, finding a control strategy that shifts a BN from a given initial state to the desired state, and control of attractors. We propose integer programming-based methods which solve these problems in a unified manner. Then, we present results of computational experiments which suggest that the proposed methods are useful for solving moderate size instances of these problems. We also show that control of attractors is -hard, which suggests that control of attractors is harder than the other two problems.