A Fixed-Parameter Algorithm for Detecting a Singleton Attractor in an AND/OR Boolean Network with Bounded Treewidth

Chia-Jung CHANG  Takeyuki TAMURA  Kun-Mao CHAO  Tatsuya AKUTSU  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E98-A    No.1    pp.384-390
Publication Date: 2015/01/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E98.A.384
Type of Manuscript: PAPER
Category: Algorithms and Data Structures
Boolean network,  attractor,  partial k-tree,  fixed-parameter algorithm,  

Full Text: PDF>>
Buy this Article

The Boolean network can be used as a mathematical model for gene regulatory networks. An attractor, which is a state of a Boolean network repeating itself periodically, can represent a stable stage of a gene regulatory network. It is known that the problem of finding an attractor of the shortest period is NP-hard. In this article, we give a fixed-parameter algorithm for detecting a singleton attractor (SA) for a Boolean network that has only AND and OR Boolean functions of literals and has bounded treewidth k. The algorithm is further extended to detect an SA for a constant-depth nested canalyzing Boolean network with bounded treewidth. We also prove the fixed-parameter intractability of the detection of an SA for a general Boolean network with bounded treewidth.